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

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

Задача 1#30393

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

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

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

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

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

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

Рассмотрим $S = 57$ :

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if 64 <= heap <= 84:
        return ’END’
    elif heap > 84:
        return ’P1’
    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(63, 0, -1):
    if game(s) == ’V2’:
        print(s)
        break

Ответ: 57

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

Задача 2#30392

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

В ответе запишите количество найденных чисел.

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

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

Из предыдущего задания мы знаем все позиции $LOSE1$ . Значит нам достаточно найти все позиции, которые ведут в $LOSE1$ . Это позиции $S = 7,19,20,58,59.$

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if 64 <= heap <= 84:
        return ’END’
    elif heap > 84:
        return ’P1’
    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’


count = 0
for s in range(1, 64):
    if game(s) == ’P2’:
        print(s, end=’’)

Ответ: 5

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

Задача 3#30391

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

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

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

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

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

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

В данной задаче требуется найти позицию $LOSE1$ . Давайте перед этим найдём позиции $WIN1$ . Очевидно, что это позиции $22 ≤ S ≤ 28,$ а также позиции $S = 63$ и $S = 62$ . Значит нам подойдут значения $S = 61,60,21.$ Максимальным из них является $S = 61.$

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

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if 64 <= heap <= 84:
        return ’END’
    elif heap > 84:
        return ’P1’
    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(63, 0, -1):
    if game(s) == ’V1’:
        print(s)
        break

Ответ: 61

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

Задача 4#29368

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

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

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

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

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

from functools import lru_cache


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


@lru_cache(None)
def f(h):
    if h >= 45 and h <= 112:
        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(45, 1, -1):
    if f(i) == ’LOSE2’:
        print(i)
        break

Ответ: 38

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

Задача 5#29367

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

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

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


@lru_cache(None)
def f(h):
    if h >= 45 and h <= 112:
        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’


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

Ответ: 3

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

Задача 6#29366

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

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

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

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

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

from functools import lru_cache


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


@lru_cache(None)
def f(h):
    if h >= 45 and h <= 112:
        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(45, 1, -1):
    if f(i) == ’LOSE1’:
        print(i)
        break

Ответ: 42

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

Задача 7#27464

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

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

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

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

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

from functools import lru_cache


def moves(h):
    return h + 2, h * 3


@lru_cache(None)
def f(h):
    if h >= 45 and h <= 112:
        return ’END’
    if h > 112:
        return ’BAD’
    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 all(f(x) == ’WIN1’ or f(x) == ’BAD’ for x in moves(h)):
        return ’LOSE1 or BAD’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if any(f(x) == ’LOSE1’ or f(x) == ’LOSE1 or BAD’ for x in moves(h)):
        return ’WIN2 or WIN(BAD for opponent)’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ or f(x) == ’BAD’ or f(x) == ’WIN2 or WIN(BAD for opponent)’
           for x in moves(h)):
        return ’LOSE2 or BAD’


for i in range(45, 1, -1):
    if f(i) == ’LOSE2’ or f(i) == ’LOSE2 or BAD’:
        print(i)
        break

Ответ: 38

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

Задача 8#27463

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

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

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

from functools import lru_cache


def moves(h):
    return h + 2, h * 3


@lru_cache(None)
def f(h):
    if h >= 45 and h <= 112:
        return ’END’
    if h > 112:
        return ’BAD’
    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 all(f(x) == ’WIN1’ or f(x) == ’BAD’ for x in moves(h)):
        return ’LOSE1 or BAD’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if any(f(x) == ’LOSE1’ or f(x) == ’LOSE1 or BAD’ for x in moves(h)):
        return ’WIN2 or WIN(BAD for opponent)’


for i in range(1, 45):
    if f(i) == ’WIN2’ or f(i) == ’WIN2 or WIN(BAD for opponent)’:
        print(i, end=’’)

Ответ: 143940

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

Задача 9#27462

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

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

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

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

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

from functools import lru_cache


def moves(h):
    return h + 2, h * 3


@lru_cache(None)
def f(h):
    if h >= 45 and h <= 112:
        return ’END’
    if h > 112:
        return ’BAD’
    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 all(f(x) == ’WIN1’ or f(x) == ’BAD’ for x in moves(h)):
        return ’LOSE1 or BAD’


for i in range(45, 1, -1):
    if f(i) == ’LOSE1’ or f(i) == ’LOSE1 or BAD’:
        print(i)
        break

Ответ: 42

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

Задача 10#26073

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

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

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

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

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

from functools import lru_cache

def moves(h):
    return h + 1, h * 2, h * 3

