Solving ADMAG using formula for index of a fibonacci number

I am trying to solve Aditi and Magic Tricks (ADMAG) question of August Long Challenge 2015 using the following formula :

Here F is the input no. and n gives the index of that Fibonacci number. I have tried many solutions so far but all in vain. My submissions are this, this, this and this. As you can see, all the codes fail in the last task of each subtask. Now, I am wondering whether this question can be solved using this formula and if the answer is yes then how?

My observations:

  1. Code is probably failing because of floating-point approximations.
  2. The code is giving correct answer till the 52nd Fibonacci number (53316291173), but problems start arising after that.

Your problem code is GRGUY but the actual problem is aditi and magic trick bro… :slight_smile:

Yes, I noticed it right now. Sorry for that. I have corrected it.

I dont think that it’s the right approach to use floating point in this case.
Maybe your solution in C++ will pass if you increase the precision of the constants to more digits (the precision for long double might be enough). I dont know of an easy way for increasing precision in python.

A better approach would be to corredt your solution in C++ using the precomputed fibonacci numbers:

Currently you accept the result from this approach only if n is exactly a fibonacci number. Also accept it in other cases (with the next highest number).

1 Like

I have tried by increasing precision in python, but doing that had no effect on the answer where my code was giving wrong answer. And my correct submission makes use of precomputed fibonacci numbers. It’s just that I am curious whether the solution will get accepted using this method.

https://www.codechef.com/viewsolution/7672856
I am also facing the same issue. just want to know, where is it faling.

The answer for 99194853094755497 should be 82, your code is giving 81.

at large values log gives different ans. so make a fibbonacci of your own by a loop or store it anywhere…

can anyone tell me about this formula? and about the ADMAG i didn’t use this formula i simply did binary search with some extra conditions and i got AC. here is my sol https://www.codechef.com/viewsolution/7777497