Compania

comp

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

== include(page="template/taskheader" task_id="comp") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| comp.in | comp.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="comp") ==

==Include(page="template/raw")==
 
Compania
 
 
 
O companie internationala are N angajati, numerotati de la 1 la N. Acestia sunt organizati intr-o structura ierarhica cu urmatoarele proprietati:
 
o fiecare angajat are un superior direct, cu exceptia angajatului cu numarul 1 care este managerul companiei
 
o fiecare angajat poate fi superiorul direct a 0, 1 sau cel mult 2 alti angajati.
 
Pentru a imbunatati eficienta afacerii lor, detinatorii companiei au decis sa o imparta in trei companii mai mic. Pe langa alte probleme pe care le-au avut de rezolvat a aparut una foarte importanta: cum trebuie distribuiti angajatii la cele trei companii nou create? Trebuie luate in considerare urmatoarele conditii:
 
o fiecare angajat trebuie distribuit la una dintre cele trei companii
 
o un angajat si superiorul sau nu trebuie sa fie distribuiti la aceeasi companie
 
o daca doi angajati au acelasi superior, atunci ei trebuie sa fie distribuiti la companii diferite
 
Pentru ca cele trei companii sa fie la fel de eficiente a mai aparut o conditie suplimentara. Sa presupunem ca N1 este numarul de angajati distribuiti la prima companie, N2 este numarul de angajati distribuiti la cea de-a doua companie si N3 este numarul de angajati distribuiti la cea de-a treia companie (N1+N2+N3=N). Cu aceste notatii, trebuie ca diferenta max(N1,N2,N3)-min(N1,N2,N3) sa fie cat mai mica posibil.
 
h2. Date de Intrare
 
Fisierul de intrare comp.in contine pe prima linie un singur numar natural N, care reprezinta numarul de angajati ai companiei. Fiecare dintre urmatoarele N-1 linii contine doua numere naturale a si b cuprinse intre 1 si N, separate printrun singur spatiu, care semnifica faptul ca angajatul b este superiorul direct al angajatului a.
 
h2. Date de Iesire
 
Fisierul de iesire comp.out va avea o singura linie pe care se vor afla N numere, separate prin spatii, din multimea {1,2,3}. Primul numar reprezinta numarul companiei la care a fost distribuit angajatul cu numarul 1, al doilea numar reprezinta numarul companiei la care a fost distribuit angajatul cu numarul 2, al treilea numar reprezinta numarul companiei la care a fost distribuit angajatul cu numarul 3 etc.
 
h2. Restrictii si precizari
 
o 0 <= N <= 16.000
 
o max(a,b,c) reprezinta maximul dintre valorile a,b si c
 
o min(a,b,c) reprezinta minimul dintre valorile a,b si c
 
o este acceptata orice solutie care minimizeaza diferenta specificata in enunt
 
o datele de intrare sunt corecte
 
h2. Exemplu
 
comp.in comp.out
6 3 1 3 2 1 2
 
2 1
 
3 2
 
4 2
 
5 3
 
6 3
 
 
==Include(page="template/taskfooter" task_id="comp")==