Перекладывание камней две кучи —Каталог задач по ЕГЭ - Информатика БУ

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

Задача 1#14227

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче будет $10$ камней, а в другой $8$ камней; такую позицию мы будем обозначать $(10,8)$ . За один ход из позиции $(10,8)$ можно получить любую из четырёх позиций: $(11,8)$ , $(10,9)$ , $(20,8)$ , $(10,16)$ . Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее $25$ .

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

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

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

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

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

Чтобы Ваня победил своим первым ходом, Петя должен увеличить количество камней в куче на столько, чтобы следующим ходом Ваня мог победить. Эффективнее Пете и Ване будет удваивать $S,$ чем добавлять к нему 1. При каких $S$ будет выполняться $2⋅2⋅S + 4 >= 25?$ При $S ≥ 6.$ Следовательно ответ $6.$

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 25:  # Если камней в куче стало больше 25
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1  # Выигрышный ход Пети
    else:
        return -max(moves)  # Выигрышный ход Вани


# Поиск минимального значения S для выигрыша Вани
for s in range(1, 21):
    if game(4, s + 1) == 1 or game(4, s * 2) == 1:
        print(s)  # Вывод минимального значения S
        break

Решение АР

from functools import lru_cache
def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)
@lru_cache(None)
def f(h):
    if (sum(h) >= 25):
        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, 21):
    h = 4, s
    if f(h) == ’V1’:
        print(s)
        break

Ответ: 6

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

Задача 2#14230

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч два камня или увеличить количество камней в куче в три раза. Например, пусть в одной куче будет $10$ камней, а в другой $8$ камней; такую позицию мы будем обозначать $(10,8)$ . За один ход из позиции $(10,8)$ можно получить любую из четырёх позиций: $(12,8),(10,10),(30,8),(10,24)$ . Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее $43$ .

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

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

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

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

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

Найдем такие $S,$ при которых Петя может выиграть своим первым ходом. Должно выполняться хотя бы одно из двух неравенств: $6⋅3 + S ≥ 43$ или $6+ S ⋅3 ≥ 43$ . То есть Петя может выиграть при $S ≥ 25$ или $S ≥ 13.$ Таким образом, если мы возьмем $S = 12,$ то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 43:  # Если камней в куче стало больше 43
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1  # Выигрышный ход Пети
    else:
        return -max(moves)  # Выигрышный ход Вани


# Поиск минимального значения S для выигрыша Вани
for s in range(1, 37):
    if game(6, s) == -1:
        print(s)  # Вывод минимального значения S
        break

Ответ: 12

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

Задача 3#14233

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч три камня или увеличить количество камней в куче в два раза. Например, пусть в одной куче будет 10 камней, а в другой 8 камней; такую позицию мы будем обозначать (10, 8). За один ход из позиции (10, 8) можно получить любую из четырёх позиций: (13, 8), (10, 11), (20, 8), (10, 16). Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 31.

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

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

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

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

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

Найдем такие $S,$ при которых Петя может выиграть своим первым ходом. Должно выполняться хотя бы одно из двух неравенств: $4⋅2 + S ≥ 31$ или $4+ S ⋅2 ≥ 31$ . То есть Петя может выиграть при $S ≥ 23$ или $S ≥ 14.$ Таким образом, если мы возьмем $S = 13$ или $S = 12,$ то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 31:  # Если в двух кучах камней больше или равно 31
        return 0  # Прекращаем игру
    moves = [game(first_heap + 3, second_heap), game(first_heap, second_heap + 3), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1  # Выигрышный ход Пети
    else:
        return -max(moves)  # Выигрышный ход Вани


# Поиск значения S для выигрыша Вани
for s in range(1, 27):
    if game(4, s) == -1:
        print(s)  # Вывод значения S

Ответ: 13

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

Задача 4#14236

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче будет 10 камней, а в другой 8 камней; такую позицию мы будем обозначать (10, 8). За один ход из позиции (10, 8) можно получить любую из четырёх позиций: (11, 8), (10, 9), (20, 8), (10, 16). Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 99.

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

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

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

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

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

Чтобы Ваня победил своим первым ходом, Петя должен увеличить количество камней в куче на столько, чтобы следующим ходом Ваня мог победить. Эффективнее Пете и Ване будет удваивать количество камней в первой куче, чем добавлять к ней 1. При каких $S$ будет выполняться $2⋅2 ⋅23+ S >= 99?$ При $S ≥ 7.$ Следовательно ответ $7.$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 99:  # Если камней в куче стало больше 98
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,76):
    if game(23 + 1,i) == 1 or game(23*2,i) == 1 or game(23,i + 1) == 1 or game(23,i * 2) == 1: # если в данной позиции после неудачного хода Пети есть выигрыш Вани
        print(i)
        break

Ответ: 7

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

Задача 5#14239

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч два камня или увеличить количество камней в куче в три раза. Например, пусть в одной куче будет 10 камней, а в другой 8 камней; такую позицию мы будем обозначать (10, 8). За один ход из позиции (10, 8) можно получить любую из четырёх позиций: (12, 8), (10, 10), (30, 8), (10, 24). Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 84.

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

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

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

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

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

Чтобы Ваня победил своим первым ходом, Петя должен увеличить количество камней в куче на столько, чтобы следующим ходом Ваня мог победить. Эффективнее Пете и Ване будет утраивать $S$ , чем добавлять к нему 2. При каких $S$ будет выполняться $3⋅3⋅S + 5 >= 84?$ При $S ≥ 9.$ Следовательно ответ $9.$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 84:  # Если камней в куче стало больше 83
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,79):
    if game(5+2,i) == 1 or game(5*3,i) == 1 or game(5,i+2) == 1 or game(5,i*3) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Ответ: 9

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

Задача 6#16216

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче будет $10$ камней, а в другой $8$ ; такую позицию мы будем обозначать $(10,8)$ . За один ход из позиции $(10,8)$ можно получить любую из четырёх позиций: $(11,8)$ , $(10,9)$ , $(30,8)$ , $(10,24)$ . Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее $50$ .

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

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

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

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

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

Чтобы Ваня победил своим первым ходом, Петя должен увеличить количество камней в куче на столько, чтобы следующим ходом Ваня мог победить. Эффективнее Пете и Ване будет утраивать $S$ , чем добавлять к нему $1$ . При каких $S$ будет выполняться $3+ 3⋅3 ⋅S >= 50?$ При $S ≥ 6$ . Следовательно ответ $6$ .

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 50:  # Если камней в куче стало больше 49
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,47):
    if game(3+1,i) == 1 or game(3*3,i) == 1 or game(3,i+1) == 1 or game(3,i*3) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a * 3, b), (a, b * 3)


@lru_cache(None)
def f(h):
    if sum(h) >= 50:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if any(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’


for i in range(1, 47):
    h = i, 3
    if f(h) == ’LOSE1’:
        print(i)
        break

Ответ: 6

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

Задача 7#16219

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч два камня или увеличить количество камней в куче в два раза. Например, пусть в одной куче будет $10$ камней, а в другой $8$ ; такую позицию мы будем обозначать $(10,8)$ . За один ход из позиции $(10,8)$ можно получить любую из четырёх позиций: $(12,8)$ , $(10,10)$ , $(20,8)$ , $(10,16)$ . Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее $48$ .

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

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

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

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

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

Найдем такие $S,$ при которых Петя может выиграть своим первым ходом. Должно выполняться хотя бы одно из двух неравенств: $12⋅2 +S ≥ 48$ или $12+ S ⋅2 ≥ 48$ . То есть Петя может выиграть при $S ≥ 24$ или $S ≥ 18$ . Таким образом, если мы возьмем $S = 17$ , то Петя никак не сможет выиграть первым ходом, но при этом любым своим ходом он создаст выигрышную позицию для Вани, и тогда Ваня уже гарантированно победит своим первым ходом.

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 48:  # Если камней в куче стало больше 47
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,35):
    if game(12,i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)

Решение АР

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 2, b), (a, b + 2), (a * 2, b), (a, b * 2)


@lru_cache(None)
def f(h):
    if sum(h) >= 48:
        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, 35):
    h = i, 12
    if f(h) == ’LOSE1’:
        print(i)

Ответ: 17

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

Задача 8#19042

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи гиасов. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч два гиаса или увеличить количество гиасов в куче в два раза. Например, пусть в одной куче будет $5$ гиасов, а в другой $6$ гиасов; такую позицию мы будем обозначать $(5,6)$ . За один ход из позиции $(5,6)$ можно получить любую из четырёх позиций: $(7,6),(5,8),(10,6),(5,12)$ . Игра завершается в тот момент, когда суммарное количество гиасов в кучах становится не менее $38$ .

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

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

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

