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:
Code is probably failing because of floating-point approximations.
The code is giving correct answer till the 52nd Fibonacci number (), but problems start arising after that.
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).
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.
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
), but problems start arising after that.
