Задания 19-21. Информатика. ЕГЭ. Шастин. 13.03.2025

19

(Д. Бахтиев) Два игрока, Полина и Вероника, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Полина. За один ход игрок может уменьшить количество камней в одной из куч в два раза (если количество камней в куче нечётно, остаётся на \(1\) камень меньше, чем убирается) или убрать из одной из куч пять камней, при этом два камня перекладываются в соседнюю кучу, а оставшиеся три выбрасываются в океан несбывшихся надежд. Например, пусть в одной куче \(10,\) а в другой \(15\) камней; такую позицию мы будем обозначать \((10, 15).\) За один ход из позиции \((10, 15)\) можно получить любую из четырёх позиций: \((5, 17),\) \((12, 10),\) \((10, 7)\) и \((5, 15).\) Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более \(69.\) Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет \(69\) или меньше камней. В начальный момент в первой куче было \(35\) камней, во второй куче — \(S\) камней, \(S > 50.\) Укажите максимальное значение \(S,\) при котором Полина не может выиграть за один ход, но при любом ходе Полины Вероника может выиграть своим первым ходом.

20

Для игры, описанной в задании 19, найдите минимальное и максимальное значения \(S,\) при котором у Полины есть выигрышная стратегия, причём одновременно выполняются два условия:

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

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

21

Для игры, описанной в задании 19, найдите наименьшее значение \(S,\) при котором одновременно выполняются два условия:

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

from math import floor

def moves(h):
    h1, h2 = h
    return (floor(h1 / 2), h2), (h1, floor(h2 / 2)), (h1 - 5, h2 + 2), (h1 + 2, h2 - 5)

def game_over(heaps):
    return sum(heaps) <= 69

def win1(heaps):
    return not game_over(heaps) and any(game_over(m) for m in moves(heaps))

def lose1(heaps):
    return all(win1(m) for m in moves(heaps))

def win2(heaps):
    return not win1(heaps) and any(lose1(m) for m in moves(heaps))

def lose2(heaps):
    return all(win1(m) or win2(m) for m in moves(heaps)) \
        and any(win2(m) for m in moves(heaps))

z19 = [S for S in range(51, 1000) if lose1((35, S))]
z20 = [S for S in range(51, 1000) if win2((35, S))]
z21 = [S for S in range(51, 1000) if lose2((35, S))]
print(max(z19))
print(min(z20), max(z20))
print(min(z21))