Задания 19-21. Информатика. ЕГЭ. Статград. 24.10.2024-1

19

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

1. убрать из кучи один камень;
2. если количество камней в куче кратно трём, уменьшить его в три раза, в противном случае убрать из кучи два камня;
3. если количество камней в куче кратно пяти, уменьшить его в пять раз, в противном случае убрать из кучи три камня.

Например, если в куче \(12\) камней, то за один ход можно получить \(11\), \(4\) или \(9\) камней.

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

В начале игры в куче было \(S\) камней, \(S > 19.\)

Укажите минимальное значение \(S\), при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим первым ходом.

20

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

21

Для игры, описанной в задании 19, найдите минимальное значение \(S,\) при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом.

def moves(h):
    return h - 1, h // 3 if h % 3 == 0 else h - 2, h // 5 if h % 5 == 0 else h - 3

HEAP_SIZE = 20
heap = [None] * 200

for i in range(199, 19, -1):
    if any(x < HEAP_SIZE for x in moves(i)):
        heap[i] = 'P1'

for i in range(199, 19, -1):
    if not heap[i] and all(heap[x] == 'P1' for x in moves(i)):
        heap[i] = 'V1'

print('Решение 19 задачи')
for i in range(199, 19, -1):
    if heap[i] == 'V1':
        print(i)

for i in range(199, 19, -1):
    if not heap[i] and any(heap[x] == 'V1' for x in moves(i)):
        heap[i] = 'P2'

print('Решение 20 задачи. Выбери 2 минимальных значения')
for i in range(199, 19, -1):
    if heap[i] == 'P2':
        print(i)

for i in range(199, 19, -1):
    if not heap[i] and all(heap[x] in ('P1', 'P2') for x in moves(i)):
        heap[i] = 'V2'

print('Решение 21 задачи. Выбери минимальное значение')
for i in range(199, 19, -1):
    if heap[i] == 'V2':
        print(i)