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

---

Компьютерная сеть Пентагона состоит из 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

   Решение

---

Семь монет расположены по кругу. Известно, что какие-то четыре из них, идущие подряд, – фальшивые и что каждая фальшивая монета легче настоящей. Объясните, как найти две фальшивые монеты за одно взвешивание на чашечных весах без гирь. (Все фальшивые монеты весят одинаково.)

   Решение

---

Докажите, что из n предметов чётное число предметов можно выбрать 2^n–1 способами.

   Решение

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

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

---

Задача 30708  (#022)

Темы:   [ Правило произведения ] [ Теория множеств (прочее) ]

Сложность: 2+ Классы: 6,7

Человек имеет 10 друзей и в течение нескольких дней приглашает некоторых из них в гости так, что компания ни разу не повторяется (в какой-то из дней он может не приглашать никого). Сколько дней он может так делать?

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

Решение

---

Задача 30710  (#024)

Темы:   [ Треугольник Паскаля и бином Ньютона ] [ Целочисленные решетки (прочее) ] [ Сочетания и размещения ]

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

План города имеет схему, изображенную на рисунке.

На всех улицах введено одностороннее движение: можно ехать только "вправо" или "вверх".
Сколько есть разных маршрутов, ведущих из точки A в точку B.

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

Решение

---

Задача 30711  (#025)

Темы:   [ Треугольник Паскаля и бином Ньютона ] [ Мощность множества. Взаимно-однозначные отображения ] [ Разбиения на пары и группы; биекции ]

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

Докажите, что из n предметов чётное число предметов можно выбрать 2^n–1 способами.

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

Решение

---

Задача 30712  (#026)

Темы:   [ Треугольник Паскаля и бином Ньютона ] [ Мощность множества. Взаимно-однозначные отображения ]

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

Докажите, что  

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

Решение

---

Задача 30713  (#027)

Темы:   [ Треугольник Паскаля и бином Ньютона ] [ Целочисленные решетки (прочее) ]

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

Докажите, что каждое число a в треугольнике Паскаля равно
  а) сумме чисел предыдущей правой диагонали, начиная с самого левого вплоть до стоящего справа над числом a.
  б) сумме чисел предыдущей левой диагонали, начиная с самого правого вплоть до стоящего слева над числом a.

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

Решение

---

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

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