== include(page="template/taskheader" task_id="fibo") ==
Poveste și cerință...
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$.
h2. 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.
h2. Date de intrare
Fișierul de intrare $fibo.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $fibo.out$ ...
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.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 100; n este număr natural$
* $3 ≤ x1, x2,..., xn ≤ 2 000 000; x1, x2, ..., xn sunt numere naturale$
h2. Exemplu
table(example).
|_. fibo.in |_. fibo.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
38 8 20 141 8 61
| 34 3 1
5 3
13 5 2
89 34 13 5
5 3
55 5 1
|
h3. 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
== include(page="template/taskfooter" task_id="fibo") ==
== include(page="template/taskfooter" task_id="fibo") ==
