Fişierul intrare/ieşire:creioane.in, creioane.outSursăONI 2008 clasa a 6-a
AutorDoru Popescu AnastasiuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.015 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Creioane (clasa a 6-a)

Notă: testele acestei probleme au fost modificate faţă de original pentru a ridica nivelul de dificultate.

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.

Exemplu

creioane.increioane.out
7
2 7
0 0
0 0
2 7
4 6
2 7
0 0
3

Explicaţie

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
Trebuie sa te autentifici pentru a trimite solutii. Click aici