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

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


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

Pe o masa se afla N pahare de plastic, numerotate distinct de la 1 la N. Paharele pot fi puse unul in altul, astfel formandu-se turnuri de pahare.
Se da o secventa de mutari de forma a b, cu semnificatia "turnul care contine paharul a va fi pus peste turnul care contine paharul cu numarul b". Daca paharele a si b sunt in acelasi turn sau daca a=b atunci mutarea nu are nici un efect.
Mutarile trebuie sa fie executate in ordinea in care ele apar in secventa.
De exemplu, sa consideram ca avem 7 pahare, iar sirul de mutari este 1 3, 2 6, 3 6, 4 7 si 4 2. Configuratia paharelor de pe masa se schimba astfel:
Initial: (1) (2) (3) (4) (5) (6) (7) (fiecare pahar formeaza un turn separat).
Dupa mutarea 1 3: (1 3) (2) (4) (5) (6) (7)
Dupa mutarea 2 6: (1 3) (2 6) (4) (5) (7)
Dupa mutarea 3 6: (1 3 2 6) (4) (5) (7)
Dupa mutarea 4 7: (1 3 2 6) (4 7) (5)
Dupa mutarea 4 2: (1 3 2 6 4 7) (5)

Cerinta

Scrieti un program care sa determine mutarea 0, adica mutarea care ar trebui sa fie executata inaintea primei mutari din secventa, astfel incat numarul de pahare din cel mai inalt turn sa fie maxim.

Date de intrare

Fisierul de intrare turn1.in contine pe prima linie doua numere naturale N (numarul de pahare) si M (numarul de mutari), separate prin spatiu. Fiecare dintre urmatoarele M linii contine o mutare, data prin doua numere naturale a b, separate printr-un spatiu.

Date de iesire

Fisierul de iesire turn1.out va contine o singura linie pe care se afla mutarea 0, specificata ca o pereche de numere naturale a b, separate printr-un singur spatiu.

Restrictii

  • 2 <= N <= 10000
  • 0 <= M <= 100000
  • Solutia nu este in mod necesar unica.

Exemple

turn1.in turn1.out turn1.in turn1.out turn1.in turn1.out
5 3
1 2
5 3
4 1
4 5 6 4
5 2
3 3
1 3
6 2
3 5 10 9
3 7
5 9
10 10
9 5
8 7
3 7
6 1
4 2
2 6
7 2

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2003: newcomp, rima, algebra, aparitii, carti1, program1, tgraf, ceas1, spioni, kgb, tabara1, romane, stop, hanoi, lift, pic, sms, fibo, bac, parc, circular, logn, lex, joc7, cuburi1, sant, mobile, pattern, oras, produs, mutare, viteza, concurs2, furnici, homeless, subsir
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
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, 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
Software recomandat
surse trimise | ajutor