АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

907. Опрос приборов

Ограничение времени: 2 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Имеется N приборов (устройств). Каждое устройство может иметь несколько подчинённых, соединённых напрямую кабелем. Все приборы имеют уникальные номера от 1 до N. Система образует дерево с корневым прибором с номером 1.

Опрос дерева осуществляется следующим образом. Корневой прибор посылает запрос одновременно всем своим непосредственным подчинённым. Те сразу же, в свою очередь, посылают запросы всем своим подчинённым и так далее.

Для каждого прибора есть свое время обработки Ti мс.

Обработка данных в каждом устройстве происходит следующим образом:

·      Если прибор не имеет подчинённых, то он возвращает своё состояние через Ti мс. Возвращает тому, от кого получен запрос.

·      Иначе, как только он получает данные хотя бы с Х% непосредственно подчинённых приборов, он начинает обрабатывать эту информацию и возвращает результаты через Ti мс.

Определите максимальное Х, при котором опрос произойдёт за время, не превосходящее Т.

Опрос заканчивается, как только корневой прибор соберёт всю необходимую информацию. Временем передачи информации между приборами можно пренебречь. Время обработки корневого прибора не учитывается.

В первой строке входного файла содержатся два целых числа: N (1  N  10 000) и Т (0  Т  106).

Следующая (N  1) строка содержит информацию о приборах со 2-го по N-й по одному описанию прибора в строке. Каждая из этих строк содержит два числа: Pi (1 ≤ Pi  N) и Ti (0  Ti  100). Pi – номер родительского прибора (то есть прибор, для которого устройство c номером i является подчинённым).

Выведите в выходной файл одно искомое число в процентах с точностью не менее 4 знаков после запятой.

Пример

Поток ввода

Поток вывода

6 3

1 2

2 2

2 1

1 2

1 4

50.00000000

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XIV Межвузовская олимпиада 2011 /
906. E - Минное поле 907. 908. G - Покраска паттернов 909. H - Сотовая связь 910. I - Мaршрутизация
 
время генерации 0.062 сек.
© Copyright ВоГУ, АВТ, Носов Д.А.