Fişierul intrare/ieşire:mese.in, mese.outSursă.campion 2006
AutorNistor Eugen MotAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.15 secLimită de memorie9216 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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

  • 2 ≤ n ≤ 100 000
  • Varstele sunt numere intregi cuprinse in intervalul [1 .. 255]
  • 2S30 000
  • Nici o varsta nu depaseste valoarea S

Exemplu

mese.inmese.out
6 10
5 9
3 4
0 2
2 4
3 7
2 2
3

Explicatie:

O posibila aranjare la cele 3 mese:
( 3 5 )
( 2 4 6 )
( 1 )

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content