== include(page="template/taskheader" task_id="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).
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.
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.
h2. Cerinta
Dandu-se matricea A cu semnificatia din enunt, aflati care dintre cei doi este castigatorul jocului.
Dandu-se matricea $A$ cu semnificatia din enunt, aflati care dintre cei doi este castigatorul jocului.
h2. 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.
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.
h2. 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.
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.
h2. Restrictii
