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

В массивах a: array[0..k] of integer и b: array[0..l] of integer хранятся коэффициенты двух многочленов степеней k и l. Поместить в массив c: array[0..m] of integer коэффициенты их произведения. (Числа k,l,m — натуральные, m = k + l; элемент массива с индексом i содержит коэффициент при степени i.)

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

Решение

(В. Баур, Ф.Штрассен) Дана программа вычисления значения некоторого многочлена P(x₁,..., x_n), содержащая только команды присваивания. Их правые части — выражения, содержащие сложение, умножение, константы, переменные x₁,..., x_n и ранее встречавшиеся (в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все n производных P/x₁,...,P/x_n, причём общее число арифметических операций не более чем в C раз превосходит число арифметических операций в исходной программе. Константа C не зависит от n.

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

Решение

Предложенный выше алгоритм перемножения многочленов требует порядка n² действий для перемножения двух многочленов степени n. Придумать более эффективный (для больших n) алгоритм, которому достаточно порядка n^{log 4/log 3} действий.

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

Решение

(Для знакомых с основами анализа; сообщил А. Г.Кушниренко) Дополнить алгоритм вычисления значения многочлена в заданной точке по схеме Горнера вычислением значения его производной в той же точке.

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

Решение

Страница: 1 [Всего задач: 4]