| Fişierul intrare/ieşire: | dosare.in, dosare.out | Sursă | Stelele Informaticii 2007, clasele 9-10 |
| Autor | Liviu Ciortea | Adăugată de |  Andrei Grigorean •wefgef |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dosare
Spre deosebire de prietenii sai - Miruna si Algorel - care isi pierd timpul cu bile si bilute, Haralambie este mult mai practic in prag de Craciun: el s-a decis sa-si optimizeze sistemul de fisiere.
Dosarele de pe calculatorul lui Haralambie sunt organizate ierarhic. In dosarul principal se afla mai multe dosare, care la randul lor contin alte dosare, s.a.m.d. El foloseste doar tastatura pentru a se deplasa prin ele, asa ca este foarte importanta ordinea in care se afla subdosarele intr-un dosar. Pentru a intra intr-un subdosar al unui dosar, Haralambie trebuie sa apese tasta de navigare in jos (sageata jos) pana cand se afla deasupra subdosarului dorit.
Spre exemplu, daca in dosarul principal, numerotat cu 1, se afla, in aceasta ordine, dosarele 2, 3 si 4, si in dosarul 3 se afla dosarele 5, 6 si 7, pentru a accesa dosarul 7, Haralambie trebuie sa apese tasta ENTER pentru a intra in 1, sa apese sageata jos o data pana ajunge pe 3, din nou ENTER pentru a intra in 3, apoi de doua ori sageata in jos, si inca o data ENTER pentru a intra in 7, deci in total 6 apasari de taste.
Haralambie cunoaste pentru fiecare dosar in parte de cate ori va avea nevoie sa acceseze acel dosar si va promite sa va cinsteasca cu bile colorate daca veti ordona subdosarele in dosare in asa fel incat numarul total de apasari de taste sa fie minim. La fiecare accesare a unui dosar, considerati ca Haralambie va porni din dosarul principal.
Date de intrare
Fisierul de intrare dosare.in contine pe prima linie numarul total de dosare, N. Pe urmatoarele N-1 linii se afla informatiile referitoare la ierarhia sistemului de dosare. Pe linia i se afla dosarul parinte al dosarului i. Dosarul principal are numarul de ordine 1. Pe ultima linie a fisierului de intrare se afla N numere intregi, reprezentand numarul de accesari al fiecarui dosar.
Date de iesire
In fisierul de iesire dosare.out se va afla pe singura linie numarul total minim de apasari.
Restrictii
- 1 ≤ N ≤ 16000
- 1 ≤ Ai ≤ 1000000
- Pentru 40% din teste 1 ≤ N ≤ 333
Exemplu
| dosare.in | dosare.out |
|---|---|
| 9 1 1 1 3 3 3 4 4 1 1 1 1 1 1 1 1 1 | 31 |
Explicatie
Dosarul 1 contine dosarele 2, 3 si 4. In dosarul 3 avem dosarele 5, 6 si 7 iar in dosarul 4 avem dosarele 8 si 9.
Putem aseza dosarele in urmatorul mod: in dosarul 3 vom aseza subdosarele in ordinea 5, 6, 7, in dosarul 4 in ordinea 8, 9, iar in dosarul 1 in ordinea 3, 4, 2.
Conform acestei asezari, scorul total va fi: 1*1 + 1*4 + 1*2 + 1*3 + 1*3 + 1*4 + 1*5 + 1*4 + 1*5 = 31. Orice alta asezare va rezulta intr-un numar total cel putin egal cu 31.
