mese
La firma DOT de pe planeta
CAMP lucreaza n persoane, numerotate
de la 1
la n. Seful cel mare pregateste o petrecere la care sa participe
toti angajatii. La fiecare masa se vor aseza unul sau mai multi angajati respectand
urmatoarele doua reguli:
- suma varstelor angajatilor asezati la aceeasi masa sa nu depaseasca valoarea
S;
- oricare doua persoane a si
b, persoane asezate la aceeasi
masa, fie se cunosc, fie exista k
persoane de la aceeasi masa x1,
x2, …, xk
astfel incat a cunoaste pe x1,
x1 cunoaste pe x2,…
xk cunoaste pe b.
Firma fiind foarte mare, fiecare se cunoaste doar cu seful sau direct si cu
subordonatii sai directi. Ierarhia din firma este necontradictorie, adica nu
exista un lant de forma x1
este seful lui x2,
x2 este seful lui
x3,…, xk-1
este seful lui xk,
xk este seful lui
x1.
Cerinta
Scrieti un program care sa determine numarul minim de mese necesare pentru petrecere.
Date de intrare
Pe prima linie a fisierului de intrare mese.in sunt scrise numerele n si S, separate printr-un spatiu. Pe urmatoarele n linii sunt scrise cate doua numere intregi separate de cate un spatiu; primul numar de pe linia i+1 reprezinta seful direct al lui i, al doilea numar reprezinta varsta lui i. Exista o singura linie, corespunzatoare sefului cel mare, in care seful direct este 0.
Date de iesire
Fisierul de iesire mese.out va contine o singura linie pe care va fi scris numarul minim de mese necesare pentru petrecere.
Restrictii
Exemplu
|
mese.in |
mese.out |
Explicatie |
|
6 10 |
3 |
O posibila aranjare
la cele 3 mese: |
Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila 5 Mb, din care pentru stiva 1 Mb.
prof.
Nistor Mot
Colegiul National
"N.Balcescu"