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

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

Задача 1#19962

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

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

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

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

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) > 70:
        return "V0"
    if sum(h) >= 50:
        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(1, 30):
    h = 20, s
    if f(h) == "P1":
        print(s, "P1")
        break

Ответ: 10

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

Задача 2#19971

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

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

Известно, что Петя выиграл своим первым ходом. Назовите минимальное значение $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) == "P1":
        print(s, "P1")

Ответ: 10

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

Задача 3#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

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

Задача 4#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

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

Задача 5#26071

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

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

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

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(first_heap):  # Функция игры
    if first_heap > 72:  # Если камней в куче стало более 72
        return 1  # Возвращаем 1, означающую победу Вани "первым ходом" из-за плохого хода Пети
    if first_heap >= 43:  # Если камней в куче стало не менее 43
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1), game(first_heap * 2), game(first_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, 42 + 1):
    if game(i) == -1:  # Если в данной позиции Ваня гарантированно выигрывает своим первым ходом
        print(i)
        break  # Первое выведенное значение будет минимальным

Решение АР

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

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

Задача 6#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

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

Задача 7#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

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

Задача 8#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

19.06 Условие проигрыша