| Fişierul intrare/ieşire: | fibsmen.in, fibsmen.out | Sursă | Infoarena Monthly 2014, Runda 4 |
| Autor | Andrei Cristian Lambru | Adăugată de |  Cristian Lambru •maritim |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | fibsmen.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.
