Fișierul intrare/ieșire	fibo.in, fibo.out	Sursă	Olimpiada locala 2012, Clasa a 9-a
Autor	Florentina Mocrienco	Adăugată de	Ioana Bica • ioanab
Timp de execuție pe test	0.05 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Fibo

Rareș este colecționar de cochilii de melci și de scoici. A făcut o cerecetare referitoare la forma acestora, și a descoperit că o cochilie de Nautilus respectă spirala construită pe baza șirului lui Fibonacci.
Termenii șirulului Fibonacci se obțin astfel: primul termen este 0, al doilea termen este 1, iar fiecare dintre următorii termeni se obține ca sumă a celorlalți doi termeni care-l preced. Șirul rezultat este: 0, 1, 0+1=1, 1+1=2, 2+1=3, 3+2=5, 5+3=8, 8+5=13 , etc.
Reprezentând geometric șirul, alegem două termeni (13 și 8) si formăm un dreptunghi. În interiorul acestui dreptunghi, fiecare termen din șirul Fibonacci mai mic ca 13 formează latura unui pătrat. Dacă trasăm un fel de diagonală curbă pornind de la 1 spre 8 obținem o spirală care poate continua, după aceeași regulă, cu un patrat de 13, rezultând valoarea 21 (8+13=21).

Această descoperire l-a facut curios pe Rareș, care a dorit să afle mai multe despre propietățile misterioase ale acestui șir. Astfel, a aflat că orice număr natural se poate descompune ca o sumă de cel puțin doi termeni nenuli distincți ai șirului Fibonacci; de exemplu, 12=8+3+1; 8=3+5.

Cerinta

Scrieți un program care să citească un număr natural n și un șir x de n numere naturale x1,x2,...,xn, și care să determine descompunerea fiecărui număr din șirul citit ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.

Date de intrare

Fișierul fibo.in conține pe prima linie numărul natural n, iar următoarea linie conține cele n numere naturale x1,x2,...,xn, separate prin câte un spațiu.

Date de ieșire

Fișierul fibo.out va conține n linii, câte una pentru fiecare număr din șirul x:
− prima linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului x1 ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci;
− a doua linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului x2 ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.
...............
− a n-a linie va conține, în ordinea descrescătoare a valorilor, separate prin câte un spațiu, numerele naturale din descompunerea numărului xn ca o sumă de un număr minim (cel puțin doi) de termeni nenuli distincți ai șirului Fibonacci.

Restricții

• 1≤ n ≤ 100; n număr natural
• 3≤ x1, x2,..., xn ≤ 2 000 000; x1,x2,...,xn sunt numere naturale

Exemplu

Explicație

38=34+3+1
8=5+3
20=13+5+2
141=89+34+13+5
8=5+3
61=55+5+1