mese
В една
компания
работят n човека,
номерирани
от 1 до n. Шефът
планира да
организира
банкет за всичките
служители. На всяка
маса на банкета
трябва да
седнат един
или повече служители,
съгласно
следните
правила:
- сумата от
възрастите
на
служителите,
седнали на
една и съща
маса не
трябва да
надминава
стойността S;
- всеки двама
служители a и b, които са
седнали на
една и съща
маса са
такива, че или
се познават,
или могат да
се намерят k
служителя,
седнали на
същата маса: x1, x2, …, xk, такива
че a познава x1, x1 познава x2,… , xk познава b.
Понеже
компанията е
много голяма,
всеки служител
познава само
своя пряк
началник и своите
преки
подчинени.
Йерархията в
компанията е непротиворечива,
т.е. не
съществува
възможността:
x1 да
е началник на
x2, x2 да е
началник на x3,…, xk-1 да е
началник на xk, xk да е
началник на x1.
Задача
Напишете
програма,
която
определя
минималния
брой на масите,
които са
необходими
за банкета.
Вход
Първият
ред на
входния файл mese.in съдържа
числата n и S,
разделени с
интервал.
Всеки от
следващите n реда
съдържа две
цели числа,
разделени с
интервал:
първото
число от (i+1)-вия ред
показва
номера на
служителя,
който е пряк
шеф на
служителя с
номер i,
а второто
число от
същия ред
показва
възрастта на
служителя с
номер i. Измежду
тези редове,
има един
единствен, съответстващ
на шефа на
компанията,
при който на
мястото на
номера на
неговия пряк
началник е
записано
числото 0.
Изход
Изходният
файл mese.out трябва
да съдържа
единствен
ред с търсената
минимална
стойност.
Ограничения
Пример
mese.in |
mese.out |
Обяснение |
6 10 |
3 |
Едно
възможно
разпределение
на 3 маси е следното: |
Време
за работа на
програмата: 0.2 seconds/test
Разрешена
памет: 5 Mb, от които 1 Mb за
стек.
prof.
Nistor Mot
"N.Balcescu"
Превод на
български:
Емил
Келеведжиев