== include(page="template/taskheader" task_id="divisibility") ==
Poveste şi cerinţă...
Doi jucatori $X$ si $Y$, joaca urmatorul joc:
* Jucatorilor li se da un numar intreg pozitiv $P$ si un set $A$ format din $N$ numere nenegative, intregi, distincte $A = {a{~1~}, a{~2~}, ..., a{~N~}}$, astfel incat fiecare $a{~i~}$ este mai mic decat $P$.
* Jucatorii muta alternativ. Fiecare jucator la mutarea sa elimina un numar din setul $A$.
* Daca dupa exact $K$ mutari, suma numerelor ramase in $A$ este divizibila cu $P$ - invinge jucatorul $X$. In caz contrar - invinge jucatorul $Y$.
Sa se determine cine invinge in cazul in care ambii jucatori joaca optim.
h2. Date de intrare
Fişierul de intrare $divisibility.in$ ...
Pe prima linie a fişierului de intrare $divisibility.in$ se afla un numar intreg, pozitiv, $T$ - numarul de jocuri din testul curent.
Dupa aceasta, pentru fiecare $i = 0, 1, ..., T - 1$:
* Pe linia a <tex> 3i + 2 </tex>-a sunt numerele $N$, $K$, $P$, separate prin spatiu;
* Pe linia a <tex> 3i + 3 </tex>-a este unul dintre simbolurile $X$, sau $Y$, indicand care dintre jucatori face prima mutare;
* Pe linia a <tex> 3i + 4 </tex>-a sunt numerele $a{~1~}, a{~2~}, ..., a{~N~}$, separate prin spatiu.
h2. Date de ieşire
În fişierul de ieşire $divisibility.out$ ...
Pe prima linie a fişierului de ieşire $divisibility.out$ se vor afla $T$ simboluri (fara separatori), un simbol pentru fiecare joc din test. Al $i$-lea simbol va fi $X$, daca $X$ a invins in jocul al $i$-lea, indiferent cum ar fi jucat $Y$; in caz contrar simbolul trebuie sa fie Y.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ K ≤ N ≤ 5000$
* $1 ≤ P ≤ 10^18^$
* $0 ≤ a{~i~} < P$ pentru fiecare $0 ≤ i < N$ si $a{~i~} ≠ a{~j~}$ pentru fiecare $0 ≤ i < j < N$.
* Pentru $20$% din teste $N ≤ 25$.
* In alte $20$% din teste $P$ este un numar prim.
h2. Exemplu
table(example). |_. divisibility.in |_. divisibility.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 3
5 3 7
X
1 2 3 4 6
8 4 13
Y
5 10 6 11 2 8 9 3
6 1 12
X
1 4 5 7 9 11
| XYX
|
== include(page="template/taskfooter" task_id="divisibility") ==
