Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-12-08 14:17:12.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cabana.in, cabana.outSursăONIS 2014, Runda 1
AutorTeodor PlopAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.35 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cabana

În pădurea cu alune, aveau o cabană N pitici. În cabană sunt exact K camere în care se poate dormi. Cum somnul nu este deloc de neglijat în lumea piticilor, aceştia se joacă înainte de culcare astfel: Piticii intră pe rând în cabană, începând cu piticul 1, până la piticul N, şi se duc în camera în care vor dormi. Un pitic îşi alege camera în care va dormi în felul următor:

  • Se duce în camera care a fost aleasă de cât mai puţini pitici.
  • Dacă sunt mai multe camere cu această proprietate, piticul va alege oricare dintre acestea.

Când ajunge Albă ca Zăpada în cabană, aceasta se întreabă:

  • Oare în câte moduri poate fi ocupată cabana de cei N pitici?

Două moduri de ocupare a cabanei sunt considerate distincte dacă există cel puţin un pitic care să se afle într-o cameră distinctă.

Date de intrare

Fişierul de intrare cabana.in conţine pe prima linie un număr natural T, reprezentând numărul de teste. Pe urmatoarele T linii, se vor găsi două numere N şi K, având semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire cabana.out se vor găsi T linii, pe fiecare linie i găsindu-se răspunsul la întrebarea i.

Restricţii

  • 1 ≤ T ≤ 1.000
  • 1 ≤ N ≤ 1018
  • 1 ≤ K ≤ 1.000.000

Exemplu

cabana.incabana.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?