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

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


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

Ionică are la dispoziţie n creioane identice, numerotate cu 1, 2, ..., n. Într-un moment de relaxare începe să aşeze pe masă creioanele, unele peste altele astfel încât poate aşeza un creion direct pe masă sau pe minim două creioane aflate la aceeaşi înălţime. Toate creioanele care nu sunt aşezate direct pe masă, sunt paralele cu suprafaţa mesei. În felul acesta se creează pe masă mai multe grămezi, fiecare cu o anumită înălţime (numărul de niveluri de creioane).

Cerinţă

Să se determine înălţimea celei mai înalte grămezi.

Date de intrare

Fişierul creioane.in conţine pe prima linie un număr natural n reprezentând numărul de creioane. Pe fiecare dintre următoarele n linii se află câte două numere separate printr-un spaţiu; astfel pe linia i+1 se află numerele ai şi bi (0<i<n+1) cu semnificaţia că ai şi bi reprezintă două dintre creioanele pe care se află creionul i. În cazul în care creionul i este aşezat direct pe masă, ai şi bi sunt amândouă egale cu 0.

Date de ieşire

Fişierul de ieşire creioane.out va conţine pe prima linie numărul cerut.

Restricţii

1 < n <= 9000
Orice creion care se află aşezat direct pe masă şi peste care nu se află aşezat nici un alt creion, formează o grămadă de înălţime 1.

Exemple

creioane.increioane.outExplicaţii
7 2 7 0 0 0 0 2 7 4 6 2 7 0 0 3 Pe masă se aşază creioanele 2, 3 şi 7. Peste creioanele 2 şi 7 se aşează creioanele 1, 4 şi 6, iar peste creioanele 4 şi 6 se aşază creionul 5. Cea mai înaltă grămadă are înâlţimea 3, pentru că:
- pe nivelul 1 se află creioanele 2, 3 şi 7
- pe nivelul 2 se află creioanele 1, 4 şi 6
- pe nivelul 3 se află creionul 5

autor: Prof. Doru Popescu Anastasiu
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2008: ab2, iepuras, palind, auto, div, teatru, pm, submat, reteta2, rezervatie, melci, mere2, felinare, joc3, 2numere, fi, tablou, borcane, mexc, tcast, dep, dist1, stiva, banda, pavare, poarta, aranjare, bile4, subgeom, albinuta1, curent, pviz, atac2, virus
De acelaşi autor: degrade, hora, noroc, test, tren, grad, palma, cs, h, vagoane, scaune, tir, nrcuv2, piata, vocale, prop, poligon, text2, onu2, exp, donald, young, albine, turn, linie, tub, suma1, triunghi, cod1, pic, zuzu, pav, prieteni1, banda10, numar2, prime1, ziduri, puncte2, texan, part, ucif, numere7, mare, furnica, pavare, cifre3, domino, exp1, coduri, efort, prodmax, char, dartz, operatii, jucarii, cd1, codif, bileprime, echipa, covor, pavari, parcela, grad1, ec, stalpi2, grad2, testament, nrpomi, elicop, triburi1, showroom, cartite
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor