Fişierul intrare/ieşire:comp.in, comp.outSursăBOI 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Compania

O companie internationala are N angajati, numerotati de la 1 la N. Acestia sunt organizati intr-o structura ierarhica cu urmatoarele proprietati:

  • 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:

  • 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 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.

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.

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.

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

Exemplu

comp.incomp.out
6
2 1
3 2
4 2
5 3
6 3
3 1 3 2 1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content