Если такого значения нет, в ответ запишите $0$ .

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 38:  # Если камней в куче стало больше 37
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,33):
    if game(5+2,i) == 1 or game(5*2,i) == 1 or game(5,i+2) == 1 or game(5,i*2) == 1 : # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Ответ: 9

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

Задача 9#19045

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи сюрикенов. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один сюрикен или увеличить количество сюрикенов в куче в три раза. Например, пусть в одной куче будет $12$ сюрикенов, а в другой $10$ сюрикенов; такую позицию мы будем обозначать $(12,10)$ . За один ход из позиции $(12,10)$ можно получить любую из четырёх позиций: $(13,10),(12,11),(36,10),(12,30)$ . Игра завершается в тот момент, когда суммарное количество сюрикенов в кучах становится не менее $136$ .

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 136:  # Если камней в куче стало больше 135
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,102):
    if game(34,i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)

Ответ: 33

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

Задача 10#19048

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

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 51:  # Если камней в куче стало больше 50
        return 0  # Прекращаем игру
    moves = [game(first_heap + 3, second_heap), game(first_heap, second_heap + 3), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2), game(first_heap + 2, second_heap), game(first_heap, second_heap + 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,46):
    if game(5+3,i) == 1 or game(5*2,i) == 1 or game(5,i + 3) == 1 or game(5,i * 2) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Ответ: 12

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

Задача 11#19198

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи стикеров. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один стикер или увеличить количество стикеров в куче в два раза. Например, пусть в одной куче будет $10$ стикеров, а в другой $8$ стикеров; такую позицию мы будем обозначать $(10,8)$ . За один ход из позиции $(10,8)$ можно получить любую из четырёх позиций: $(11,8),(10,9),(20,8),(10,16)$ . Игра завершается в тот момент, когда суммарное количество стикеров в кучах становится не менее $33$ .

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

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

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

Если такого значения нет, в ответ запишите $0$ .

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 33:  # Если камней в куче стало больше 32
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,29):
    if game(4+1,i) == 1 or game(4*2,i) == 1 or game(4,i+1) == 1 or game(4,i*2) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 33:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif any(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, 29):
    print(s, game((4, s)))

Ответ: 8

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

Задача 12#19201

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи деталей. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч две детали или увеличить количество деталей в куче в три раза. Например, пусть в одной куче будет $11$ деталей, а в другой $9$ деталей; такую позицию мы будем обозначать $(11,9)$ . За один ход из позиции $(11,9)$ можно получить любую из четырёх позиций: $(13,9),(11,11),(33,9),(11,27)$ . Игра завершается в тот момент, когда суммарное количество деталей в кучах становится не менее $99$ .

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 99:  # Если камней в куче стало больше 98
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,94):
    if game(5,i) == -1: # если в данной позиции возможен выигрыш Вани первым ходом
        print(i)

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 2, b), (a, b + 2), (a * 3, b), (a, b * 3)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 99:
        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, 94):
    print(s, game((5, s)))

Ответ: 31

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

Задача 13#19204

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи фантиков. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один фантик или добавить в одну из куч два фантика или увеличить количество фантиков в куче в два раза. Например, пусть в одной куче будет $11$ фантиков, а в другой $10$ фантиков; такую позицию мы будем обозначать $(11,10)$ . За один ход из позиции $(11,10)$ можно получить любую из шести позиций: $(12,10),(11,11),(13,10),(11,12),(22,10),(11,20)$ . Игра завершается в тот момент, когда суммарное количество фантиков в кучах становится не менее $47$ .

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 47:  # Если камней в куче стало больше 46
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2), game(first_heap + 1, second_heap), game(first_heap, second_heap + 1)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,40):
    if (game(7+1,i) == 1 or game(7+2,i) == 1 or game(7*2,i) == 1 or
        game(7, i+1) == 1 or game(7, i+2) == 1 or game(7, i*2) == 1): # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 1, b), (a, b + 1),
           (a + 2, b), (a, b + 2),
           (a * 2, b), (a, b * 2)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 47:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif any(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, 40):
    print(s, game((7, s)))

Ответ: 10

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

Задача 14#19959

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 199:  # Если камней в куче стало больше 198
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap + 2, second_heap),
             game(first_heap, second_heap + 2),
             game(first_heap + first_heap - 1, second_heap), game(first_heap, second_heap + second_heap - 1)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(2,98):
    if game(97,i) == 1: # если в данной позиции возможен выигрыш Пети первым ходом
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a + 2, b), (a, b + 2), (a + a - 1, b), (a, b + b - 1)

