Fişierul intrare/ieşire:trib.in, trib.outSursăBOI 2003
AutorMihai PatrascuAdăugată de
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Consiliul tribului

Tribul Kazooba este format din N oameni ce doresc sa se reuneasca pentru un consiliu al tribului. Oamenii sunt cu totii descendenti a unui singur om, care este seful tribului. Deoarece toti oamenii acestui trib au o viata lunga, ascendentii fiecarei persoane, chiar si seful tribului, sunt in viata si se vor prezenta la consiliu.
Oamenii ajung la consiliu intr-o anumita ordine si se aseaza la mese la venire. Ei stau intr-un rand de mese paralele. Prima masa este asezata la poalele Muntelui Sfant, si randul se extinde infinit spre vest (partea opusa muntelui). Pe de alta parte, fiecare om ar dori sa fie cat mai aproape de divinitate, asa ca, atunci cand soseste, el se aseaza catre masa cea mai apropiata de Muntele sfant la care nu s-a asezat nici unul dintre copiii sau tatal lui.
Ca de obicei, zeii tribului au o inclinatie aparte pentru frumusete. Ei ar dori sa ceara membrilor tribului sa soseasca la consiliu intr-o ordine in care numarul de mese ocupate sa fie maxim. Din pacate, ei nu au nici un fel de inclinatie pentru programare, asa ca v-au cerut voua sa scrieti un program pentru asta.

Cerinta

Scrieti un program care determina numarul maxim de mese ce poate fi ocupat la consiliu.

Date de Intrare

Prima linie a fisierului trib.in contine un numar intreg N, reprezentand numarul de oameni din trib. Oamenii sunt numerotati de la 1 la N; seful lor este numarul 1. Fiecare dintre urmatoarele linii contin doua numere A, B cu semnificatia "exista o legatura directa de rudenie intre persoanele A si B". Relatiile descrise in fisierul de intrare sunt corecte (de exemplu nu exista cicluri, iar fiecare persoana este unul dintre descendentii sefului).

Date de Iesire

Fisierul trib.out are o singura linie ce contine numarul maxim de mese care pot fi ocupate.

Restrictii si precizari

  • 1 < N ≤ 100 000
  • pentru 30% dintre teste N ≤ 1000
  • orice masa are capacitate nelimitata

Exemplu

trib.intrib.out
5
1 4
3 2
1 3
3 5
3

Explicatie

Daca oamenii sosec in ordinea 2 4 1 5 3, ei se aseaza astfel:
-2 se aseaza la prima masa
-4 se aseaza la prima masa
-1 are un fiu (4) la prima masa asa ca se aseaza la masa a 2-a
-5 se aseaza la prima masa
-3 are 2 fii la prima masa (2 si 5) si pe tatal sau (1) la a 2-a masa, asa ca se aseaza la a 3-a masa

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content