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

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

Пример

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

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

Например, пусть в одной куче 23 камня, а в другой 28 камней; такую позицию в игре обозначим (23, 28). Тогда за один ход можно получить любую из четырёх позиций: (34, 28), (23, 39), (38, 28), (23, 43).

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

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

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

Решение

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

Подходят S = 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57 — всего 11.

Проверка для S = 47: после каждого хода Пети у Вани есть ход, заканчивающий игру (Петя → Ваня):

(9, 47) → (20, 47) → (31, 47)
(9, 47) → (24, 47) → (35, 47)
(9, 47) → (9, 58) → (24, 58)
(9, 47) → (9, 62) → (24, 62)

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

from functools import lru_cache


def moves(p):
    a, b = p
    return [(a + 11, b), (a + 15, b), (a, b + 11), (a, b + 15)]


def done(p):
    a, b = p
    return a * b >= 1391


@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, 155)
print(len([s for s in R if f((9, s), 2)]))

Ответ: 11.

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