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

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


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

Se consideră un arbore oarecare având N noduri, numerotate de la 1 la N. Nodurile arborelui se împart în două categorii: active şi inactive. Iniţial toate nodurile sunt inactive. În acest arbore, deplasarea de la nodul i la nodul j este posibilă doar dacă sunt îndeplinite simultan următoarele condiţii:
- nodul j este ascendent sau descendent direct al lui i (tată sau fiu);
- nodul j este inactiv;
După atingerea nodului j, va fi selectat unul dintre fiii inactivi ai săi (dacă există) şi va fi activat, împreună cu subarborele care îl are pe acest fiu drept rădăcină.
Orice drum în acest arbore are ca nod de plecare o frunză (nod terminal în arbore). Definim lungimea unui drum, parcurs în condiţiile de mai sus, ca fiind numărul de deplasări efectuate.

Cerinţă

Scrieţi un program care determină drumul de lungime maximă ce porneşte de la un nod terminal dat. Programul va afişa pentru fiecare nod de pe drum, nodul fiu ce a fost activat.

Date de intrare

Fişierul de intrare activ.in conţine pe prima linie numărul natural N. Următoarele N-1 linii conţin perechi de numere (i,j) cu semnificaţia ″nodul i este fiu al nodului j″. Ultima linie a fişierului de intrare conţine nodul de plecare.

Date de ieşire

Fişierul de ieşire activ.out va conţine pe prima linie numărul natural L reprezentând lungimea drumului maxim. Pe a doua linie se vor scrie L numere naturale, despărţite prin câte un spaţiu, reprezentând nodurile drumului, în ordinea în care acestea au fost traversate, exceptând nodul de plecare. Pe a treia linie, pentru fiecare nod din drumul afişat pe linia anterioară, se va scrie fiul său ales pentru activare. Dacă nodul respectiv nu are fii inactivi se va scrie cifra 0.

Restricţii

1 ≤ N ≤ 100 000

Exemple

activ.inactiv.out
6 2 1 3 1 4 2 5 2 6 3 4 6 2 5 2 1 3 1 4 0 5 2 6 3

autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Finala .campion 2010: expo, mine, popic, arctir, guess, orientare, secvbiti
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, swap, tetris3, monede2, ssk
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, 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, 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 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, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
surse trimise | ajutor