Задание 21 ЕГЭ: две кучи, камни добавляются

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

Пример

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

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

Например, пусть в одной куче 27 камней, а в другой 39 камней; такую позицию в игре обозначим (27, 39). Тогда за один ход можно получить любую из четырёх позиций: (32, 39), (27, 44), (54, 39), (27, 78).

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

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

Найдите наименьшее значение S, при котором одновременно выполняются два условия:

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

Решение

Первое условие — f(S, 4): при любой игре Пети Ваня выигрывает не позже своего второго хода. Второе — не f(S, 2): гарантированно выиграть первым ходом Ваня не может (иначе это значение S из задания 19). Нужны S, для которых верно первое и не верно второе.

Проверка для S = 5 (все ходы Пети):

Петя: (27, 5) — одним ходом Ване не выиграть; он ходит в (32, 5), и после любого хода Пети выигрывает своим вторым ходом.
Петя: (44, 5) — Ваня сразу выигрывает ходом в (88, 5);
Петя: (22, 10) — одним ходом Ване не выиграть; он ходит в (22, 20), и после любого хода Пети выигрывает своим вторым ходом.
Петя: (22, 10) — одним ходом Ване не выиграть; он ходит в (22, 20), и после любого хода Пети выигрывает своим вторым ходом.

Программа: f(p, m) — может ли «наш» игрок выиграть из позиции p не более чем за m полуходов (на нечётном m ходит «наш» игрок — нужен хотя бы один хороший ход, any; на чётном ходит соперник — хорошими должны быть все его ходы, all).

from functools import lru_cache


def moves(p):
    a, b = p
    return [(a + 5, b), (a * 2, b), (a, b + 5), (a, b * 2)]


def done(p):
    a, b = p
    return a + b >= 70


@lru_cache(None)
def f(p, m):
    if done(p):
        return m % 2 == 0
    if m == 0:
        return False
    h = [f(q, m - 1) for q in moves(p)]
    return any(h) if m % 2 else all(h)


R = range(1, 48)
print(min(s for s in R if f((22, s), 4) and not f((22, s), 2)))

Ответ: 5.

Решить такую задачу — новый вариант с проверкой