PROBLEM LINK:
DIFFICULTY:
CAKEWALK
PROBLEM:
Given initial atoms in the lab (N), multiplication rate per second (K) and the maximum limit of atoms (M), print the time at which reaction should be stopped, such that atoms don’t exceed the M limit.
QUICK EXPLANATION:
Simple simulation. We have N, we keep on multiply it with K until it doesn’t cross M. Note that even if we have K=2, it will take only (log(M) to base 2) time to simulate. So simulating was the best method.
Worst case Complexity: log(M-N) to base K.
The issue most people faced:
Suppose we are using long long int for variables, consider this case N=K=10^11.
If we check (N*K > M) this will overflow since long long has maximum limit of around 10^18.
One way to handle this is to do:
if((double)cur*(double)k>(double)m)
since double has higher limits.
Another way:
while (n <= m / k)
See code for other details.
CODE:
#define sd(n) scanf("%d",&n)
int main()
{
int t;
sd(t);
while(t--)
{
LL n,k,m,cur,ans=0;
cin >> n >> k >> m;
cur=n;
while(1)
{
if((double)cur * (double)k>(double)m)break;
cur=cur * k;
ans++;
}
cout << ans << endl;
}
return 0;
}