Задача к ЕГЭ по информатике на тему «Уменьшение количества камней» №1

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

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

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

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

from functools import lru_cache

def moves(h):

    a, b = h

    res = []

    if a — 2 >= 0:

        res.append((a — 2, b))

    if b — 2 >= 0:

        res.append((a, b — 2))

    if a > 0:

        res.append((a // 2, b))

    if b > 0:

        res.append((a, b // 2))

    return tuple(res)

@lru_cache(None)

def f(h):

    if sum(h) <= 12:

        return «END»

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

        return «P1»

    if any((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») for x in moves(h)):

        return «V2»

for s in range(1, 100):

    h = 25, s

    if f(h) == «V1»:

        print(s, «V1»)

Ответ: 1