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

---

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

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

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

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

---

Задача 58307  (#27.001)

Темы:   [ Индукция в геометрии ] [ Раскраски ]

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

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

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

Решение

---

Задача 58308  (#27.002)

Темы:   [ Индукция в геометрии ] [ Выпуклые многоугольники ]

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

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

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

Решение

---

Задача 58309  (#27.003)

Темы:   [ Индукция в геометрии ] [ Трапеции (прочее) ] [ Теорема Фалеса и теорема о пропорциональных отрезках ]

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

Пусть E – точка пересечения боковых сторон AD и BC трапеции ABCD, B_n+1 – точка пересечения прямых A_nC и BD  (A₀ = A),  A_n+1 – точка пересечения прямых EB_n+1 и  AB. Докажите, что  A_nB = ^AB/_n+1.

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

Решение

---

Задача 58310  (#27.004)

Темы:   [ Индукция в геометрии ] [ Свойства суммы, разности векторов и произведения вектора на число ]

Сложность: 4- Классы: 8,9,10,11

На прямой даны точки A₁, ..., A_n и B₁, ..., B_n–1. Докажите, что     = 1.

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

Решение

---

Задача 58311  (#27.005)

Темы:   [ Индукция в геометрии ] [ Системы точек и отрезков (прочее) ]

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

Докажите, что если n точек не лежат на одной прямой, то среди прямых, их соединяющих, не менее n различных.

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

Решение

---

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

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