Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cabana.in, cabana.out | Sursă | ONIS 2014, Runda 1 |
| Autor | Teodor Plop | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | cabana.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
