Fişierul intrare/ieşire:divisibility.in, divisibility.outSursăShumen 2016 - Seniori
AutorDaniel AtanasovAdăugată deAndrei1998Constantinescu Andrei-Costin Andrei1998
Timp execuţie pe test2 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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  3i + 2 -a sunt numerele N, K, P, separate prin spatiu;
  • Pe linia a  3i + 3 -a este unul dintre simbolurile X, sau Y, indicand care dintre jucatori face prima mutare;
  • Pe linia a  3i + 4 -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.indivisibility.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?