Well hello guys! Below is the link to my source code for the above problem. http://codeforces.me/contest/614/submission/15376824 I am getting a WRONG_ANSWER on test case 3 after my submission on CodeForces but when I compiled and executed the testcase on my g++ compiler it gave the right answer.Can anyone please tell me why is this happening?!.Below is a screenshot of the answer that I got for testcase 3 after compiling on g++. (http://codeforces.me/predownloaded/4d/2c/4d2c56826166cb8597ec2f5249162eb3266b58b4.png)
You shouldn't use the function pow, its return type is double. For example it may return 2.99999999 and when you cast it to int it becomes 2, while the answer actually should be 3
Thanks a lot!
try adding 0.5 to your answer before casting it to int, that might work ;)
Did not work for other testcases.Anyways thanks!
Check my next reply ;)
By the way your code has an overflow bug. The problem limits are up to 10^18. First, its wrong to cast the answer to int, it should be to unsigned long long. Second, the condition on the for loop will make an overflow with large test cases.
I modified my code as you had said earlier but experienced the same problem again in test case 31 wherein my g++ output differed from that submitted to codeforces. http://codeforces.me/contest/614/submission/15377789 (http://codeforces.me/06a211/Screenshot from 2016-01-15 02:44:58.png)
pow(k,i)<=r this condition is not totally correct. in large test cases you will get overflow. For example in this test case : 1 10^18 10^9 the for loop will go like : 1 10^9 10^18 and then it will try 10^26 which should break your for loop. What really happens is that 10^26 is greater than the upper limit of unsigned long long. Unsigned long long can hold a number up to 10^19 as maximum. Thus, it makes an overflow which means that pow(k,i) returns a random number.
Try adding the following code at the bottom of your for loop :
if((ll)(pow(k,i)+0.5) * k / k != (ll)(pow(k,i)+0.5)) break;That didn't work.Thanks for the help!I will try to figure this out.
Ah your problem is that you forgat to add 0.5 to pow(k,i) at your for loop condition :D
for(i=0;(ull)(pow(k,i)+0.5)<=r;i++)In some cases, you have an overflow because the resulting value of k is greater than the upper limit of unsigned long long.
.