Задача к ЕГЭ по информатике на тему «прочие прототипы» №1

Просмотров 13 Комментарии 0

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

В начальный момент в первой куче было $20$ камней, во второй куче был $10$ каменей, в третьей — $S$ камней, $1 ≤ S ≤ 39$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Петя выиграл своим первым ходом. Назовите минимальное значение $S$ , при котором это возможно.

from functools import lru_cache

def moves(h):

    a, b, c = h

    return (a + 1, b, c), (a, b + 1, c), (a, b, c + 1), (a * 2, b, c), (a, b * 2, c), (a, b, c * 2)

@lru_cache(None)

def f(h):

    if sum(h) >= 70:

        return «END»

    if any((f(x) == «END») for x in moves(h)):

        return «P1»

    if all((f(x) == «P1») for x in moves(h)):

        return «V1»

    if any((f(x) == «V1») for x in moves(h)):

        return «P2»

    if all((f(x) == «P2» or f(x) == «P1») for x in moves(h)):

        return «V2»

for s in range(39, 0, -1):

    h = 20, 10, s

    if f(h) == «P1»:

        print(s, «P1»)

Ответ: 20