Fișierul intrare/ieșire creioane.in, creioane.out Sursă ONI 2008 clasa a 6-a
Autor Doru Popescu Anastasiu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.015 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in creioane.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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii