19 задание ЕГЭ информатика

Теория игр: выигрыш за один ход

1 балл ≈ 6 мин уровень Б Анализ алгоритма логической игры

Задания 19–21 – одна игра: куча камней (или две кучи), игроки Петя и Ваня ходят по очереди, первым ходит Петя. Возможные ходы заданы (добавить/убрать камни, умножить/разделить). Игра заканчивается, когда количество камней достигает порога. Задание 19 – обычно: Петя не может выиграть первым ходом, но при любом ходе Пети Ваня выигрывает своим первым ходом (или «Ваня выигрывает после неудачного хода Пети»). 1 балл.

Универсальная программа (оценка позиции)

from functools import lru_cache

def moves(s):
    return s + 1, s * 2           # ходы из условия

@lru_cache(None)
def f(s):
    if s >= 29:                    # игра окончена: ходивший ПЕРЕД нами выиграл
        return 0
    res = [f(m) for m in moves(s)]
    neg = [r for r in res if r <= 0]
    if neg:                        # есть ход в проигрышную для соперника позицию
        return 1 - max(neg)        # выигрываю за столько ходов
    return -max(res)               # все ходы ведут к выигрышу соперника

print([s for s in range(1, 29) if f(s) == -1])

Смысл значения: f(s) = k > 0 – игрок, который ходит, выигрывает своим k-м ходом; f(s) = −k – он проигрывает, соперник выигрывает своим k-м ходом.

Соответствие заданиям

19: «Ваня выигрывает первым ходом при любом ходе Пети» → f(s) == −1.
20: «Петя выигрывает вторым ходом, но не первым» → f(s) == 2.
21: «Ваня выигрывает первым или вторым ходом, но не гарантированно первым» → f(s) == −2.

Разобранный пример. Ходы: +1 или ×2; игра заканчивается при s ≥ 29; начальное s ≤ 28. Для s = 14: ходы Пети в 15 или 28; из 15 Ваня делает ×2 = 30, из 28 – +1 = 29. Ваня выигрывает первым ходом при любом ходе Пети: f(14) = −1. Ответ задания 19 – 14.

Вариант «неудачный ход Пети» (Ваня может выиграть первым ходом, если Петя сходит плохо): ищи s, где f(s) не равно 1, но среди f(m) есть значение 1: any(f(m) == 1 for m in moves(s)).

Ловушки: условие окончания (≥ или >, «не более 30» при убывании) и направление диапазона s; «округляется до меньшего» – целочисленное деление //; для двух куч позиция – пара (a, b), ходы применяются к каждой куче.

На экзамене

Одна функция f решает 19, 20 и 21 – меняется только сравниваемое значение.
Проверь условие окончания игры буквально: «не менее 29» – это s >= 29.
Для двух куч: def moves(a, b): return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2).

Разобранные задания 19 из открытого банка ФИПИ

Пример 1 · код ФИПИ 35A49A

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы.

Игра завершается в тот момент, когда количество камней в куче становится не менее 58.

Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой находится 58
или больше камней.

В начальный момент в куче было S камней; 1 ≤ S ≤ 57.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Показать ответ и решение

Ответ: 28

Игра: +1, +4, ×2, конец при ≥ 58.

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

Перебор позиций программой (рекурсия по ходам) даёт 28.

Пример 2 · код ФИПИ 4B9187

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

– добавить в одну из куч (по своему выбору) 3 камня;

– увеличить количество камней в одной из куч (по своему выбору) в 3 раза.

Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (23, 30), (20, 33), (60, 30), (20, 90).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 176. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую игровую позицию, при которой в двух кучах суммарно 176 камней
или больше. В начальный момент в первой куче было 14 камней, во второй куче – S камней; 1 ≤ S ≤ 161.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Ваня выиграл своим первым ходом после неудачного хода Пети. Укажите минимальное значение S,
при котором такая ситуация возможна.

Показать ответ и решение

Ответ: 18

Игра: две кучи (14, S), +3 или ×3, конец при сумме ≥ 176.

Ищем S, при котором у Пети есть ход в позицию, из которой Ваня выигрывает одним ходом.

Перебор программой: наименьшее такое S = 18.

Пример 3 · код ФИПИ 719FB2

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:

– убрать из кучи 3 камня;

– убрать из кучи 5 камней;

– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).

Например, из кучи в 20 камней за один ход можно получить кучу из 17, 15 или 5 камней.

Игра завершается, когда количество камней в куче становится не более 10. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 10 или менее камней. В начальный момент в куче было S камней, S ≥ 11.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Показать ответ и решение

Ответ: 44

Игра: −3, −5, :4, конец при ≤ 10.

Перебор позиций программой (рекурсия по ходам) даёт 44.

Частые вопросы о задании 19

Сколько баллов даёт задание 19 ЕГЭ по информатике?

Максимум – 1 первичный балл. Норма времени на экзамене – около 6 мин. Уровень сложности – Б.

Что проверяет задание 19?

Как подготовиться к заданию 19?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.