Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | melodii.in, melodii.out | Sursă | FMI No Stress 4 |
| Autor | Andrei Cristian Lambru | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Melodii
Gigel a fost invitat la aniversarea prietenei lui dragi, Alinuta, pe post de DJ. Principala lui problema este ca nu cunoaste decat 2 melodii. Prima melodie dureaza fix 1 minut, iar a doua fix 2 minute, dar el a fost chemat pentru exact N minute de reprezentatii.
Deoarece Gigel este student la FMI si nu la Conservator nu il deranjeaza acest lucru, in plus vrea sa stie pentru un N dat care este numarul de moduri de a dispune cele 2 melodii astfel incat sa dureze fix N minute. Mai exact pentru N = 3, el are 3 posibilitati de dispunere a melodiilor : {1, 2} , {2, 1}, {1, 1, 1}.
Dupa ce a calculat pentru N <= 100 (cu backtracking) si-a dat seama ca acest numar este destul de mare, asa ca doreste sa afle doar restul impartirii acestui numar la R, numarul lui norocos. In plus el doreste raspunsul la aceasta intrebare pentru T valori diferite ale lui N.
Date de intrare
Pe prima linie din fişierul de intrare melodii.in se vor gasi valorile T si R. Pe urmatoarele T linii se va afla exact o singura valoarea ce va semnifica numarul N de minute pentru testul respectiv.
Date de ieşire
În fişierul de ieşire melodii.out se vor afla exact T linii, raspunsul la cele T intrebari in ordinea in care se gasesc in fisierul de intrare.
Restricţii
- 1 ≤ T, R ≤ 100 000
- $1 ≤ N ≤ 10^18
- Pentru 50% din teste, 1 ≤ N ≤ 1 000 000
Exemplu
| melodii.in | melodii.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
