Kboard

kboard

== include(page="template/taskheader" task_id="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':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.

Poveste si cerinta...

h2. 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.

...

h2. 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$.

...

h2. 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}$

* $... ≤ ... ≤ ...$

h2. Exemple

h2. Exemplu

table(example). |_. kboard.in |_. kboard.out |

|1 3
1
2
3
|1
2
1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

|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
|

 
h3. Explicatie
 
...

== include(page="template/taskfooter" task_id="kboard") ==

2376