== include(page="template/taskheader" task_id="comp") ==
==Include(page="template/taskheader" task_id="comp")==
Poveste ...
O companie internationala are $N$ angajati, numerotati de la $1$ la $N$. Acestia sunt organizati intr-o structura ierarhica cu urmatoarele proprietati:
h2. Cerinta
* fiecare angajat are un superior direct, cu exceptia angajatului cu numarul $1$ care este managerul companiei
* 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:
h2. Restrictii
* fiecare angajat trebuie distribuit la una dintre cele trei companii
* un angajat si superiorul sau nu trebuie sa fie distribuiti la aceeasi companie
* 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 $N{~1~}$ este numarul de angajati distribuiti la prima companie, $N{~2~}$ este numarul de angajati distribuiti la cea de-a doua companie si $N{~3~}$ este numarul de angajati distribuiti la cea de-a treia companie $(N{~1~} + N{~2~} + N{~3~} = N)$. Cu aceste notatii, trebuie ca diferenta $max(N{~1~},N{~2~},N{~3~})-min(N{~1~},N{~2~},N{~3~})$ sa fie cat mai mica posibil.
h2. Date de intrare
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
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
* $0 ≤ N ≤ 16.000$
* $max(a,b,c)$ reprezinta maximul dintre valorile $a, b$ si $c$
* $min(a,b,c)$ reprezinta minimul dintre valorile $a, b$ si $c$
* este acceptata orice solutie care minimizeaza diferenta specificata in enunt
* datele de intrare sunt corecte
h2. Exemplu
| comp.in | comp.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. comp.in |_. comp.out |
| 6
2 1
3 2
4 2
5 3
6 3
| 3 1 3 2 1 2 |
== include(page="template/taskfooter" task_id="comp") ==
==Include(page="template/taskfooter" task_id="comp")==
