Задача по информатике на всероссийском конкурсе по програмированию,
проводимом Фихтехом. Для сомневающихся- ссылка
http://frtk.ru/it2007/tasksa.html
Слов нет...................
А2. Коррумпированное государство
В тридевятом царстве в тридесятом государстве для получения лицензии на
проведение любых исследований необходимо разрешение председателя
Комиссии по наукоемким технологиям. В комиссии N < =100 чиновников.
Соответственно, у каждого чиновника (кроме самого главного №1) есть 1
непосредственный начальник и могут быть подчиненные (как
непосредственные, так и подчиненные его подчиненных). Согласно
естественным правилам бюрократической системы каждый чиновник, кроме
самых младших, на заявлении может потребовать на заявлении подписи
одного или нескольких своих прямых подчиненных и взятку, как за то,
чтобы можно было обойти нижестоящих чиновников, так и просто за свою
подпись. Для каждого чиновника известен непустой список возможных
наборов "виз" (подписей своих подчиненных) и соответствующая каждому
набору взятка (достаточно наличие только одного набора). Пустой набор
означает, что данный чиновник не требует виз в данном случае. В какую
минимальную сумму обойдется лицензия на проведение исследований?
Ввод: Ν , в следующих строках: < номер чиновника (1..N) > < взятка
— целое число меньше 10000 > < набор виз (может быть пустым) — номера
чиновников, разделенные пробелом > (Замечание: для каждого чиновника
можно записать несколько таких строк). Количество виз в наборе не
превосходит 50. Количество наборов для каждого чиновника не превосходит
15.
Вывод: < Сумма взяток >
Пример
Ввод: 4
3 100
1 300
1 100 2 3
4 20
3 50 4
2 50
1 200 2
Вывод: 220