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


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

hide comments
2010-10-22 00:46:58 Michael T
Bad input formatting - trailing newlines / spaces (?). In python use stdin.read().split().

Last edit: 2010-10-22 00:57:05
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.