ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

J. Теория Невероятности

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Евгений Кондратьев, знаменитый профессор Галактического Института, продолжает свою работу над Универсальной Теорией Невероятности. На данный момент она состоит из n гипотез. Некоторые из них основаны на других гипотезах Теории. Как и любая теория, исследующая невероятностные эффекты, теория Кондратьева очень сложна, поэтому нет ничего удивительного в том, что зависимости между гипотезами могут образовывать циклы.
После нескольких отчаянных, но безуспешных попыток объяснить исход последнего эксперимента средствами Теории профессор начал подозревать, что с некоторыми гипотезами явно что-то не так.
Чтобы найти ошибки в Теории Невероятности, профессор Кондратьев построил специальный компьютер, который за ti секунд может проверить, является ли i-я гипотеза допустимой. Компьютер способен проверять гипотезы в любом порядке, но не одновременно. Профессор также смог вычислить для i-й гипотезы число pi — вероятность того, что эта гипотеза является допустимой. Известно, что допустимость гипотезы никак не зависит от допустимости других гипотез.
Профессор считает гипотезу истинной, если допустима и она, и все гипотезы, на которых она основана (напрямую или через другие гипотезы). Теперь профессор Кондратьев хочет абсолютно точно узнать, какие из гипотез являются истинными. Помогите ему вычислить ожидаемое время, которое на это потребуется, при условии, что процесс проверки будет организован оптимальным образом.

Исходные данные

В первой строке записано количество гипотез в Теории Невероятности n (1 ≤ n ≤ 500). В следующих n строках описываются эти гипотезы. В i-й из этих строк записаны числа ti (1 ≤ ti ≤ 1000), pi (0.0001 ≤ pi ≤ 0.9999), и ki (0 ≤ ki < n), за которыми следует ki различных номеров гипотез, на которых напрямую основана i-я гипотеза. Ни одна гипотеза не основана напрямую сама на себе. Гипотезы занумерованы целыми числами от 1 до n. Все числа ti целые.

Результат

Выведите ожидаемое время определения истинности всех гипотез, с точностью не менее 10−3.

Примеры

исходные данныерезультат
4
5 0.3 1 2
6 0.99 0
2 0.2 1 4
2 0.2 0
13.350
3
1 0.5 1 2
2 0.5 1 3
3 0.5 1 1
2.750
Автор задачи: Дамир Ахметзянов
Источник задачи: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1751. Теория Невероятности