Fişierul intrare/ieşire:fibsmen.in, fibsmen.outSursăInfoarena Monthly 2014, Runda 4
AutorAndrei Cristian LambruAdăugată demaritimCristian Lambru maritim
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fibsmen

Fiind dat un numar natural N sa se spuna in cate moduri se poate scrie ca suma de termeni distincti din sirul lui Fibonacci. Pentru fiecare mod posibil nu va conta ordinea in care se vor aduna termenii. Mai precis, doua moduri care contin exact aceeasi termeni nu se vor considera distincte si in consecinta se vor numara o singura data.

Sa se raspunda la Q astfel de intrebari .

Date de intrare

Fişierul de intrare fibsmen.in contine pe prima linie o singura valoare Q cu semnificatia de mai sus.
Pe fiecare din urmatoarele Q linii se afla un singur numar natural N care va reprezinta valoarea la care trebuie sa se raspunde pentru intrebarea respectiva 

Date de ieşire

În fişierul de ieşire fibsmen.out se vor afisa exact Q linii. Pe a i-a linie se va afla raspunsul pentru a i-a intrebare din fisierul de intrare.

Restricţii

  • 1 ≤ Q ≤ 200 000
  • 1 ≤ N ≤ 1016

Exemplu

fibsmen.infibsmen.out
3
6
73
666013
2
6
340

Explicaţie

Cele 2 moduri distincte in care se poate scrie numarul 6 sunt: 1+2+3 si 1+5.
Cele 6 moduri distincte in care se poate scrie numarul 73 sunt: 2+3+13+21+34, 2+3+5+8+21+34, 5+13+21+34, 2+3+13+55, 2+3+5+8+55 si 5+13+55.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content