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ă cel puţin o cameră conţine alţi pitici.
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 |
|---|---|
| 2 3 2 5 2 | 4 8 |
Explicaţie
Pentru primul test, sunt 3 pitici şi 2 camere. Cele patru posibilităţi sunt:
1. Camera 1 este ocupată de piticii 1 şi 3, iar camera 2 de piticul 2.
2. Camera 1 este ocupata de piticul 1, iar camera 2 de piticii 2 şi 3.
3. Camera 1 este ocupata de piticul 2 şi 3, iar camera 2 de piticul 1.
4. Camera 1 este ocupata de piticul 2, iar camera 2 de piticii 1 şi 3.
