Cell Mitosis:
There’s a scientist named Brook who is interested in budding of cells. He has one container which initially contains only a single cell. Now Brook wants n number of cells in his container. So he can change the number of cells in container in 3 different ways -:
Double the number of cells present in the container.
Increase the number of cells in the container by 1.
Decrease the number of cells in the container by 1.
Now, all the above operations have different costs associated with them x,y,z respectively for above operations. Help brook in finding the minimum cost to generate n cells in the container starting from one cell .
My solution:
Solving is to make sure, we don’t get stuck in in infinite recursion like for example when we are at state 2, we can got state 1,3,4 . Assume we go to 4, from 4 we can go to 3.5.8. Assume we go to state 3 from 3 we can get to 2,4,6. so we can come back to in same recursion. 2 -> 4 -> 3 -> 2.
Solving will contain state which have been visited but not solved completely.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x,y,z;
unordered_set<ll> solving;
unordered_map<ll, ll> solved;
ll func(ll i) {
if (i <= 0) {
return ll(1e12+7);
}
else if (i >= n) {
return z * (i-n);
}
else if (solving.find(i) != solving.end()) {
return ll(1e12+7);
}
else if (solved[i]) {
return solved[i];
}
else {
solving.insert(i);
ll a = x + func(i*2);
ll b = y + func(i+1);
ll c = z + func(i-1);
solving.erase(solving.find(i));
solved[i] = min(a, min(b,c));
return solved[i];
}
}
int main () {
cin>>n>>x>>y>>z;
cout<<func(1);
/* for (ll i = 1; i <= n ; i++)
cout<<solved[i]<<endl; */
return 0;
}