Fişierul intrare/ieşire:fibo.in, fibo.outSursăOlimpiada locala 2012, Clasa a 9-a
AutorFlorentina MocriencoAdăugată deioanabIoana Bica ioanab
Timp execuţie pe test0.05 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 este număr natural
  • 3 ≤ x1, x2,..., xn ≤ 2 000 000; x1, x2, ..., xn sunt numere naturale

Exemplu

fibo.infibo.out
6
38 8 20 141 8 61
34 3 1
5 3
13 5 2
89 34 13 5
5 3
55 5 1

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici