Ограничение по ходам —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#30408

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

Показать ответ и решение

Решение руками

Мы знаем, что $S = 6$ это позиция типа $WIN2$ . Тогда рассмотрим $S = 5 :$

Решение программой

from functools import lru_cache


def moves(heap):
    h, k = heap
    m = []
    if k != 0:
        m += [(h + 1, 0)]
    if k != 1:
        m += [(h + 2, 1)]
    if k != 2:
        m += [(h * 3, 2)]
    return m


@lru_cache(None)
def game(heap):
    if heap[0] >= 50:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 50):
    if game((s, -1)) == ’V2’:
        print(s)

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 2#30407

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

Найдите наименьшее и наибольшее из таких значений $S$ . В ответе, запишите сначала наименьшее, затем наибольшее значение, без пробелов и знаков препинания.

Показать ответ и решение

Решение руками

Рассмотрим позицию $S = 6.$ Из неё Петя сходит в позицию $S = 18$ утроением камней, после чего Ваня не сможет утроить кучу, и сходит либо в $S = 20,$ либо в $S = 19.$ Из этих позиций Петя выигрывает утроением камней. Также рассмотрим позицию $S = 15.$ Из неё Петя сходит в $S = 16,$ а это позиция типа $LOSE1$ .

Решение программой

from functools import lru_cache


def moves(heap):
    h, k = heap
    m = []
    if k != 0:
        m += [(h + 1, 0)]
    if k != 1:
        m += [(h + 2, 1)]
    if k != 2:
        m += [(h * 3, 2)]
    return m


@lru_cache(None)
def game(heap):
    if heap[0] >= 50:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 50):
    if game((s, -1)) == ’P2’:
        print(s)

Ответ: 615

Ошибка.
Попробуйте повторить позже

Задача 3#30406

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

Например, если в начале игры в куче $3$ камня, Петя может первым ходом получить кучу из $4,5$ или $9$ камней. Если Петя получил кучу из $5$ камней (добавил $2$ камня), то следующим ходом Ваня может получить $6$ или $15$ камней. Получить $7$ камней Ваня не может, так как для этого нужно добавить $2$ камня, а такой ход только что сделал Петя.

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

В начальный момент в куче было $S$ камней, $1 ≤ S ≤ 49.$

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Показать ответ и решение

Решение руками

Для начала найдём все позиции $WIN1$ . Это позиции $S ≥ 17.$ Рассмотрим позицию $S = 16.$ Из неё Петя утроением камней достигнет позиции $S = 48,$ из которой Ваня выиграет добавив в кучу $2$ камня.

Решение программой

from functools import lru_cache


def moves(heap):
    h, k = heap
    m = []
    if k != 0:
        m += [(h + 1, 0)]
    if k != 1:
        m += [(h + 2, 1)]
    if k != 2:
        m += [(h * 3, 2)]
    return m


@lru_cache(None)
def game(heap):
    if heap[0] >= 50:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 50):
    if game((s, -1)) == ’V1’:
        print(s)

Ответ: 16

Ошибка.
Попробуйте повторить позже

Задача 4#30402

Для игры, описанной в задании $40,$ найдите два таких значения $S,$ при которых одновременно выполняются два условия:

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

Показать ответ и решение

Решение руками

Рассмотрим $S = 1$ . Из этой позиции Петя сможет сходить только в $S = 3,$ а мы знаем, что это позиция $WIN2$ . Теперь рассмотрим позицию $S = 2 :$

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if (heap + 1) % 2 != 0:
        m += [heap + 1]
    if (heap + 3) % 2 != 0:
        m += [heap + 3]
    if (heap * 3) % 2 != 0:
        m += [heap * 3]
    return m


@lru_cache(None)
def game(heap):
    if heap >= 63:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’


for s in range(1, 63):
    if game(s) == ’LOSE2’:
        print(s)

Ответ: 12

Ошибка.
Попробуйте повторить позже

