Что проверяют задания

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

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

Определения

Позиция, полное описание состояния: размеры куч, координата фишки, набор фишек. Все дальнейшие свойства, свойства позиции, а не игроков как личностей.

Ход, разрешённое правило перехода к другой позиции. Одинаковое для обоих, если условие не вводит особый первый ход.

Терминальная позиция, из неё ходов нет, потому что достигнуто условие конца: сумма камней не меньше порога, фишка на финише и т. п. Игрок, который пришёл в такую позицию, уже выиграл предыдущим ходом.

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

Проигрышная позиция, позиция, из которой при любой своей игре соперник может принудить победу.

Оптимальная игра, каждый всегда выбирает ход, который ведёт его к победе, если она достижима, и максимально оттягивает проигрыш, если победы нет. На экзамене обычно достаточно первого: «если можно выиграть, игрок выигрывает».

Петя, игрок, который ходит первым из стартовой позиции задания. Ваня, второй.

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

k-й ход игрока, порядковый номер хода именно этого игрока, а не общий номер полухода партии.

Как устроена нумерация вопросов

Имеет смысл мыслить дерево партии по слоям:

• после одного хода Пети;
• после ответа Вани (это уже два полухода);
• после второго хода Пети;
• после второго хода Вани.

«Ваня выиграл своим первым ходом», терминальная позиция наступила на втором полуходе. «Петя выиграл своим вторым ходом», на третьем полуходе, и при этом он не мог выиграть уже первым. «Ваня выиграл первым или вторым ходом, но не гарантированно первым», победа второго игрока не позже четвёртого полухода, и среди оптимальных продолжений нет принудительной победы уже на втором полуходе.

Граф позиций

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

Позиция выигрышна, если есть ход в проигрышную для соперника. Позиция проигрышна, если все ходы ведут в выигрышные для соперника (или ходов нет, но тогда партия уже кончилась раньше).

Для ограничения «победа не позже чем за k своих ходов» ту же разметку делают с глубиной: учитывают только пути ограниченной длины.

Общий алгоритм решения

1. Формализовать позицию, список ходов и критерий конца партии.
2. Понять, какая стартовая величина неизвестна (часто размер второй кучи S) и какой вопрос задан в 19, 20 и 21.
3. Разметить позиции по выигрышности с ограничением на число ходов, начиная от терминальных.
4. Для задания 19 отобрать стартовые S, из которых выполняется указанный сценарий первого ответа Вани.
5. Для задания 20 отобрать S, из которых Петя принуждает победу своим вторым ходом, но не своим первым.
6. Для задания 21 отобрать S, из которых Ваня принуждает победу не позже второго своего хода, но не гарантирует её первым.
7. Из множества подходящих S взять минимум, сумму или перечисление, как просит бланк.

Программа построчно

В заданиях 19-21 два игрока по очереди делают ходы, а нужно найти начальные позиции, в которых кто-то из них гарантированно выигрывает. Программа перебирает все возможные партии рекурсивной функцией.

Разберём программу на условии:

Перед игроками лежит куча камней. Первый ход делает Петя. За один ход можно добавить в кучу один камень или увеличить количество камней в два раза. Игра завершается, когда в куче становится не менее 62 камней. Победителем считается игрок, сделавший последний ход.

win = 62

def f(k, m):
    if k >= win:
        return m % 2 == 0
    if m == 0:
        return False
    l = [f(k * 2, m - 1), f(k + 1, m - 1)]
    return all(l) if m % 2 == 0 else any(l)

print(min(s for s in range(1, 62) if f(s, 2)))

win = 62 - порог окончания игры из условия.

def f(k, m): - функция отвечает на вопрос: «из позиции k (камней в куче) может ли игрок, за которого считаем, гарантированно выиграть ровно за m оставшихся ходов (считая ходы обоих)?». Подробно - в разделе «Число ходов m».

if k >= win: / return m % 2 == 0 - игра уже окончена. Выиграл тот, кто сделал последний ход; функция проверяет, был ли это нужный игрок. Подробно - в разделе «Позиция и победа».

if m == 0: / return False - ходы закончились, а до порога не дошли: за отведённое число ходов выиграть не получилось.

l = [f(k * 2, m - 1), f(k + 1, m - 1)] - результаты всех возможных ходов: после каждого хода позиция меняется, а ходов остаётся на один меньше. Подробно - в разделе «Список ходов l».

return all(l) if m % 2 == 0 else any(l) - кто сейчас ходит, тот и выбирает ход. Подробно - в разделе «all и any: кто ходит».

print(min(s for s in range(1, 62) if f(s, 2))) - перебираем начальные позиции и выбираем подходящие. Какой m ставить в каждом вопросе - в разделе «Вопросы 19, 20, 21».

Позиция и победа

Позиция - всё, что определяет игру в данный момент: количество камней в куче k (или в двух кучах k1, k2). Ход меняет позицию.

    if k >= win:
        return m % 2 == 0

Эта проверка стоит первой: если игра уже закончилась, ходить больше нельзя. Условие окончания берут из текста задачи:

• «не менее 62 камней» → k >= win;
• «суммарное количество камней в кучах становится не менее 77» → k1 + k2 >= win;
• «хотя бы в одной куче не менее 36» → k1 >= win or k2 >= win;
• «не более 12 камней» (камни убирают) → k <= win.

Число ходов m

