Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | trib.in, trib.out | Sursă | BOI 2003 |
Autor | Mihai Patrascu | Adăugată de | |
Timp execuţie pe test | 0.125 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Consiliul tribului
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
Link: [1]File-List
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 copii 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 persoane 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.in trib.out Explicatie
5 3 Daca oamenii sosec in ordinea 2 4 1 5 3, ei se aseaza astfel:
1 4 -2 se aseaza la prima masa
3 2 -4 se aseaza la prima masa
1 3 -1 are un fiu (4) la prima masa asa ca se aseaza la masa a 2-a
3 5 -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
References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/trib/enunt_files/filelist.xml