| Fişierul intrare/ieşire: | kboard.in, kboard.out | Sursă | Happy Coding 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kboard
Gigel si Ionel au inceput sa joace un joc nou, dupa ce s-au plictisit de jocul de la Happy Coding-ul de anul trecut ( vezi problema obj ). De data aceasta, ei au la dispozitie o tabla de joc liniara formata din N patratele numerotate de la 1 la N, de la stanga la dreapta. Initial, toate cele N patratele sunt libere. Cei doi efectueaza alternativ mutari de tipul urmator: jucatorul aflat la mutare trebuie sa amplaseze o piesa avand dimensiunea 1xK peste K patratele consecutive libere de pe tabla; in urma amplasarii piesei, cele K patratele devin ocupate. Castigatorul jocului este cel care efectueaza ultima mutare (echivalent, pierzatorul este jucatorul care, atunci cand ii vine randul, nu mai poate efectua nici o mutare).
Pentru mai multe perechi (K,N) date, determinati cine castiga jocul (primul jucator, adica cel care efectueaza prima mutare, sau cel de-al doilea), considerand ca ambii jucatori vor folosi o strategie optima.
Date de intrare
Pe prima linie a fisierului kboard.in se afla numerele intregi K si T, separate printr-un spatiu. K reprezinta dimensiunea piesei, iar T reprezinta numarul de table de joc ce vor fi date in continuare. Fiecare din urmatoarele T linii va contine un numar intreg N, reprezentand numarul de patratele ale tablei de joc.
Date de iesire
In fisierul de iesire kboard.out veti afisa T linii. Pe a i-a dintre aceste linii veti afisa castigatorul jocului pe o tabla de joc avand numarul de patratele N dat in al i-lea test din fisierul de intrare si dimensiunea pieselor K data pe prima linie a fisierului de intrare. In cazul in care castigatorul jocului este primul jucator, afisati 1. In caz contrar, afisati 2.
Restrictii
- 1 ≤ K ≤ 10 000 000
- 1 ≤ T ≤ 100 000
- Daca K ≤ 2, atunci 1 ≤ N ≤ 1 000 000 000
- Daca K > 2, atunci 1 ≤ N ≤ max{3000, 69*K-19}
Exemple
| kboard.in | kboard.out |
|---|---|
| 1 3 1 2 3 | 1 2 1 |
| 2 4 1 2 5 6 | 2 1 2 1 |
| 3 4 999 998 100 256 | 1 1 2 1 |
| 9999999 20 89999988 289999962 129999982 16124217 299106936 60546243 524323847 649999916 449756549 64633851 209999972 368724199 152731683 89999988 77390991 649999916 25493701 289999962 225376567 223888509 | 2 2 2 1 1 1 1 2 1 1 2 1 1 2 1 2 1 2 1 1 |