Задача 5#30401

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

В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

Показать ответ и решение

Решение руками

Рассмотрим $S = 3.$ Первым ходом Петя достигнет позиции $S = 9,$ из которой Ваня не сможет сделать никаких ходов, кроме утроения, что приведёт Петю в позицию $S = 27,$ из которой он победит утроением. Теперь рассмотрим $S = 18.$ Первым ходом Петя сходит в позицию $S = 19,$ из которой Ваня сможет сходить лишь в $S = 57,$ из которой Петя победит также утроением.

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if (heap + 1) % 2 != 0:
        m += [heap + 1]
    if (heap + 3) % 2 != 0:
        m += [heap + 3]
    if (heap * 3) % 2 != 0:
        m += [heap * 3]
    return m


@lru_cache(None)
def game(heap):
    if heap >= 63:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’


for s in range(1, 63):
    if game(s) == ’WIN2’:
        print(s)

Ответ: 318

Ошибка.
Попробуйте повторить позже

Задача 6#30400

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в $3$ раза, при этом после каждого хода в куче должно быть нечетное количество камней. Например, пусть в куче будет $6$ камней. Тогда за один ход можно получить кучу из $7$ или $9.$ Игра завершается в тот момент, когда количество камней в куче становится не менее $63.$

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет $63$ или более камней. В начальный момент в куче было $S$ камней $1 ≤ S ≤ 62$ .

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

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

Показать ответ и решение

Решение руками

Для начала найдём все позиции типа $WIN1$ . Это позиции $S = 60,$ $S = 62$ и все нечётные позиции $S ≥ 21.$ Тогда из позиции $S = 7$ Петя может сходить только в $S = 21$ и Ваня также умножит количество камней в куче на $3$ и победит.

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if (heap + 1) % 2 != 0:
        m += [heap + 1]
    if (heap + 3) % 2 != 0:
        m += [heap + 3]
    if (heap * 3) % 2 != 0:
        m += [heap * 3]
    return m


@lru_cache(None)
def game(heap):
    if heap >= 63:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’


for s in range(1, 63):
    if game(s) == ’LOSE1’:
        print(s)
        break

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 7#30399

Для игры, описанной в задании $37,$ найдите минимальное значение $S,$ при котором одновременно выполняются два условия:

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Показать ответ и решение

Решение руками

