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

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

== include(page="template/taskfooter" task_id="joc5") ==

== SmfTopic(topic_id="...") ==

1843