Gigel a aflat din “sursa
sigura” ca orice numar natural se poate descompune ca suma de termeni neconsecutivi
ai sirului Fibonacci si ca o astfel de descompunere este unica.
Desi s-a chinuit cateva nopti bune sa demonstreze acest lucru el nu a ajuns
la nici o concluzie. Totusi un program care poate sa gaseasca descompunerea
unui numar dat i-ar fi de mare ajutor avand o mica sansa sa se prinda de modul
in care aceasta descompunere este construita uitandu-se pe cateva exemple.
Cerinta
Scrieti programul de care
Gigel are nevoie.
Date de intrare
Pe prima linie a fisierului
descfib.in se afla un numar natural N
de a carui descompunere este interesat Gigel.
Date de iesire
Fisierul descfib.out
contine pe prima linie un numar intreg K reprezentand numarul de termeni din descompunerea lui N. Pe urmatoarele K linii se afla cate un termen din descompunere, in ordine crescatoare.
Restrictii si precizari
1
<= N <= 10100
Pentru 40% din teste
N <= 1018
Pentru problema "descfib"
sirul Fibonacci se va considera definit in urmatorul mod:
F1 = 1, F2 = 2 si F(n+1)
= F(n) + F(n - 1) cu n > 1
(prin F(i)
se intelege al i-lea termen
al sirului).
In consecinta, primii
termeni ai sirului vor fi:
1, 2, 3, 5, 8, 13, 21, ...