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

---

Компьютерная сеть Пентагона состоит из 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 [Всего задач: 30]      

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

---

Задача 60478  (#03.026)  [Числа Ферма]

Темы:   [ Делимость чисел. Общие свойства ] [ Разложение на множители ]

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

Пусть a и n – натуральные числа, большие 1. Докажите, что если число  aⁿ + 1  простое, то a чётно и  n = 2^k.
(Числа вида  f_k = 2^2k + 1  называются числами Ферма.)

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

Решение

---

Задача 60479  (#03.027)

Темы:   [ Делимость чисел. Общие свойства ] [ Разложение на множители ]

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

Пусть  f_n = 2²ⁿ + 1.  Докажите, что  f_n  делит  2^f_n – 2.

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

Решение

---

Задача 60480  (#03.028)

Темы:   [ Простые числа и их свойства ] [ Формулы сокращенного умножения (прочее) ]

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

Докажите, что числа Ферма  f_n = 2²ⁿ + 1  при  n > 1  не представимы в виде суммы двух простых чисел.

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

Решение

---

Задача 60481  (#03.029)  [Числа Мерсенна]

Темы:   [ Простые числа и их свойства ] [ Разложение на множители ]

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

Пусть a и n – натуральные числа, большие 1. Докажите, что если число aⁿ – 1 простое, то  a = 2  и n – простое.
(Числа вида  q = 2ⁿ – 1  называются числами Мерсенна.)

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

Решение

---

Задача 60482  (#03.030)

Темы:   [ Простые числа и их свойства ] [ Целочисленные и целозначные многочлены ] [ Многочлен n-й степени имеет не более n корней ]

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

Пусть P(x) – многочлен ненулевой степени с целыми коэффициентами. Могут ли все числа P(0), P(1), P(2), ... быть простыми?

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

Решение

---

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

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