Рассмотрим $S = 13.$ Из этой позиции Петя может сходить в $S = 10$ или $S = 11,$ а из этих позиций Ваня сходит либо в $S = 7$ , либо в $S = 8,$ а мы знаем, что это позиции типа $LOSE1$ .

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap % 2 == 0:
        m += [heap // 2]
    else:
        if heap > 1:
            m += [heap - 2]
    if heap % 3 == 0:
        m += [heap // 3]
    else:
        if heap > 2:
            m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 2:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1


for s in range(3, 100):
    if game(s) == 4:
        print(s)
        break

Ответ: 13

Ошибка.
Попробуйте повторить позже

Задача 8#30398

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

В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.

Показать ответ и решение

Решение руками

Для начала давайте найдём все позиции $WIN1$ . Это все $3 ≤ S ≤ 6.$ Теперь найдём все позиции $LOSE1$ . Это позиции $S = 7,8,12.$ Рассмотрим позицию $S = 9.$ Уменьшение на $2$ приведёт нас в $S = 7,$ а это $LOSE1$ . Теперь Рассмотрим позицию $S = 36.$ Уменьшение в $3$ раза приведёт нас в $S = 12,$ а это $LOSE1$ . Пишем их в ответ.

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap % 2 == 0:
        m += [heap // 2]
    else:
        if heap > 1:
            m += [heap - 2]
    if heap % 3 == 0:
        m += [heap // 3]
    else:
        if heap > 2:
            m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 2:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1


for s in range(3, 100):
    if game(s) == 3:
        print(s)

Ответ: 936

Ошибка.
Попробуйте повторить позже

Задача 9#30397

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

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет $2$ и менее камней. В начальный момент в куче было $S$ камней $S > 2$ .

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

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

Показать ответ и решение

Решение руками

Рассмотрим $S = 6.$ Первым ходом Петя делает неудачный ход в $S = 3,$ после чего Ваня убирает из кучи две трети камней, создавая этим позицию $S = 1$ и побеждая.

Решение программой

from functools import lru_cache


def moves(heap):
    m = []
    if heap % 2 == 0:
        m += [heap // 2]
    else:
        if heap > 1:
            m += [heap - 2]
    if heap % 3 == 0:
        m += [heap // 3]
    else:
        if heap > 2:
            m += [heap - 3]
    return m


@lru_cache(None)
def game(heap):
    if heap <= 2:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    return max(steps) + 1


for s in range(3, 100):
    print(s, game(s), [game(x) for x in moves(s)])

Ответ: 6

Ошибка.
Попробуйте повторить позже

Задача 10#28817

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

Показать ответ и решение

from functools import lru_cache


def moves(h):
    k = h[0]
    m = h[1]
    if m == 0:
        return (k + 1, 1), (k + 2, 2), (k * 3, 3)
    if m == 1:
        return (k + 2, 2), (k * 3, 3)
    if m == 2:
        return (k + 1, 1), (k * 3, 3)
    if m == 3:
        return (k + 1, 1), (k + 2, 2)


@lru_cache(None)
def f(h):
    if h[0] >= 43:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


for i in range(1, 43):
    h = i, 0
    if f(h) == ’LOSE2’:
        print(i)

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 11#28816

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

Найдите наименьшее и наибольшее из таких значений $S$ . В ответе, через пробел, запишите сначала наименьшее, затем наибольшее значение.

Показать ответ и решение

from functools import lru_cache


def moves(h):
    k = h[0]
    m = h[1]
    if m == 0:
        return (k + 1, 1), (k + 2, 2), (k * 3, 3)
    if m == 1:
        return (k + 2, 2), (k * 3, 3)
    if m == 2:
        return (k + 1, 1), (k * 3, 3)
    if m == 3:
        return (k + 1, 1), (k + 2, 2)


@lru_cache(None)
def f(h):
    if h[0] >= 43:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’


minim = 10000
maxim = 0
for i in range(1, 43):
    h = i, 0
    if f(h) == ’WIN2’:
        minim = min(minim, i)
        maxim = max(maxim, i)
print(minim,maxim)

Ответ: 5 13

Ошибка.
Попробуйте повторить позже

Задача 12#28815

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

Например, если в начале игры в куче $3$ камня, Петя может первым ходом получить кучу из $4,5$ или $9$ камней. Если Петя получил кучу из $5$ камней (добавил $2$ камня), то следующим ходом Ваня может получить $6$ или $15$ камней. Получить $7$ камней Ваня не может, так как для этого нужно добавить $2$ камня, а такой ход только что сделал Петя.

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

В начальный момент в куче было $S$ камней, $1 ≤ S ≤ 42.$

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Показать ответ и решение

from functools import lru_cache

def moves(h):
    k = h[0]
    m = h[1]
    if m == 0:
        return (k + 1, 1), (k + 2, 2), (k * 3, 3)
    if m == 1:
        return (k + 2, 2), (k * 3, 3)
    if m == 2:
        return (k + 1, 1), (k * 3, 3)
    if m == 3:
        return (k + 1, 1), (k + 2, 2)

@lru_cache(None)
def f(h):
    if h[0] >= 43:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’

for i in range(1, 43):
    h = i, 0
    if f(h) == ’LOSE1’:
        print(i)

Ответ: 14

Ошибка.
Попробуйте повторить позже

Задача 13#25913

Найдите количество значений S, при которых одновременно выполняются два условия:

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

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Показать ответ и решение

def moves(h):
    ans = []
    if (h+1) % 2 == 1:
        ans.append(h+1)
    if (h+3) % 2 == 1:
        ans.append(h+3)
    if (h*3) % 2 == 1:
        ans.append(h*3)
    return ans


def f(h):
    if h >= 51:
        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’ for x in moves(h)):
        return ’V2’


count = 0
for i in range(1, 51):
    if f(i) == ’V2’:
        count += 1
print(count)

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 14#25912

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

— Петя не может выиграть за один ход;

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

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

Показать ответ и решение

def moves(h):
    ans = []
    if (h+1) % 2 == 1:
        ans.append(h+1)
    if (h+3) % 2 == 1:
        ans.append(h+3)
    if (h*3) % 2 == 1:
        ans.append(h*3)
    return ans


def f(h):
    if h >= 51:
        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’


predmax = 0
maxim = 0
for i in range(1, 51):
    if f(i) == ’P2’:
        predmax = maxim
        maxim = i
print(predmax, maxim)

Ответ: 1214

Ошибка.
Попробуйте повторить позже

Задача 15#25911

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней в куче в три раза, добавить в кучу один камень, или 3 камня, при этом после каждого хода в куче должно быть нечетное количество камней. Например, пусть в куче было 8 камней. Тогда за один ход можно получить кучу из 9 камней или из 11 камней (увеличить количество камней в три раза нельзя, т.к. после этого хода получится четное количество камней – 24). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 51.

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно. При этом, если у Пети существует всего 1 возможный ход, который приводит Ваню к победе, то такая позиция не считается. Другими словами — единственный возможный ход нельзя назвать неудачным.

Показать ответ и решение

def moves(h):
    ans = []
    if (h+1) % 2 == 1:
        ans.append(h+1)
    if (h+3) % 2 == 1:
        ans.append(h+3)
    if (h*3) % 2 == 1:
        ans.append(h*3)
    return ans


def f(h):
    if h >= 51:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if any(f(x) == ’P1’ for x in moves(h)) and len(moves(h)) >= 2:
        return ’V1’


for i in range(1, 51):
    if f(i) == ’V1’:
        print(i)
        break

Ответ: 14

Ошибка.
Попробуйте повторить позже

Задача 16#19958

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

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

Показать ответ и решение

from functools import lru_cache

# c = 1 если в прошлый ход меняли кучи местами
def moves(h):
    a, b, c = h
    res = []

    res.append((a, b * 2, 0))
    if c == 0:
        res.append((b, a, 1))

    return tuple(res)

@lru_cache(None)
def f(h):
    if sum(h[:2]) >= 199:
        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(1, 100):
    h = 99, s, 0
    if f(h) == "V2":
        print(s, "V2")

Ответ: 7 8

Ошибка.
Попробуйте повторить позже

Задача 17#19957

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

Показать ответ и решение

from functools import lru_cache

# c = 1 если в прошлый ход меняли кучи местами
def moves(h):
    a, b, c = h
    res = []

    res.append((a, b * 2, 0))
    if c == 0:
        res.append((b, a, 1))

    return tuple(res)

@lru_cache(None)
def f(h):
    if sum(h[:2]) >= 199:
        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(1, 100):
    h = 99, s, 0
    if f(h) == "P2":
        print(s, "P2")

Ответ: 13

Ошибка.
Попробуйте повторить позже

Задача 18#19956

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

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

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

Показать ответ и решение

from functools import lru_cache

# c = 1 если в прошлый ход меняли кучи местами
def moves(h):
    a, b, c = h
    res = []

    res.append((a, b * 2, 0))
    if c == 0:
        res.append((b, a, 1))

    return tuple(res)

@lru_cache(None)
def f(h):
    if sum(h[:2]) >= 199:
        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"

for s in range(1, 100):
    h = 99, s, 0
    if f(h) == "V1":
        print(s, "V1")

Ответ: 1