Повышенный (3 балла за три вопроса) Время: 8-12 мин Python lru_cache any / all Все задачи №19 в каталоге

Задания №19–21. Игра с камнями: код Кабанова

Тема: Выигрышные стратегии Пети и Вани: одна куча и две кучи

Одна игра и три вопроса про начальное количество камней S. Мы пишем короткую функцию, которая умеет проверять «кто выигрывает за m ходов», и тремя вызовами отвечаем на все три вопроса.

Что от тебя хотят

Петя и Ваня по очереди ходят в игре с камнями, Петя первый. Есть правила ходов и порог, при достижении которого игра заканчивается. Выигрывает тот, кто сделал последний ход. Начальное количество камней S неизвестно, и про него задают три вопроса. В экзамене это задания 19, 20 и 21, а в нашем банке они собраны в один блок с одной игрой и тремя вопросами.

Три вопроса и что вызвать

Как звучит вопрос	Что проверить в коде
№19. Петя не может выиграть первым ходом, но при любом его ходе Ваня выигрывает своим первым ходом	`f(S, 2)`
№19, вариант «возможно». Ваня выиграл первым ходом после неудачного хода Пети: при каком S это возможно	`any(f(x, 1) for x in moves(S))`
№20. У Пети есть стратегия: за один ход он не выигрывает, но выигрывает вторым ходом при любой игре Вани	`f(S, 3) and not f(S, 1)`
№21. Ваня выигрывает первым или вторым ходом при любой игре Пети, но не может гарантированно выиграть первым	`f(S, 4) and not f(S, 2)`

Идея Кабанова: считаем ходы по одному

Функция f(h, m) отвечает на вопрос «чем кончится игра, если сделать не больше m ходов». Вызываем её всегда для начального положения, когда ходит Петя. Тогда:

если m нечётное, ответ True означает «выигрывает Петя»;
если m чётное, ответ True означает «выигрывает Ваня».

Внутри функции три строки: «если игра кончилась, засчитываем победу тому, кто сделал последний ход»; «если ходы закончились, никто не выиграл»; «иначе пробуем все ходы». Для нашего игрока достаточно одного хорошего хода (any), а противника придётся проверить на любой ход (all).

Менять в коде нужно только две вещи: функцию moves (какие ходы бывают) и условие конца игры. Весь остальной код переписывать не придётся ни в одной задаче.

Разбор 1: одна куча

Куча из S камней, S ≥ 3215. За ход можно убрать 4 камня, убрать 5 камней или уменьшить число камней в 3 раза (с округлением вверх). Игра заканчивается, когда в куче не более 3214 камней. Вопрос 1: сумма всех S, при которых выполнено условие №19. Вопрос 2: наименьшее и наибольшее S из №20. Вопрос 3: сколько значений S подходит под №21.

В левом окне округление вверх записано как (h + 2) // 3. Ответы: 38578, 9647 и 28938, 8. Они совпадают с ответами из банка.

Разбор 2: две кучи

Две кучи: в первой 6 камней, во второй S (от 1 до 93). За ход можно добавить в любую кучу один камень или увеличить любую кучу в четыре раза. Игра заканчивается, когда в двух кучах вместе не меньше 100 камней. Три вопроса те же.

Состояние теперь пара (a, b), ходы возвращают пары, конец игры по sum(h). Правое окно даёт ответы 4, 3 и 23, 22. Первый вопрос здесь в варианте «возможно», поэтому в нём стоит any по первому ходу Пети.

Округление вверх в целых числах. Деление с округлением вверх пишут (h + 2) // 3 для деления на 3 и (h + k - 1) // k для любого k. Обычное // округляет вниз и даёт другой ответ.

Разновидности и прототипы задания на экзамене

Тип 1: Одна куча

Состояние это одно число. Ходы: добавить камни, убрать, умножить или разделить.

Тип 2: Две кучи

Состояние это пара (a, b). Ход меняет одну из куч, игра кончается по сумме камней.

Тип 3: Особые правила

Например, удвоение запрещено, когда кучи равны. Такое условие попадает в функцию moves.

Код решения на Python

Запустить код в онлайн-песочнице

from functools import lru_cachedef moves(h)@lru_cache(None)any(hod) / all(hod)m % 2 == 0(a, b)sum(h)range(...)

Одна куча

from functools import lru_cache


def moves(h):
    return h - 4, h - 5, (h + 2) // 3


@lru_cache(None)
def f(h, m):
    if h <= 3214:
        return m % 2 == 0
    if m == 0:
        return 0
    hod = [f(x, m - 1) for x in moves(h)]
    if (m - 1) % 2 == 0:
        return any(hod)
    return all(hod)


S = range(3215, 100000)

q1 = [s for s in S if f(s, 2)]
print(sum(q1))

q2 = [s for s in S if f(s, 3) and not f(s, 1)]
print(min(q2), max(q2))

q3 = [s for s in S if f(s, 4) and not f(s, 2)]
print(len(q3))

Задача из базы, которую решает этот код Открыть в песочнице

Две кучи

from functools import lru_cache


def moves(h):
    a, b = h
    return [
        (a + 1, b), (a, b + 1),
        (a * 4, b), (a, b * 4),
    ]


@lru_cache(None)
def f(h, m):
    if sum(h) >= 100:
        return m % 2 == 0
    if m == 0:
        return 0
    hod = [f(x, m - 1) for x in moves(h)]
    if (m - 1) % 2 == 0:
        return any(hod)
    return all(hod)


S = range(1, 94)

q1, q2, q3 = [], [], []
for s in S:
    h = (6, s)
    if any(f(x, 1) for x in moves(h)):
        q1.append(s)
    if f(h, 3) and not f(h, 1):
        q2.append(s)
    if f(h, 4) and not f(h, 2):
        q3.append(s)

print(min(q1))
print(min(q2), max(q2))
print(q3)

Задача из базы, которую решает этот код Открыть в песочнице

Типичные ошибки

✕ Не так

Путать, за кого True

При нечётном m в f True значит победу Пети, при чётном победу Вани.

✓ Так

Перед вызовом проверь чётность m и держи в голове таблицу: №19 это m = 2, №20 m = 3, №21 m = 4.

✕ Не так

Забыть про not f(S, 1) во втором и третьем вопросах

В ответ попадут значения S, где Петя (или Ваня) выигрывает слишком рано.

✓ Так

Условие «не может выиграть первым ходом» записывать явно: and not f(S, 1) и and not f(S, 2).

✕ Не так

Забыть ход, который запрещён или особый

Если при равных кучах удвоение запрещено, а в moves оно осталось, ответ окажется неверным.

✓ Так

Правила игры целиком вписывать в moves: условие if a == b внутри функции.

ГРОБ

ГРОБ №19–21: Две кучи с особым правилом

Бывает, что одну из куч нельзя трогать при определённом условии, или что ход зависит от того, какая куча больше. Тогда набор ходов у разных позиций получается разный.

Как обойти

Всё это решается внутри moves(h): вытащи a, b = h, и допиши нужные if перед return. Остальной код остаётся без изменений.

Лайфхаки на экзамене

Для двух куч состояние хранится кортежем (a, b): списки нельзя класть в lru_cache, кортежи можно.
Диапазон S бери из условия: для одной кучи начни с порога плюс один, для двух возьми диапазон второй кучи.
Сначала проверь функцию на очень маленькой игре, где исход можно разобрать руками: например, куча до 5 камней и ходы +1 и ×2.

Банк реальных задач №19 Открыть в тренажере СмартКИМ