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

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

Пример

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

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

Например, пусть в одной куче 13 камней, а в другой 28 камней; такую позицию в игре обозначим (13, 28). Тогда за один ход можно получить любую из четырёх позиций: (14, 28), (13, 29), (15, 28), (13, 30).

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

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

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

• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания через пробел.

Решение

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

Подходят S = 129, 142, 156, 157. Спрашивают не два наименьших, а наименьшее и наибольшее — первый и последний элементы списка, поэтому диапазон просматриваем до конца.

Проверка для S = 129: выиграть первым ходом Петя не может, а ходом (7, 129) → (9, 129) он ставит Ваню в проигрышную позицию: любой ход Вани (слева) Петя заканчивает выигрышным ходом (справа):

(10, 129) → (12, 129)
(11, 129) → (12, 129)
(9, 130) → (11, 130)
(9, 131) → (11, 131)

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

from functools import lru_cache


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


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


@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, 204)
a20 = [s for s in R if f((7, s), 3) and not f((7, s), 1)]
print(a20[0], a20[-1])

Ответ: 129 157.

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