Одна задачка
^ruВидимо, мне доведётся готовить задачи к заочной олимпиаде моего факультета по програмированию, и по этому поводу я получил сборник с задачами прошлого года. Одна из задачек мне понравилась настолько,что заслужила место в моём ЖЖ:

В тридевятом царстве в тридесятом государстве для получения лицензии на проведение любых исследований необходимо разрешение председателя Комиссии по наукоёмким технологиям. В комиссии N ≤ 1000 чиновников. Соответственно, у каждого чиновника (кроме самого главного №1) есть 1 непосредственный начальник и могут быть подчинённые (как непосредственные, так и подчинённые его подчинённых). Согласно естественным правилам бюрократической системы каждый чиновник, кроме самых младших, на заявлении может потребовать подписи одного или нескольких своих прямых подчинённых и взятку, как за то, чтобы можно было обойти нижестоящих чиновников, так и просто за свою подпись. Для каждого чиновника известен непустой список возможных наборов "виз" (подписей своих подчинённых) и соответствующая каждому набору взятка (достаточно наличие только одного набора). Пустой набор означает, что данный чиновник не требует виз в данном случае. В какую минимальную сумму обойдётся лицензия на проведение исследований?