.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » joc6

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
joc6


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
32MB / 1MB

Gică şi Petrică locuiesc în Oraşul Vesel. Acolo există o reţea stradală care conţine doar străzi cu sens unic iar pentru a te deplasa între două intersecţii trebuie să plăteşti o taxă specifică fiecărei intersecţii şi fiecărei străzi prin care treci (inclusiv intersecţia din care pleci şi intersecţia în care ajungi). Aceste taxe nu deranjează însă pe nimeni, deoarece sunt valori monetare naturale între 0 şi 10. Pe cei doi nu îi interesează harta propriu-zisă a Oraşului, însă au găsit tabelul sumelor minime pe care trebuie să le plătească pentru a se plimba între oricare două intersecţii şi s-au gândit să-l folosească pentru a juca un joc interesant (Această matrice conţine numai valori finite).
Astfel, având matricea A în care A[i, j] reprezintă costul minim pentru a ajunge din intersecţia i în intersecţia j (A[i, i] este taxa care trebuie plătită în nodul i), fiecare dintre cei doi mută alternativ, după cum urmează: jucătorul aflat la mutare îşi alege un număr natural strict pozitiv k, şi scade k din toate elementele unei linii sau coloane ale matricei, cu condiţia ca toate elementele matricei să rămână nenegative. Gică mută primul, iar jucătorul care, atunci când îi vine rândul, nu mai poate efectua o mutare corectă, pierde. Se consideră că cei doi prieteni joacă perfect, însemnând că dacă unul dintre ei are la un moment dat o strategie de câştig indiferent de mutările adversarului, nu va efectua o mutare care să ducă la pierderea oricărei strategii de câştig.

Cerinţă

Dându-se matricea A cu semnificaţia din enunţ, aflaţi care dintre cei doi este câştigătorul jocului.

Date de intrare

Fişierul de intrare joc6.in conţine între 1 şi 20 de seturi de date de intrare. Pe prima linie a fiecărui set se află un număr natural pozitiv N reprezentând dimensiunile matricei A, iar pe următoarele N linii se află câte N numere naturale, reprezentând elementele matricei A. N = 0 marchează sfârşitul seturilor de date ce compun fişierul de intrare.

Date de ieşire

Fişierul de ieşire joc6.out va conţine un număr de linii egal cu numărul de seturi de date. Pe fiecare dintre aceste linii se află una dintre valorile: 1 în cazul în care jocul respectiv este câştigat de Gică, 2 în cazul în care jocul respectiv este câştigat de Petrică.

Restricţii

1 ≤ numărul testelor ≤ 20
2 ≤ N ≤ 100
Rezolvarea corectă a testelor ce conţin cel mult 10 seturi de date cu N ≤ 5 garantează obţinerea a 50% din punctaj

Exemple

joc6.injoc6.out
2 8 25 25 9 2 3 8 9 3 0 1 2

autor: Tiberiu Lucian Florea
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, turn, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, triunghi, apel, castel, excursia, matricea, randuri, zidar, desc, felinar, log, maxq, tric, cover, dist, munte1, promo, puncte1, role
De acelaşi autor: soldati, vector, infinit, felinar
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre joc: connect3, cartonase, pioni, vector, gramezi1, cutii, joc13, color, jocv, graphgame, joct, lipsa, neconex, cutie1
surse trimise | ajutor