In this task you would be given an integer N (less than 106), find the minimum way in which you could sum to N using only Fibonacci numbers - this partition is called Zeckendorf representation.
You could use any Fibonacci number more than once and if there is more than one representation output any.
For example if the input is 67 then one possible output could be using the Fibonacci numbers 1,3,8,55 which is also the minimum number of Fibonacci numbers that could be used to get the sum 67.
The input N is given on a single line, the inputs are terminated by EOF.
Given in the format
0: 0 47: 34+13 3788: 2584+987+144+55+13+5 1646: 1597+34+13+2 25347: 17711+6765+610+233+21+5+2 677: 610+55+8+3+1 343: 233+89+21 3434: 2584+610+233+5+2
- The number of inputs would not exceed 106 values.
- Your program should not run more than 5 seconds for all inputs.
- You can use any language of your choice.
- Shortest solution wins!