Fişierul intrare/ieşire:petsoft.in, petsoft.outSursăConcurs de incalzire 2004
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

PetSoft

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.

Cerinta

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.

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.

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.

Restrictii si precizari

  • 1 ≤ N ≤ 1000
  • Fiecare angajat poate fi incadrat in maxim o echipa.

Exemplu

petsoft.inpetsoft.out
5
1
4
2
4
4

Explicatii

Se vor forma echipele 2-4 si 3-5.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content