Problem link: CodeChef: Practical coding for everyone.
In problem Digits & Magic, we need to calculate, how many digits have number A^B in number system with base i for 2 \le i \le 20.
Obvious solution:
-
If a=0, then all answers are 0;
-
If a>0, then ans_i = \lfloor1+\log_i A^B\rfloor = \lfloor1+B\log_i A\rfloor = \left\lfloor1+B\cdot\dfrac{\ln A}{\ln i}\right\rfloor.
But in the second part, there is precision error: computer can’t store all infinite number of digits, so float numbers can be a bit incorrect. And I’ll prove that all accepted solutions and author’s solution are wrong.
For example, let A=1000, i=10. Then A^B = 1000^B = 10^{3B}. This number in decimal system is “one and 3B zeros”, so it is 3B+1 digits. Really, ans_i = \lfloor1+B\log_i A\rfloor = \lfloor1+B\log_{10}1000\rfloor = \lfloor1+3B\rfloor = 3B+1.
I wrote this solution: CodeChef: Practical coding for everyone. It uses such approach and gets AC:
if(a==0)
{
for(int i=2;i<=20;i++)
cout<<1<<" ";
}
else
{
for(int i=2;i<=20;i++)
cout<<int(1+b*(log(a)/log(i)))<<" ";
}
Then I added that for A=1000 and i=10, answer is 3B+1: CodeChef: Practical coding for everyone. This solution must be AC too, but it gets WA:
if(a==0)
{
for(int i=2;i<=20;i++)
cout<<1<<" ";
}
else
{
for(int i=2;i<=20;i++)
if(a==1000&&i==10)
cout<<3*b+1<<" ";
else
cout<<int(1+b*(log(a)/log(i)))<<" ";
}
And then I replaced 3B+1 with 3B: CodeChef: Practical coding for everyone.
This solution must get WA, but it gets AC:
if(a==0)
{
for(int i=2;i<=20;i++)
cout<<1<<" ";
}
else
{
for(int i=2;i<=20;i++)
if(a==1000&&i==10)
cout<<3*b<<" ";
else
cout<<int(1+b*(log(a)/log(i)))<<" ";
}
If I am not mistaken, all accepted solutions and author’s solution are wrong. Does anyone know correct solution?
UPD. You can run my code with some values of B and see that it outputs 3B. For example: Ry3ijc - Online C++0x Compiler & Debugging Tool - Ideone.com (B=100000).