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

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


Timp maxim de execuţie/test:
0.3 secunde
Memorie totala disponibilă/stivă:
16 MB/1 MB

Ana şi Bogdan joacă din nou un joc interesant. Ana desenează pe o foaie de hârtie un arbore (graf neorientat conex şi aciclic) cu N vârfuri numerotate de la 1 la N. Apoi elimină vârfurile arborelui în modul următor: determină frunza (vârf cu gradul 1) cu numărul cel mai mic, o elimină din arbore şi scrie pe o altă foaie de hârtie numărul vârfului conectat direct cu frunza eliminată.
Procedeul de eliminare continuă până când în arbore rămâne un singur vârf, iar pe foaie s-a obţinut o listă cu N-1 vârfuri.
Bogdan primeşte foaia de hârtie cu lista vârfurilor scrise de Ana pe parcursul eliminării şi trebuie să reconstituie arborele.

Cerinţă

Dată fiind lista vârfurilor scrise de Ana, scrieţi un program care să reconstituie arborele.

Date de intrare

Fişierul de intrare lista.in conţine pe prima linie un număr natural N care reprezintă numărul de vârfuri din arbore. Pe cea de a doua linie sunt scrise N-1 numere naturale separate prin câte un spaţiu reprezentând lista vârfurilor scrise de Ana.

Date de ieşire

Fişierul de ieşire lista.out va conţine N-1 linii, fiecare linie conţinând o muchie specificată prin cele două extremităţi ale sale, separate prin spaţiu. Muchiile pot fi afişate în orice ordine.

Restricţii

  • 2 <= N <= 100 000

Exemple

lista.in lista.out
10
6 2 7 9 2 9 4 4 10
1 6
3 2
5 7
6 9
7 2
2 9
8 4
9 4
4 10
prof. Emanuela Cerchez
Colegiul Naţional "Emil Racoviţă" Iaşi
emanuela.cerchez@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, operatii1, codarb, codpatrat, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala, 2ndesc
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, turn1, 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, 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 arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
Software recomandat
surse trimise | ajutor