Fişierul intrare/ieşire: | divisibility.in, divisibility.out | Sursă | Shumen 2016 - Seniori |
Autor | Daniel Atanasov | Adăugată de | Andrei Constantinescu •Andrei1998 |
Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Divisibility
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 = {a1, a2, ..., aN}, astfel incat fiecare ai 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.
Date de intrare
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 -a sunt numerele N, K, P, separate prin spatiu;
- Pe linia a -a este unul dintre simbolurile X, sau Y, indicand care dintre jucatori face prima mutare;
- Pe linia a -a sunt numerele a1, a2, ..., aN, separate prin spatiu.
Date de ieşire
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.
Restricţii
- 1 ≤ K ≤ N ≤ 5000
- 1 ≤ P ≤ 1018
- 0 ≤ ai < P pentru fiecare 0 ≤ i < N si ai ≠ aj pentru fiecare 0 ≤ i < j < N.
- Pentru 20% din teste N ≤ 25.
- In alte 20% din teste P este un numar prim.
Exemplu
divisibility.in | divisibility.out |
---|---|
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 |