Fişierul intrare/ieşire:	joc5.in, joc5.out	Sursă	ONI 2007, clasele 11-12
Autor	Tiberiu-Lucian Florea	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.05 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Joc5

Gica si Petrica locuiesc in Orasul Vesel. Acolo exista o retea stradala care contine doar strazi cu sens unic iar pentru a te deplasa intre doua intersectii trebuie sa platesti o taxa specifica fiecarei intersectii si fiecarei strazi prin care treci (inclusiv intersectia din care pleci si intersectia in care ajungi). Aceste taxe nu deranjeaza insa pe nimeni, deoarece sunt valori monetare naturale intre 0 si 10. Pe cei doi nu ii intereseaza harta propriu-zisa a Orasului, insa au gasit tabelul sumelor minime pe care trebuie sa le plateasca pentru a se plimba intre oricare doua intersectii si s-au gandit sa-l foloseasca pentru a juca un joc interesant (Aceasta matrice contine numai valori finite).

Astfel, avand matricea A in care A_i,j reprezinta costul minim pentru a ajunge din intersectia i in intersectia j (A_i,i este taxa care trebuie platita in nodul i), fiecare dintre cei doi muta alternativ, dupa cum urmeaza: jucatorul aflat la mutare isi alege un numar natural strict pozitiv k, si scade k din toate elementele unei linii sau coloane ale matricei, cu conditia ca toate elementele matricei sa ramana nenegative. Gica muta primul, iar jucatorul care, atunci cand ii vine randul, nu mai poate efectua o mutare corecta, pierde. Se considera ca cei doi prieteni joaca perfect, insemnand ca daca unul dintre ei are la un moment dat o strategie de castig indiferent de mutarile adversarului, nu va efectua o mutare care sa duca la pierderea oricarei strategii de castig.

Cerinta

Dandu-se matricea A cu semnificatia din enunt, aflati care dintre cei doi este castigatorul jocului.

Date de intrare

Fisierul joc5.in contine intre 1 si 20 de seturi de date de intrare. Pe prima linie a fiecarui set se afla un numar natural pozitiv N reprezentand dimensiunile matricei A, iar pe urmatoarele N linii se afla cate N numere naturale, reprezentand elementele matricei A. N = 0 marcheaza sfarsitul seturilor de date ce compun fisierul de intrare.

Date de iesire

Fisierul de iesire joc5.out va contine un numar de linii egal cu numarul de seturi de date. Pe fiecare dintre aceste linii se afla una dintre valorile: 1 in cazul in care jocul respectiv este castigat de Gica, 2 in cazul in care jocul respectiv este castigat de Petrica.

Restrictii

• 1 ≤ numarul testelor ≤ 20
• 2 ≤ N ≤ 100
• Rezolvarea corecta a testelor ce contin cel mult 10 seturi de date cu N ≤ 5 garanteaza obtinerea a 50% din punctaj.

Exemplu

Cum se trimit solutii?