21

Теория к заданию 21 ЕГЭ по информатике Дерево игры и выигрышная стратегия

Задание 21 — третий вопрос к игре из задания 19. Нужна позиция В2: у Вани есть стратегия выиграть первым или вторым ходом, но нет стратегии гарантированно выиграть первым ходом. Значит, позиция не П1 и не В1, а каждый ход Пети ведёт в П1 или П2. Сначала находят позиции П1, В1 и П2, затем проверяют позиции ниже П2.

Ответ — одно число, за верный ответ дают 1 балл. Ручной разбор здесь длиннее, чем в заданиях 19 и 20, поэтому удобна программа с метками позиций или программа для двух куч. Функция вызывает себя для каждого хода и без мемоизации работает слишком долго.

Пример задания

Открытый банк ФИПИ

Условие игры

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней либо увеличить количество камней в куче в четыре раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 105. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, состоящую из 105 или более камней. В начальный момент в куче было S камней; 1≤S≤104.1 \leq S \leq 104 . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Для игры, описанной выше, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них. 

Что учить: от главного к редкому

Основа

Понятия, на которых стоят все правила

  1. 1Python для ЕГЭ
  2. 2Рекурсивные функции

Главное

Самые частые правила — учите первыми

  1. 3Теория игрвстречается в каждом задании

Тренировка в формате ЕГЭ

Условие игры

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

Для игры, описанной выше, найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Закрепите на настоящих заданиях №21

Решать