Fişierul intrare/ieşire:pawns.in, pawns.outSursăBursele Agora 2004
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Pawns

Se considera o tabla impartita in mai multe celule care contin pioni. Celulele sunt conectate intre ele prin sageti, si mergand de la orice celula in directia in care indica sagetile nu vom ajunge niciodata in locul din care am plecat. Deci, exista celule din care nu pleaca sageti si celule in care nu ajung sageti.
Consideram doi jucatori. Fiecare jucator poate muta, cand ii vine randul, un pion din celula in care se afla intr-o celula spre care pleaca o sageata. Cel care nu mai poate muta atunci cand ii vine randul pierde partida. La inceputul unui joc, prima mutare o face jucatorul 1.

Cerinta

Sa se determine daca jucatorul 1 are strategie sigura de castig.

Date de intrare

Fisierul de intrare pawns.in contine pe prima linie doua numere intregi n si m, separate printr-un singur spatiu, care reprezinta numarul de celule de pe tabla, respectiv numarul de sageti.
Pe fiecare dintre urmatoarele m linii se afla cate doua numere intregi x si y, separate intre ele printr-un singur spatiu, cu semnificatia ca exista o sageata care pleaca din celula cu numarul de ordine x si ajunge in celula cu numarul de ordine y.
Pe linia urmatoare se afla un numar t care reprezinta numarul de jocuri care se joaca.
Pe fiecare dintre urmatoarele t linii se afla n numere intregi, separate intre ele prin spatii, care reprezinta numarul de pioni din fiecare celula pentru un anumit joc.

Date de iesire

Fisierul de iesire pawns.out trebuie sa contina t linii. Fiecare dintre cele t linii va contine valoarea 0, daca pentru o configuratie jucatorul 1 nu are strategie sigura de castig si valoarea 1 in caz contrar.

Restrictii si precizari

  • 1 ≤ n, m ≤ 500
  • 1 ≤ t ≤ 15
  • Numarul de pioni dintr-o celula nu va depasi valoarea 500
  • Celulele sunt numerotate de la 1 la n

Exemplu

pawns.inpawns.out
3 3
1 2
1 3
2 3
2
1 0 0
2 2 2
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content