FIBOREP - Fibonacci Representation

no tags 

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 upto 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 upto 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