m - сколько ходов ещё осталось в партии, которую мы проверяем. Ходы считаются общие, по очереди: первый - Петин, второй - Ванин, третий - снова Петин и так далее.

• f(s, 1) - Петя выигрывает первым ходом;
• f(s, 2) - Ваня выигрывает своим первым ходом (после первого хода Пети);
• f(s, 3) - Петя выигрывает не позже второго хода;
• f(s, 4) - Ваня выигрывает не позже своего второго хода.

Почему return m % 2 == 0 в конце игры. Каждый ход уменьшает m на 1. Если игра закончилась, когда осталось чётное число ходов (например, вызвали f(s, 2), Петя сходил - осталось 1, Ваня сходил и выиграл - осталось 0), значит, последний ход сделал тот игрок, за которого считаем. Если осталось нечётное - последний ход сделал соперник, и это проигрыш.

Список ходов l

    l = [f(k * 2, m - 1), f(k + 1, m - 1)]

Для каждого хода из условия пишем вызов f от новой позиции с m - 1:

• «добавить один камень» → f(k + 1, m - 1);
• «добавить три камня» → f(k + 3, m - 1);
• «увеличить в два раза» → f(k * 2, m - 1);
• «убрать два камня» → f(k - 2, m - 1);
• «уменьшить в три раза» → f(k // 3, m - 1);
• «возвести в квадрат» → f(k * k, m - 1).

В списке l оказываются значения True и False: «приводит ли этот ход к нужному результату».

all и any: кто ходит

    return all(l) if m % 2 == 0 else any(l)

• Когда ходит игрок, за которого считаем (m нечётное), ему достаточно одного хорошего хода: any(l) - True, если хотя бы один ход ведёт к победе.
• Когда ходит соперник (m чётное), он выберет худший для нас ход. Победа гарантирована, только если все его ходы ведут к нашей победе: all(l).

Запись X if условие else Y - короткое «если … иначе …»: при m % 2 == 0 возвращается all(l), иначе any(l).

Неудачный ход: f_neudacha

В задании 19 часто спрашивают: «Ваня выиграл своим первым ходом после неудачного первого хода Пети». Значит, Петя не обязательно играл лучше всего - он сделал какой-то ход, после которого Ваня выиграл.

def f_neudacha(k, m):
    if k >= win:
        return m % 2 == 0
    if m == 0:
        return False
    l = [f(k * 2, m - 1), f(k + 1, m - 1)]
    return any(l)

Отличие от f одно: в конце всегда any(l) - достаточно, чтобы хотя бы один Петин ход давал Ване выигрыш. Внутри списка вызывается обычная f: дальше Ваня играет как обычно. Вызов: f_neudacha(s, 2).

Вопросы 19, 20, 21

• 19: «Ваня выигрывает своим первым ходом при любой игре Пети» → f(s, 2); «после неудачного хода Пети» → f_neudacha(s, 2); «Петя выигрывает первым ходом» → f(s, 1).
• 20: «у Пети есть выигрышная стратегия, но он не может выиграть первым ходом, а выигрывает вторым» → f(s, 3) and not f(s, 1).
• 21: «у Вани есть стратегия выиграть первым или вторым ходом, но нет стратегии выиграть первым ходом» → f(s, 4) and not f(s, 2).

Начальные позиции перебирают циклом в выражении:

• min(s for s in range(1, 62) if …) - наименьшее подходящее s;
• print(*(s for s in range(1, 62) if …)) - все подходящие через пробел (в задании 20 обычно два значения). Звёздочка * «раскладывает» значения по отдельности.

Диапазон берут так, чтобы игра ещё не была окончена в начальной позиции: при k >= win - от 1 до win - 1.

Ходы с условиями

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

    l = [f(k - 4, m - 1)]
    if k % 2 == 0:
        l.append(f(k // 2, m - 1))
    if k % 3 == 0:
        l.append(f(k // 3, m - 1))

• сначала в l кладут ходы, которые возможны всегда;
• l.append(…) добавляет элемент в конец списка;
• k % 2 == 0 - «чётно», k % 3 == 0 - «кратно трём».

Если формулировка «если кратно 3 - уменьшить в три раза, в противном случае убрать два камня», это один ход с выбором: f(k // 3, m - 1) if k % 3 == 0 else f(k - 2, m - 1).

Две кучи

С двумя кучами позиция - пара чисел k1, k2, и ходов вдвое больше: каждый можно сделать в любую из куч.

def f(k1, k2, m):
    if k1 + k2 >= win:
        return m % 2 == 0
    if m == 0:
        return False
    l = [f(k1 + 1, k2, m - 1), f(k1 * 2, k2, m - 1),
         f(k1, k2 + 1, m - 1), f(k1, k2 * 2, m - 1)]
    return all(l) if m % 2 == 0 else any(l)

• f(k1 + 1, k2, m - 1) - добавили камень в первую кучу, вторая не изменилась;
• f(k1, k2 * 2, m - 1) - удвоили вторую кучу;
• если ход «увеличить в два раза каждую из куч» - f(k1 * 2, k2 * 2, m - 1);
• если ходить можно только в большую кучу, ходы зависят от того, какая куча больше: if k1 >= k2: … и if k2 >= k1: … (при равных - обе).

В вопросе одну кучу фиксируют числом из условия, а вторую перебирают: f(7, s, 2).