petsoft

PetSoft

== include(page="template/taskheader" task_id="petsoft") ==

==Include(page="template/taskheader" task_id="petsoft")==

Poveste ...

Petrica detine o companie de software numita PETSOFT cu care este lider in domeniu. Secretul succesului sta in modul de organizare interna din aceasta firma. Fiecare angajat are asociat un numar distinct de la $1$ la $N$ si se stie pentru fiecare angajat cine este seful sau direct (angajatul numarul $1$ este chiar Petrica si nu are nici un sef). Mai exact relatiile dintre angajatii firmei formeaza un arbore cu radacina in nodul $1$. Firma este invitatata la un targ international de software unde isi va prezenta oferta. La conferinta se vor prezenta din partea firmei un numar de echipe (stabilit de Petrica) de cate doi angajati. Petrica nu este interasat de numarul de echipe ci de valoarea lor. Pentru asta el stabileste urmatoarele regula: angajatii $x$ si $y$ pot fi trimisi la conferinta impreuna daca $x$ este seful direct al lui $y$ sau daca $x$ si $y$ au acelasi sef iar valoarea echipei formate din cei doi este $|x - y|$. De asemenea este stiut faptul ca Petrica (angajatul numarul {$1$}) nu va fi incadrat in nici o echipa, el fiind managerul firmei. Valoarea totala e echipelor va fi suma valorilor tuturor echipelor.

h2. Cerinta

...
 
h2. Restrictii
 
...

Se cauta un programator capabil sa stabileasca modul de formare a echipelor astfel incat valoarea totala a echipelor sa fie maxima. Odata gasit, el va fi angajat direct intr-un loc de frunte in ierarhia firmei. Poti fi chiar tu acel programator, dar trebuie sa demostrezi ca esti alegerea buna dezvoltand un program care poate calcula valoarea totala maxima a echipelor pe care firma le va trimite la conferinta.

h2. Date de intrare

...

Pe prima linie in fisierul de intrare $petsoft.in$ se afla un numar intreg $N$ reprezentand numarul de angajati ai firmei. Pe urmatoarele $N-1$ linii sunt date informatiile cu privire la ierhia firmei: pe linia $i$ se afla seful angajatului cu numarul $i$.

h2. Date de iesire

...

Pe prima linie din fisierul de iesire $petsoft.out$ se va gasi un numar intreg reprezentand valoarea totala maxima a echipelor ce vor fi trimise la conferinta.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 1000$
* Fiecare angajat poate fi incadrat in maxim o echipa.

h2. Exemplu

| petsoft.in | petsoft.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. petsoft.in |_. petsoft.out |
| 5
1
4
2
4
| 4 |

== include(page="template/taskfooter" task_id="petsoft") ==

h3. Explicatii
 
Se vor forma echipele 2-4 si 3-5.
 
==Include(page="template/taskfooter" task_id="petsoft")==
 
 

141