@lru_cache(None)
def f(h):
    if sum(h) >= 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(97, 1, -1):
    h = 97, s
    if f(h) == "P1":
        print(s, "P1")

Ответ: 6

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

Задача 15#22899

Петя и Ваня после отслушки пошли в хинкальную и решили сыграть в игру. Перед ними лежат две тарелки хинкали. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из тарелок два хинкали или увеличить количество хинкалей в куче в два раза. Например, пусть в одной тарелке 8 хинкали, а в другой 10 хинкали; такую позицию мы будем обозначать (8,10). За один ход из этой позиции можно получить любую из четырёх позиций: (10,10), (8,12), (16,10), (8,20). Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество хинкали. Игра завершается в тот момент, когда суммарное количество хинкали в тарелках становится не менее 43. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в тарелках будет 43 или больше хинкали. В начальный момент в первой тарелке было 8 хинкали, во второй тарелке $S$ хинкали, $1 ≤ S ≤ 34.$

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 43:  # Если камней в куче стало больше 42
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,35):
    if game(8,i) == 1: # если в данной позиции возможен выигрыш Пети первым ходом
        print(i)
        break

Решение АР

from functools import lru_cache


def moves(h):
    a, b = h
    return (a+2, b), (a, b+2), (a*2, b), (a, b*2)


@lru_cache(None)
def f(h):
    if sum(h) >= 43:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’


for i in range(1, 35):
    h = 8, i
    if f(h) == ’WIN1’:
        print(i)
        break

Ответ: 18

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

Задача 16#23506

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

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.

Назовите минимальное значение $S$ , при котором это возможно.

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 57:  # Если камней в куче стало больше 56
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,52):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(5+1,i) == 1 or game(5*2,i) == 1 or game(5,i+1) == 1 or game(5,i*2) == 1 :
        print(i)
        break

Решение АР

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)


@lru_cache(None)
def f(h):
    if (sum(h) >= 57):
        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, 52):
    h = 5, s
    if f(h) == ’V1’:
        print(s)
        break

Ответ: 13

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

Задача 17#23687

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче будет $6$ камней, а в другой $7$ камней; такую позицию мы будем обозначать $(6,7)$ . За один ход из позиции $(6,7)$ можно получить любую из четырёх позиций: $(7,7),(6,8),(12,7),(6,14)$ . Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее $66$ .

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 66:  # Если камней в куче стало больше 65
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,55):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(11+1,i) == 1 or game(11*2,i) == 1 or game(11,i+1) == 1 or game(11,i*2) == 1:
        print(i)
        break

Ответ: 14

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

Задача 18#23690

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче будет $11$ камней, а в другой $10$ камней; такую позицию мы будем обозначать $(11,10)$ . За один ход из позиции $(11,10)$ можно получить любую из четырёх позиций: $(12,10),(11,11),(33,10),(11,30)$ . Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее $49$ .

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 49:  # Если камней в куче стало больше 48
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,44):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(5+1,i) == 1 or game(5*3,i) == 1 or game(5,i+1) == 1 or game(5,i*3) == 1 :
        print(i)
        break

Ответ: 4

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

Задача 19#23705

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

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

В начальный момент в первой куче было $7$ камней, во второй куче — $S$ камней; $1 ≤ S ≤ 69$ .

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 77:  # Если камней в куче стало больше 76
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,70):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(7+1,i) == 1 or game(7*2,i) == 1 or game(7,i+1) == 1 or game(7,i*2) == 1:
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 1, b), (a * 2, b), (a, b + 1), (a, b * 2)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 77:
        return "END"
    elif any(game(x) == "END" for x in moves(heap)):
        return "WIN1"
    elif any(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, 70):
    print(s, game((7, s)))

Ответ: 18

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

Задача 20#23708

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

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

В начальный момент в первой куче было $4$ камня, во второй куче — $S$ камней, $1 ≤ S ≤ 77$ .

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 82:  # Если камней в куче стало больше 81
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 4, second_heap),
             game(first_heap, second_heap * 4)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,78):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(4+1,i) == 1 or game(4*4,i) == 1 or game(4,i+1) == 1 or game(4,i*4) == 1:
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 1, b), (a * 4, b), (a, b + 1), (a, b * 4)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 82:
        return "END"
    elif any(game(x) == "END" for x in moves(heap)):
        return "WIN1"
    elif any(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, 77):
    print(s, game(4, s))

Ответ: 5

19.02 Перекладывание камней две кучи