Малыш и Карлсон режут квадратный торт. Карлсон выбирает на нём точку (не на границе). После этого Малыш делает прямолинейный разрез от выбранной точки до края (в любом направлении). Затем Карлсон проводит второй прямолинейный разрез от выбранной точки до края, перпендикулярный первому, и отдаёт меньший из получившихся двух кусков Малышу. Малыш хочет получить хотя бы четверть торта. Может ли Карлсон ему помешать?

   Решение

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

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

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

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