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.
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.
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.
T <= 1000
1 <= N <= 100000000 (10^8)
Sample Input:
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

Last edit: 2010-10-22 00:57:05

Added by:Varun Jalan
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC VB.NET
Resource:own problem