Версия для печати
Убрать все задачи

---

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

КГБ хочет прослушивать все передаваемые в сети Пентагона сообщения. Для этого советскими программистами был разработан вирус, который, будучи установлен на какой-либо из компьютеров, передает КГБ всю информацию, проходящую через него. Оказалось, что материальные затраты, необходимые для установки вируса на различные компьютеры, различны. Требуется определить набор компьютеров, которые КГБ должно инфицировать, чтобы минимизировать общие материальные затраты.

Входные данные
Первая строка входного файла содержит N – количество компьютеров в сети (1 ≤ N ≤ 500). В i-й из последующих N строк содержатся номера компьютеров, с которыми непосредственно связан компьютер номер i. Далее следуют N целых чисел из диапазона [1, 1000] – материальные затраты, связанные с установкой вируса на каждый из компьютеров.

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

Пример входного файла
5
5
4
4
2 3 5
4 1
1 5 5 2 10

Пример выходного файла
3
1 4

   Решение

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 129]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 31366

Тема:   [ Соображения непрерывности ]

Сложность: 3- Классы: 5,6,7,8

Матч между двумя футбольными командами закончился со счетом 8:5. Доказать, что был момент, когда первая команда забила столько же мячей, сколько второй оставалось забить.

Прислать комментарий

Решение

---

Задача 34940

Тема:   [ Малые шевеления ]

Сложность: 3-

Докажите, что на координатной плоскости можно провести окружность, внутри которой лежит ровно n целочисленных точек.

Прислать комментарий

Решение

---

Задача 35732

Тема:   [ Соображения непрерывности ]

Сложность: 3 Классы: 7,8

Шеренга новобранцев стояла лицом к сержанту. По команде "налево" некоторые повернулись налево, некоторые – направо, а остальные – кругом.
Всегда ли сержант сможет встать в строй так, чтобы с обеих сторон от него оказалось поровну новобранцев, стоящих к нему лицом?

Прислать комментарий

Решение

---

Задача 104102

Темы:   [ Монотонность и ограниченность ] [ Тригонометрические уравнения ] [ Смешанные уравнения и системы уравнений ]

Сложность: 3 Классы: 9,10

Решите систему уравнений:
    x² + 4sin²y – 4 = 0,
    cos x – 2cos²y – 1 = 0.

Прислать комментарий

Решение

---

Задача 32840

Тема:   [ Соображения непрерывности ]

Сложность: 3+ Классы: 7,8,9

Выйдя на маршрут в 4 часа утра, альпинист Джеф Лоу к вечеру достиг пика "Свободная Корея". Переночевав на вершине, на следующий день он вышел в то же время и быстро спустился обратно по пути подъема. Докажите, что на маршруте есть такая точка, которую Лоу во время спуска и во время подъема проходил в одно и то же время суток.

Прислать комментарий

Решение

---

Страница: 1 2 3 4 5 6 7 >> [Всего задач: 129]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями