Fişierul intrare/ieşire:joc5.in, joc5.outSursăONI 2007, clasele 11-12
AutorTiberiu-Lucian FloreaAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.05 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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 Ai,j reprezinta costul minim pentru a ajunge din intersectia i in intersectia j (Ai,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

joc5.injoc5.out
2
8 25
25 9
2
3 8
9 3
0
1
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content