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

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


Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Nargy si Fumeanu joaca un joc pe un graf orientat fara circuite cu N noduri (numerotate de la 1 la N) si M arce. In acest graf exista K pioni plasati in noduri. Fiecare jucator trebuie sa mute, cand ii vine randul, toti pionii care se pot muta din nodurile in care se afla in noduri adiacente. Mai exact, un pion situat in nodul x poate fi mutat in nodul y, daca exista arc de la x la y.
Cel care nu mai poate muta nici un pion atunci cand ii vine randul pierde partida. La inceputul unui joc, prima mutare o face jucatorul Nargy.


Cerinta

Dandu-se mai multe configuratii de pioni, sa se determine cine castiga jocul, daca ambii jucatori joaca optim. 

Date de intrare

Fisierul de intrare pioni.in contine pe prima linie 3 numere naturale T N M. Urmatoarele M linii vor contine cate doua numere naturale a b cu semnificatia ca exista arc de la a la b. Urmatoarele T linii vor descrie configuratii de pioni astfel: primul numar de pe linie va fi K si va fi urmat de K numere naturale reprezentand nodurile in care se afla pioni. Numerele de pe aceeasi linie sunt separate prin spatii.

Date de iesire

Fisierul de iesire pioni.out va contine T linii, cate o linie pentru fiecare configuratie de pioni din fisierul de intrare. Pe linia i se va scrie numele jucatorului care castiga (Nargy sau Fumeanu) pentru a i-a configuratie de pioni din fisierul de intrare.

Restrictii

1 <= T <= 5
1 <= N <= 20 000
1 <= M <= 50 000
1 <= K <= 30 000

Pot exista mai multi pioni in acelasi nod.

Exemple

pioni.in

pioni.out

Explicatie

2 4 3
2 1
3 1
4 3
3 2 2 3
2 1 4

Nargy
Fumeanu

1. Conform regulilor jocului Nargy trebuie sa mute cu toti cei 3 pioni, iar singura posibilitate este sa-i mute pe toti in 1. Fumeanu nu mai poate muta.

2. Nargy muta pionul din 4 in 3, iar Fumeanu muta din 3 in 1. Acestea sunt singurele mutari posibile.

Mircea Paşoi
Universitatea Bucuresti,Facultatea de Matematica si Informatica
mircea@infoarena.ro

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, copaci, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, hd, pajura, pc, sir, cadere
De acelaşi autor: copaci, ab2, plimbare, cuvinte, reinvent, numere3, perm, criptare, sume, gramezi, nr2, rev, paintball, matricea, emax, turism, puncte1, casute, dep
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, 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, joc6, 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, vector, joc6, gramezi1, cutii, joc13, color, jocv, graphgame, joct, lipsa, neconex, cutie1
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor