Here is the problem statement
http://www.spoj.com/problems/ADV04L/
This problem is a little bit tricky. Let's have a look at constraints. There are 10000 test cases and every test case is less or equal to 10^15. The first thing we will have to do is generating all the Fibonacci numbers which are less or equal to 10^15. Be sure that that number won't exceed 80 so we generate the Fibonacci numbers and keep them. Now we need to find the right combination of Fibonacci numbers. The task says that the numbers must be as big as possible.Basically we need to complete this steps in order to get our answer.
1. Find the smallest Fibonacci number which is bigger than the given number.
2. Add the found number to our answer and subtract the previous Fibonacci number of the current Fibonacci number from our given number .
3. Go back to step 1 if our number is still greater than 0.
http://www.spoj.com/problems/ADV04L/
This problem is a little bit tricky. Let's have a look at constraints. There are 10000 test cases and every test case is less or equal to 10^15. The first thing we will have to do is generating all the Fibonacci numbers which are less or equal to 10^15. Be sure that that number won't exceed 80 so we generate the Fibonacci numbers and keep them. Now we need to find the right combination of Fibonacci numbers. The task says that the numbers must be as big as possible.Basically we need to complete this steps in order to get our answer.
1. Find the smallest Fibonacci number which is bigger than the given number.
2. Add the found number to our answer and subtract the previous Fibonacci number of the current Fibonacci number from our given number .
3. Go back to step 1 if our number is still greater than 0.
No comments:
Post a Comment