Игровое поле для игры «Кошки-мышки» представляет собой совокупность кружков, некоторые из которых соединены линиями. Первый игрок играет за «кошек», второй – за «мышек». В процессе игры кошки и мышки располагаются в кружках игрового поля. Ходы совершаются игроками по очереди. За один ход игрок может передвинуть некоторые из своих фигур (кошек или мышек) по линиям, ведущим из тех кружков, где они в данный момент находятся. Первыми ходят кошки.  В случае если кошка окажется в одном кружке с мышкой, мышка считается съеденной. Цель первого игрока – съесть максимальное число мышек и сделать это как можно быстрее, цель второго – помешать первому игроку.

Напишите программу, определяющую максимальное число мышек, которых съедят кошки, и номер хода, на котором будет съедена последняя из них, в предположении о наилучших действиях обоих игроков.

Входные данные
В первой строке входного файла содержатся два целых числа 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

   Решение

Страница: 1 2 3 >> [Всего задач: 13]      

Окружность S и точка O лежат в одной плоскости, причём O находится вне окружности. Построим произвольный шар, проходящий через окружность S, и опишем конус с вершиной в точке O и касающийся шара. Найти геометрическое место центров окружностей, по которым конусы касаются шаров.

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

Решение

Два правильных равных треугольника расположены в пространстве в параллельных плоскостях P₁ и P₂, причём отрезок, соединяющий их центры, перпендикулярен плоскостям. Найти геометрическое место точек, являющихся серединами отрезков, соединяющих точки одного треугольника с точками другого треугольника.

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

Решение

Дан прямой круговой конус и точка O. Найти геометрическое место вершин конусов, равных данному, с осями, параллельными оси данного конуса, и содержащих внутри данную точку O.

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

Решение

Рассмотрим всевозможные прямые, проходящие через точку A , не принадлежащую плоскости π , и образующие равные углы с этой плоскостью (углы, отличные от нуля). Найдите геометрическое место точек пересечения этих прямых с плоскостью π .

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

Решение

На плоскости α даны три точки A , B и C , не лежащие на одной прямой. Пусть M – такая точка в пространстве, что прямые MA , MB и MC образуют равные углы с плоскостью α . Найдите геометрическое место точек M .

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

Решение

Страница: 1 2 3 >> [Всего задач: 13]