@lru_cache(None)
def f(h):
    if h >= 43 and h <= 72:
        return ’END’
    if h > 72:
        return ’BAD’
    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 all(f(x) == ’WIN1’ or f(x) == ’BAD’ for x in moves(h)):
        return ’LOSE1 or BAD’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if any(f(x) == ’LOSE1 or BAD’ for x in moves(h)):
        return ’WIN2 or WIN(BAD for opponent)’
    if all(f(x) == ’WIN2’ or f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE2’
    if all(f(x) == ’WIN2’ or f(x) == ’WIN1’ or f(x)==’BAD’ or f(x)==’WIN2 or WIN(BAD for opponent)’
       for x in moves(h)):
        return ’LOSE2 or BAD’

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

Ответ: 12

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

Задача 11#26072

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

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

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

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

from functools import lru_cache

def moves(h):
    return h + 1, h * 2, h * 3

@lru_cache(None)
def f(h):
    if h >= 43 and h <= 72:
        return ’END’
    if h > 72:
        return ’BAD’
    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 all(f(x) == ’WIN1’ or f(x) == ’BAD’ for x in moves(h)):
        return ’LOSE1 or BAD’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if any(f(x) == ’LOSE1 or BAD’ for x in moves(h)):
        return ’WIN2 or WIN(BAD for opponent)’

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

Ответ: 2

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

Задача 12#26071

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

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

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

from functools import lru_cache

def moves(h):
    return h + 1, h * 2, h * 3

@lru_cache(None)
def f(h):
    if h >= 43 and h <= 72:
        return ’END’
    if h > 72:
        return ’BAD’
    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 all(f(x) == ’WIN1’ or f(x) == ’BAD’ for x in moves(h)):
        return ’LOSE1 or BAD’

for i in range(1, 43):
    if f(i) == ’LOSE1’ or f(i) == ’LOSE1 or BAD’:
        print(i)
        break

Ответ: 14

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

Задача 13#23813

У кого из игроков есть выигрышная стратегия при $S = 12$ ? В ответ укажите первую букву имени игрока в нижем регистре.

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

from functools import lru_cache

def moves(heap):
    return heap + 1, heap + 2, heap + 3, heap * 3

@lru_cache(None)
def game(heap):
    if 50 <= heap <= 100:
        return ’END’
    elif heap > 100:
        return ’WIN1’
    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’
    elif any(game(x) == ’LOSE2’ for x in moves(heap)):
        return ’WIN3’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ or game(x) == ’WIN3’ for x in moves(heap)):
        return ’LOSE3’
    elif any(game(x) == ’LOSE3’ for x in moves(heap)):
        return ’WIN4’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ or game(x) == ’WIN3’ or game(x) == ’WIN4’ for x in moves(heap)):
        return ’LOSE4’

print(game(12))

Ответ: с

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

Задача 14#23812

У кого из игроков есть выигрышная стратегия при $S = 13$ ? В ответ укажите первую букву имени игрока в нижем регистре.

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

from functools import lru_cache

def moves(heap):
    return heap + 1, heap + 2, heap + 3, heap * 3

@lru_cache(None)
def game(heap):
    if 50 <= heap <= 100:
        return ’END’
    elif heap > 100:
        return ’WIN1’
    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’

print(game(13))

Ответ: о

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

Задача 15#23811

Два игрока, Олаф и Свен, играют в следующую игру. Перед игроками лежит куча морковок. Игроки ходят по очереди, первый ход делает Олаф. За один ход игрок может:

a) добавить в кучу одну морковку

б) добавить в кучу две морковки

в) добавить в кучу три морковки

г) увеличить количество морковок в куче в три раза

Игра завершается в тот момент, когда количество морковок в куче становится не менее 50. Если при этом в куче оказалось не более 100 морковок, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник.

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

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

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

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

from functools import lru_cache

def moves(heap):
    return heap + 1, heap + 2, heap + 3, heap * 3

@lru_cache(None)
def game(heap):
    if 50 <= heap <= 100:
        return ’END’
    elif heap > 100:
        return ’WIN1’
    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, 50):
    if game(s) == ’LOSE1’:
        print(s)
        break

Ответ: 6

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

Задача 16#23810

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

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

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

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

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

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if 45 <= heap <= 112:
        return ’END’
    elif heap > 112:
        return ’WIN1’
    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(44, 0, -1):
    if game(s) == ’LOSE2’:
        print(s)
        break

Ответ: 38

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

Задача 17#23809

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

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

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

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if 45 <= heap <= 112:
        return ’END’
    elif heap > 112:
        return ’WIN1’
    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, 45):
    if game(s) == ’WIN2’:
        print(s)

Ответ: 143940

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

Задача 18#23808

Два игрока, Нео и Тринити, играют в следующую игру. Перед игроками лежит куча красных и синих таблеткок. Игроки ходят по очереди, первый ход делает Нео. За один ход игрок может добавить в кучу две таблетки или увеличить количество таблеток в куче в три раза. Например, имея кучу из 17 таблеток, за один ход можно получить кучу из 19 или 51 таблеток. Чтобы делать ходы, у каждого игрока есть неограниченное количество таблеток. Игра завершается в тот момент, когда количество таблеток в куче становится не менее 45. Если при этом в куче оказалось не более 112 таблеток, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник.

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

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

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

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

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if 45 <= heap <= 112:
        return ’END’
    elif heap > 112:
        return ’WIN1’
    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(44, 0, -1):
    if game(s) == ’LOSE1’:
        print(s)
        break

Ответ: 42

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

Задача 19#19973

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

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

from functools import lru_cache

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

@lru_cache(None)
def f(h):
    if sum(h) > 80:
        return "V0"
    if sum(h) >= 60:
        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" or f(x) == "V0") for x in moves(h)):
        return "V2"

for s in range(29, 0, -1):
    h = 10, 10, 10, s
    if f(h) == "V2":
        print(s, "V2")

Ответ: 1

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

Задача 20#19972

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

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

from functools import lru_cache

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

@lru_cache(None)
def f(h):
    if sum(h) > 80:
        return "V0"
    if sum(h) >= 60:
        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" or f(x) == "V0") for x in moves(h)):
        return "V2"

for s in range(29, 0, -1):
    h = 10, 10, 10, s
    if f(h) == "P2":
        print(s, "P2")

Ответ: 2