don't get logic to dis spoj problem


here is d link of spoj problm
I don’t know how to solve it and how to deal with large FIBNACCI numbers
Help Plz

Thank You

Use Greedy Approach. Store Fibonacci numbers till 10^15. For each N start from largest fibonacci number (say F) smaller than or equal to N. So now you have to make (N - F) from the rest Fibonacci numbers so update N to (N - F). And each time you encounter such a Fibonacci number F, you have to add the Fib number next to F.

Just got AC. However I didn’t liked the time limit. Same algorithm that failed in python, passed easily C++. Approach is same as @anuraganand.

//