Hide
Problem G
Minimal Fibonacci Sums
Languages
en
sv
All positive integers can be written as a sum of Fibonacci numbers (for example, the trivial solution $1 + 1 + 1 + \dots + 1$). A harder problem is to write it as the sum of as few Fibonacci numbers as possible. For example, $7$ can be written as $2 + 5$, while $12$ requires three numbers: $1 + 3 + 8$. Your task is to write a program that finds this shortest representation.
Input
The input consists of a single integer between $1$ and $10^9$.
Output
Output a shortest sequence of Fibonacci numbers that sum to the input. You should output them in increasing order, separated by spaces. If there are several possible shortest sequences, any one will be accepted.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 |
2 5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
12 |
1 3 8 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 |
3 |
