Hide
Problem G
Minimala Fibonaccisummor
Languages
en
sv
Alla positiva heltal kan skrivas som en summa av fibonaccital (t.ex. den triviala lösningen 1+1+1+...+1). Ett svårare problem är att skriva heltalet med så få fibonaccital som möjligt. T.ex. skrivs talet 7 med minsta antal fibonaccital som 2+5, medan 12 skrivs som 8+3+1. Din uppgift är att skriva ett program som gör precis detta!
Indata
Den första raden består av ett heltal mellan $1$ och $10^9$.
Utdata
Skriv ut en så kort sekvens som möjligt av fibonaccital som sumerar till talet i indatan. Du ska skriva ut dom i stigande ordning, åtskiljda av blanksteg. Om det finns flera kortaste sekvenser så kan du skriva ut vilken som helst.
| 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 |
