Задания 19–21 ЕГЭ по информатике: решайте с автопроверкой

Задания 19, 20 и 21 описывают одну игру. Два игрока по очереди меняют кучу камней или монет, и игра заканчивается, когда достигнут порог. Нужно найти начальные позиции, в которых у одного из игроков есть выигрышная стратегия за заданное число ходов.

Решать задачи номера

Как решать программой

Программа описывает игру рекурсивной функцией f(s, m): можно ли из позиции s за m оставшихся ходов прийти к победе нужного игрока. Если игра уже закончилась, позиция выигрышна для того, кто сделал последний ход. Если ходов не осталось, это проигрыш.

На ходу игрока, который должен выиграть, достаточно одного удачного хода, поэтому берётся any. На ходу соперника нужно, чтобы все его ходы вели к нашей победе, поэтому берётся all. Задание 20 — это f(s, 3) без f(s, 1), задание 21 — это f(s, 4) без f(s, 2).

Задание 19 часто спрашивает о неудачном ходе первого игрока, поэтому там на ходу Пети тоже стоит any. Перечитайте вопрос каждого из трёх заданий: формулировки отличаются в деталях.

Разбор примера

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

T, K = 30, 2

def moves(s):
    return (s + 1, s * K)

def f(s, m):
    if s >= T:
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(x, m - 1) for x in moves(s)]
    return any(h) if m % 2 == 1 else all(h)

print(min(s for s in range(1, T)
          if any(x < T and any(y >= T for y in moves(x)) for x in moves(s))))
print(*[s for s in range(1, T) if f(s, 3) and not f(s, 1)])
print(min(s for s in range(1, T) if f(s, 4) and not f(s, 2)))

Программа печатает

8
7 13
12

Первая строка — это ответ на задание 19, вторая на задание 20, третья на задание 21. Перед тем как вписать ответ, проверьте одну позицию руками: например, из 13 монет Петя ходит на 14, и после любого хода Вани (на 15 или на 28) Петя выигрывает следующим ходом.

Решить эту задачу

Задачи к заданиям 19–21

  • Копилка: монета или умножениеСредняяРешать
  • Гирлянда: +1, +step или удвоениеСредняяРешать
  • Два ящика: добавить содержимое соседаСложнаяРешать
  • Лёд из морозильника: убывающая кучаСредняяРешать
  • Две полки: +1 или удвоениеСложнаяРешать
  • Две башни: удвоить можно только меньшуюСложнаяРешать
  • Бусины: удвоение только нечётныхСредняяРешать
  • Два ведра песка: вычесть или ополовинитьСложнаяРешать
  • Ростки: +step, ×2 или ×3СредняяРешать
  • Табло: +1, +сумма цифр или ×multСредняяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Почему в задании 19 другая проверка?
Там спрашивают не о стратегии, а о существовании неудачного хода. Поэтому проверка проще: есть ли ход Пети, после которого Ваня выигрывает одним ходом.
Что значит чётность m в функции?
Нечётное m означает, что ходит игрок, за которого мы ищем выигрыш. Чётное означает ход соперника.
Как быть с двумя кучами?
Позиция становится парой чисел, и ходы меняют одну из куч. Функция f та же.