FIBOREP - Fibonacci Representation
Zeckendorf's theorem states that every number can be written uniquely as the sum of distinct Fibonacci numbers, such that no 2 of the Fibonacci numbers are consecutive. Given N, print the Zeckendorf representation of N.
Given a number N, you have to print the Fibonacci numbers that sum up to N, as per the Zeckendorf's theorem.
Input:
The first line consists of an integer T, denoting the number of test cases that follow. Each of the next T lines consist of an integer N.
Output:
Your output should contain T lines. On each line, print the Fibonacci numbers that add up to the corresponding N (in increasing order), as per the Zeckendorf's theorem.
Constraints:
T <= 1000
1 <= N <= 100000000 (10^8)
Sample Input:
2
10
100
Sample Output:
2 8
3 8 89
hide comments
Michael T:
2010-10-22 00:46:58
Bad input formatting - trailing newlines / spaces (?). In python use stdin.read().split(). Last edit: 2010-10-22 00:57:05 |
Added by: | Varun Jalan |
Date: | 2010-09-06 |
Time limit: | 0.300s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC VB.NET |
Resource: | own problem |