Fişierul intrare/ieşire:kboard.in, kboard.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inkboard.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content