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

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


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

Sa presupunem ca dorim sa desenam un arbore binar pe o foaie de matematica (in care am numerotat liniile de sus in jos si coloanele de la stânga la dreapta). Desenul trebuie sa respecte urmatoarele reguli:
1. Nodurile situate pe acelasi nivel trebuie sa fie desenate pe aceeasi linie. Nivelul radacinii arborelui este 1 si radacina va fi desenata pe linia 1. Fii radacinii constituie nivelul 2 si vor fi desenati pe linia 2. Fiii fiilor radacinii constituie nivelul 3 si vor fi desenati pe linia 3 etc.
2. Pe fiecare coloana poate fi desenat un singur nod.
3. Nodurile din subarborele stâng al unui nod trebuie sa fie desenate în coloanele din stânga coloanei in care este desenat nodul respectiv, iar nodurile din subarborele drept trebuie sa fie desenate în coloanele din dreapta coloanei în care este desenat nodul respectiv.
4.Orice coloana cuprinsa intre coloana cea mai din stânga în care este desenat un nod si coloana cea mai din dreapta în care este desenat un nod trebuie sa contina un nod.

Sa notam cu L cea mai din stanga coloana in care este desenat un nod si cu R cea mai din dreapta coloana in care este desenat un nod. Latimea arborelui binar este R-L+1.

De exemplu:

Observati ca latimea acestui arbore binar este 19.
Putem calcula latimea pe fiecare nivel ca fiind diferenta dintre numarul celei mai din dreapta coloane care contine un nod de pe nivelul respectiv si numarul celei mai din stanga coloane care contine un nod de pe nivelul respectiv +1.
Arborele din exemplu are 6 niveluri, latimile nivelurilor fiind 1, 13, 18, 18, 13, 12.
Cand desenam un arbore binar dupa aceste reguli ne intereseaza si latimea nivelului cu latime maxima si care este acest nivel. Daca exista mai multe niveluri cu latimea maxima, ne intereseaza cel cu numarul cel mai mic.
In exemplul de mai sus latimea maxima a unui nivel este 18 si ea este atinsa pe nivelurile 3 si 4, deci nivelul care ne intereseaza este 3.

Cerinta

Dat fiind un arbore binar, scrieti un program care sa determine latimea maxima a unui nivel in arborele desenat dupa regulile de mai sus si nivelul cu numarul cel mai mic care are aceasta latime.

Date de intrare

Fisierul de intrare latime.in contine pe prima linie un numar natural N reprezentand numarul de noduri din arbore. Nodurile sunt numerotate de la 1 la N. Fiecare dintre urmatoarele N linii contine cate 3 numere întregi separate prin cate un spatiu x s d cu semnificatia "fiul stang al nodului x este s, iar fiul drept al nodului x este d". Daca un nod nu are fiu stang sau fiu drept atunci s, respectiv d, pentru nodul respectiv va avea valoarea -1. Radacina arborelui este nodul 1.

Date de iesire

Fisierul de iesire latime.out va contine o singura linie pe care se afla doua numere naturale separate printr-un singur spatiu niv lat cu semnificatia "cel mai mic nivelul de latime maxima este niv, iar latimea lui este lat".

Restrictii

  • 1<=N<=1000

Exemplu

latime.in latime.out

19
1 2 3
2 4 5
3 6 7
4 8 -1
5 9 10
6 11 12
7 13 -1
8 -1 -1
9 14 15
10 -1 -1
11 16 -1
12 -1 -1
13 17 -1
14 -1 -1
15 18 -1
16 -1 -1
17 -1 19
18 -1 -1
19 -1 -1

3 18

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 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, descfib, maraton, masina1, otilia, multiplu, tub, pasune, remi, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
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, 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, 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 arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, 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, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
Software recomandat
surse trimise | ajutor