Экспресс-подготовка. Часть IV

1.

ЭКСПРЕСС-ПОДГОТОВКА
Часть IV
КЕГЭ-2023
19-20-21
игровая стратегия, две кучи

2.

Задания 19-21
• Для решения задач на две кучи
модифицируем способ для 1 кучи.
• Также будем решать задачу для всех
позиций, а затем искать ответы на вопросы
• Все договоренности и определения
описаны в разборе задач на 1 кучу

3.

Опишем решение стандартной задачи на одну кучу «ручным» способом.
Вершины будем задавать как кортеж из двух элементов. Программа получения
смежных вершин будет выглядеть следующим образом:
Список состояния «раскраски» сделаем двумерным и назовем XY.
Заполнение можно провести следующим образом (без стремления за какой-либо
оптимальностью):

4.

Основной блок практически без изменений (только замена одинарного
цикла обхода вершин на двойной и замена списка A на флаг)
Как посмотреть результат? Надо посмотреть условие добавить обработку
списка XY или его строки

5.

Вопросы, код программы для вывода ответов
Ответы:
19 = 38
20 = 22 35
21 = 16

6.

Основной блок практически без изменений (только замена одинарного
цикла обхода вершин на двойной и замена списка A на флаг)
Текст достаточно объёмный (50
строк), но очень много ‘copypaste’ (вывод результата,
повторения)
Решение занимает около 15
минут ( по спецификации дается
25 минут)
Далее разбор ещё одной задачи

7.

Опишем решение стандартной задачи на одну кучу «ручным» способом.
Программа получения смежных вершин и начальное заполнение «списка раскраски»:
«Список раскраски» заполнили 0 и -1, то есть часть вершин раскрасили в «чётные»
цвета, а часть в «нечётные»
Основной блок менять не надо. Изменим блоки выводов.
Разберем вопросы и найдем ответы. Для этого достаточно исследовать XY[5]

8.

19. В списке XY[5] находим поля из которых выигрывают на 1 такте и ищем
минимальное S, позволяющее попасть в этот набор.
S=26 : (5,26) -> (5,26*2) -> (5,52*2) (5+52*2=109).
20-1. В списке XY[5] находим поля из которых выигрывают на 2 такте и ищем лучшие
поля из которых есть возможность проиграть в 1 ход. Минимальным будет S=44
(5,44) ->(5,88)->(5,166) = Петя выиграл сделав 1 ход (при остальных ответах Вани за 2)
20-2. Берем XY[5] и находим поля из которых выигрывают на 3 такте (S=25).

9.

21. В списке XY[5] находим поля из которых выигрывают на 4
такте.
Ответы:
19 = 26
20 = 44 25
21 = 34
Этот пример показывает,
что способ дает
возможность решить
большой класс задач, в том
числе и достаточно
сложных