Две кучи

Чем позиция с двумя кучами отличается от позиции с одной?

Позиция — пара чисел (a, b): камни в первой и во второй куче. Ход меняет одну кучу, и какую — выбирает тот, кто ходит. В задаче темы можно добавить три камня или удвоить кучу. Из (7, 10) получается четыре позиции:

• (10, 10) — три камня в первую кучу;
• (14, 10) — удвоить первую;
• (7, 13) — три камня во вторую;
• (7, 20) — удвоить вторую.

Если условие не говорит иного, за ход нельзя менять обе кучи сразу. И «своих» куч у игроков нет: и Петя, и Ваня на каждом ходе выбирают из всех четырёх ходов.

Что поменять в программе?

Только moves и finished: позиция становится парой, а функция g остаётся прежней. Правила задачи темы:

def moves(p):    a, b = p    return [(a + 3, b), (a * 2, b),            (a, b + 3), (a, b * 2)]  def finished(p):    a, b = p    return a + b >= 100  print(moves((7, 10)), finished((7, 93)))

Пару в Python записывают кортежем: (7, 10). Строка a, b = p раскладывает его на две кучи. g работает с позицией только через moves и finished, поэтому ей всё равно, число в позиции или пара.

Как выглядят группы позиций двух куч?

Позиции двух куч — клетки таблицы: строка — первая куча, столбец — вторая. Возьмём игру поменьше: +1 или ×2 в одну кучу, победа при сумме не менее 20, начало (3, S):

Проверим (3, 8). Ходы дают (4, 8), (6, 8), (3, 9) и (3, 16) — из каждой соперник выигрывает сразу: удваивает вторую кучу или добавляет камень к 16. Все ходы ведут в В1, значит, (3, 8) — П1.

Сумма камней позицию не описывает. У (6, 6) и (2, 10) сумма 12, но из (2, 10) удвоение даёт (2, 20) — победа, а из (6, 6) лучший ход даёт только 18. Удваивают одну кучу, поэтому важно, как камни разложены, — на сетке у этих клеток разные группы.

Решим задачу темы целиком:

«Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) три камня или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 100. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах всего 100 камней или больше. В начальный момент в первой куче было 7 камней, во второй куче — S камней; 1 ≤ S ≤ 92. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 19. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

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

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

Программа из подтемы 3 с новыми правилами и начальными позициями (7, S) отвечает на все три вопроса за один запуск. Ответ — вторая куча, p[1]:

from functools import cache  def moves(p):    a, b = p    return [(a + 3, b), (a * 2, b),            (a, b + 3), (a, b * 2)]  def finished(p):    a, b = p    return a + b >= 100  @cachedef g(s):    nxt = moves(s)    if any(finished(q) for q in nxt):        return 1  # В1    r = [g(q) for q in nxt]    if all(x == 1 for x in r):        return -1  # П1    if -1 in r:        return 2  # В2    if all(x > 0 for x in r):        return -2  # П2    return 0  def mistake(s):    # Петя ходит так, что Ваня выигрывает сразу    return any(not finished(q) and g(q) == 1               for q in moves(s))  starts = [(7, s) for s in range(1, 93)]print(min(p[1] for p in starts if mistake(p)))print([p[1] for p in starts if g(p) == 2][:2])print(min(p[1] for p in starts if g(p) == -2))

Ответы: задание 19 — 24, задание 20 — 23 42, задание 21 — 39. Их можно проверить и рассуждением:

• 19: быстрее всего растёт вторая куча при двух удвоениях: 7 + 4S ≥ 100, то есть S ≥ 24. Из (7, 23) получится только 7 + 92 = 99.
• 20: из (7, 23) Петя удваивает вторую кучу и отдаёт Ване (7, 46). Это П1: после любого хода Вани — (10, 46), (14, 46), (7, 49) или (7, 92) — Петя добирает до 100 одним ходом. Из (7, 42) ловушка — (7, 45), туда ведёт ход +3.
• 21: из (7, 39) три хода ведут в В2 Вани, а ход (7, 78) — в В1. Все ходы в В1 или В2, но не все в В1 — это П2.

А если игра кончается не по сумме или ходы другие?

Меняются только moves и finished — их пишут дословно по условию. Правила окончания в подборках бывают такие:

сумма не менее 100

a + b >= 100чаще всего

в одной из куч не менее 50

a >= 50 or b >= 50хватает одной кучи

в обеих кучах не менее 50

a >= 50 and b >= 50нужны обе сразу

произведение не менее 400

a * b >= 400«произведение количеств камней»

С ходами так же. «Добавить в кучу столько камней, сколько в другой» — это (a + b, b) и (a, a + b). «Первую кучу можно удвоить, а вторую — утроить» — (a * 2, b) и (a, b * 3). Перечисли в moves все ходы, что разрешает условие, — и ни одного лишнего.

• Позицияпара (a, b) — кортеж
• Ходменяет одну кучу, любую из двух
• movesчетыре хода: каждая операция с каждой кучей
• gне меняется
• Суммане описывает позицию: важно, как разложены камни
• Начало (7, S)ответ — p[1]
• Задача темы24; 23 42; 39