Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-11-06 14:27:58.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:melodii.in, melodii.outSursăFMI No Stress 4
AutorAndrei Cristian LambruAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 dureaza 1 minut, iar a doua 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 este curios sa stie pentru un N dat care este numarul de moduri de a dispune cele 2 melodii astfel incat reprezentatia sa dureze exact N minute. De exemplu 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 ≤ 1018
  • Pentru 50% din teste, 1 ≤ N ≤ 1 000 000

Exemplu

melodii.inmelodii.out
5 5
1
2
3
10
666013
1
2
3
10
x

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?