Страница:
<< 21 22 23 24
25 26 27 >> [Всего задач: 145]
|
[Кошки-Мышки
]
|
|
Сложность: 4-
|
Игровое поле для игры «Кошки-мышки» представляет собой совокупность
кружков, некоторые из которых соединены линиями. Первый игрок играет за
«кошек», второй – за «мышек». В процессе игры кошки и мышки
располагаются в кружках игрового поля. Ходы совершаются игроками по очереди. За один ход игрок может
передвинуть некоторые из своих фигур (кошек или мышек) по линиям, ведущим
из тех кружков, где они в данный момент находятся. Первыми ходят кошки.
В случае если кошка окажется в одном кружке с мышкой, мышка считается
съеденной. Цель первого игрока – съесть максимальное число мышек и сделать
это как можно быстрее, цель второго – помешать первому игроку.
Напишите программу, определяющую максимальное число мышек, которых
съедят кошки, и номер хода, на котором будет съедена последняя из них, в
предположении о наилучших действиях обоих игроков.
Входные данные
В первой строке входного файла содержатся два целых числа N и M –
количество кружков (1 ≤ N ≤ 20) и линий (1 ≤ M ≤
200) на игровом поле. В следующих M строках указаны номера кружков, которые соединяются
очередной линией. Далее следуют количество кошек и номера кружков, в
которых они первоначально располагаются. После этого в таком же формате
записаны данные о мышках. Суммарное количество кошек и мышек не
превосходит четырех.
Выходные данные
Запишите в выходной файл максимальное количество мышек, съедаемых
кошками, минимальное число ходов, необходимых для этого, и все возможные
положения кошек после первого хода, обеспечивающие достижение цели за
указанное число ходов.
Пример входного файла
8 9
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 8
8 6
1 5
2 3 7
Пример выходного файла
1 2
6
Та же задача, если требуется, чтобы число операций было
пропорционально
log
n. (Переменные должны быть
целочисленными.)
(В. Баур, Ф.Штрассен)
Дана программа вычисления значения некоторого многочлена
P(
x1,...,
xn), содержащая только команды
присваивания. Их правые части — выражения, содержащие
сложение, умножение, константы, переменные
x1,...,
xn
и ранее встречавшиеся (в левой части) переменные. Доказать,
что существует программа того же типа, вычисляющая все
n производных
P/
x1,...,
P/
xn,
причём общее число арифметических операций не более чем
в
C раз превосходит число арифметических операций
в исходной программе. Константа
C не зависит от
n.
Предложенный выше алгоритм перемножения многочленов требует
порядка
n2 действий для перемножения двух многочленов
степени
n. Придумать более эффективный (для больших
n)
алгоритм, которому достаточно порядка
nlog 4/log 3 действий.
Перечислить все последовательности длины
n из чисел
1..k в таком порядке, чтобы каждая следующая отличалась
от предыдущей в единственной цифре, причём не более, чем
на
1.
Страница:
<< 21 22 23 24
25 26 27 >> [Всего задач: 145]
Фильтр
Решение 
