21. Теория игр - Каталог заданий по ЕГЭ - Информатика БУ в Школково

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

Задача 21#19206Максимум баллов за задание: 1

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

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

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

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

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

Решение БУ

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,i) == -2: # если в данной позиции возможен выигрыш Вани вторым ходом
        print(i)

Решение АР

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 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, 40):
    print(s, game((7, s)))

Ответ: 18

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

Задача 22#19952Максимум баллов за задание: 1

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

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

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

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if (a + b) <= 12:
        return 0
    moves = []
    if a - 2 >= 0:
        moves.append(f(a - 2, b))
    if b - 2 >= 0:
        moves.append(f(a, b - 2))
    if a > 0:
        moves.append(f(a // 2, b))
    if b > 0:
        moves.append(f(a, b // 2))
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    return -max(moves)


for i in range(1, 100):
    if f(25, i) == -2:
        print(i)

Ответ: 4 5

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

Задача 23#19955Максимум баллов за задание: 1

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

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

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

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if (a + b) <= 75:
        return 0
    moves = []
    if a - 3 >= 0:
        moves.append(f(a - 3, b))
    if b - 3 >= 0:
        moves.append(f(a, b - 3))
    if a > 0:
        moves.append(f(a // 5, b))
    if b > 0:
        moves.append(f(a, b // 5))
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    return -max(moves)


for i in range(50, 101):
    if f(100, i) == -2:
        print(i)

Ответ: 60

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

Задача 24#19958Максимум баллов за задание: 1

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

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

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

from functools import lru_cache


@lru_cache(None)
def f(a, b, c):
    if a + b >= 199:
        return 0
    moves = [f(a, b * 2, c)]
    if c == 0:
        moves.append(f(b, a, 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, 100):
    if f(99, i, 0) == -2:
        print(i)

Ответ: 7 8

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

Задача 25#19961Максимум баллов за задание: 1

Найдите такое $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) == -2: # если в данной позиции возможен выигрыш Вани вторым ходом
        print(i)

Решение АР

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) == "V2":
        print(s, "V2")

Ответ: 2

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

Задача 26#19964Максимум баллов за задание: 1

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

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

Программное решение

from functools import lru_cache


@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры

    # Если суммарное кол-во камней в кучах стало более 70
    if first_heap + second_heap > 70:
        # Возвращаем 1,
        # которая преобразуется в победу Вани первым ходом из-за "плохого" хода Пети
        return 1

    # Если суммарное кол-во камней в кучах стало не менее 50
    if first_heap + second_heap >= 50:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [
        game(first_heap + 1, second_heap),
        game(first_heap * 2, second_heap),
        game(first_heap, second_heap + 1),
        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 S in range(1, 29 + 1):
    # Если в данной позиции Петя гарантированно выигрывает своим вторым ходом
    if game(20, S) == -2:
        print(S)

Ответ: 6

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

Задача 27#19967Максимум баллов за задание: 1

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

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

from functools import lru_cache


@lru_cache(None)
def f(first_heap, second_heap, third_heap):
    if first_heap + second_heap + third_heap >= 70:
        return 0
    moves = [f(first_heap + 1, second_heap, third_heap), f(first_heap, second_heap + 1, third_heap),
             f(first_heap, second_heap, third_heap + 1),
             f(first_heap * 2, second_heap, third_heap), f(first_heap, second_heap * 2, third_heap),
             f(first_heap, second_heap, third_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, 40):
    if f(20, 10, i) == -2:
        print(i)

Ответ: 16

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

Задача 28#19970Максимум баллов за задание: 1

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

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

from functools import lru_cache


@lru_cache(None)
def f(first_heap, second_heap, third_heap, fourth_heap):
    if first_heap + second_heap + third_heap + fourth_heap >= 70:
        return 0
    moves = [f(first_heap + 2, second_heap, third_heap, fourth_heap),
             f(first_heap, second_heap + 2, third_heap, fourth_heap),
             f(first_heap, second_heap, third_heap + 2, fourth_heap),
             f(first_heap, second_heap, third_heap, fourth_heap + 2),
             f(first_heap * 3, second_heap, third_heap, fourth_heap),
             f(first_heap, second_heap * 3, third_heap, fourth_heap),
             f(first_heap, second_heap, third_heap * 3, fourth_heap),
             f(first_heap, second_heap, third_heap, fourth_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, 40):
    if f(9, 6, 8, i) == -2:
        print(i)

Ответ: 14

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

Задача 29#19973Максимум баллов за задание: 1

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

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

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(heap_1, heap_2, heap_3, heap_4):  # Функция игры

    # Если суммарное кол-во камней в кучах стало более 80
    if heap_1 + heap_2 + heap_3 + heap_4 > 80:
        # Возвращаем 1,
        # которая преобразуется в победу Вани первым ходом из-за "плохого" хода Пети
        return 1

    # Если суммарное кол-во камней в кучах стало не менее 60
    if heap_1 + heap_2 + heap_3 + heap_4 >= 60:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [
        game(heap_1 + 2, heap_2, heap_3, heap_4), game(heap_1 * 3, heap_2, heap_3, heap_4),
        game(heap_1, heap_2 + 2, heap_3, heap_4), game(heap_1, heap_2 * 3, heap_3, heap_4),
        game(heap_1, heap_2, heap_3 + 2, heap_4), game(heap_1, heap_2, heap_3 * 3, heap_4),
        game(heap_1, heap_2, heap_3, heap_4 + 2), game(heap_1, heap_2, heap_3, heap_4 * 3)
    ]

    # Находим значения, через которые может победить Петя
    petya_win = [i for i in moves if i <= 0]

    if petya_win:  # Если такие значения нашлись и список не пуст
        return -max(petya_win) + 1
    else:  # Иначе побеждает Ваня максимальным ходом
        return -max(moves)


for S in range(1, 29 + 1):
    # Если в данной позиции Ваня гарантированно выигрывает своим вторым ходом
    if game(10, 10, 10, S) == -2:
        print(S)
        break  # Первое выведенное значение будет минимальным

Решение АР

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

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

Задача 30#19976Максимум баллов за задание: 1

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

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

from functools import lru_cache


@lru_cache(None)
def f(x_coord, y_coord):
    if (x_coord ** 2 + y_coord ** 2) ** 0.5 > 20:
        return 0
    moves = [f(x_coord + 1, y_coord + 2), f(x_coord, y_coord + 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, 18):
    if f(10, i) == -2:
        print(i)
        break

Ответ: 11

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

Задача 31#19979Максимум баллов за задание: 1

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

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

from functools import lru_cache


@lru_cache(None)
def f(x_coord, y_coord):
    if (x_coord ** 2 + y_coord ** 2) ** 0.5 > 30:
        return 0
    moves = [f(x_coord + 1, y_coord + 2), f(x_coord, y_coord + 1), f(x_coord + 10, y_coord + 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, 26):
    if f(15, i) == -2:
        print(i)
        break

Ответ: 10

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

Задача 32#22901Максимум баллов за задание: 1

Для игры, описанной ранее, найдите четыре таких значения $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) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        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) >= 43:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’


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

Ответ: 9101516

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

Задача 33#23508Максимум баллов за задание: 1

Укажите минимальное значение $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,i) == -2: # если в данной позиции возможен выигрыш Вани вторым ходом
        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 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) == ’P1’ or f(x) == ’P2’ for x in moves(h)):
        return ’V2’


for s in range(1, 52):
    h = 5, s
    if f(h) == ’V2’:
        print(s)
        break

Ответ: 22

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

Задача 34#23623Максимум баллов за задание: 1

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

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

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

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

Из $S = 49$ Петя может попасть либо в $50$ , либо в $59$ . Любой ход из данной позиции приведет Ваню к гарантированному выигрышу своим вторым ходом.

Из $S = 58$ Петя может попасть либо в $59$ , либо в $68$ . Из позиции $68$ Ваня легко выигрывает, добавляя $10$ камней.

При наличии в куче $59$ камней Ване достаточно добавить один камень и получить $60$ камней. Петя сможет увеличить количество камней либо до $61$ , либо до $70$ , откуда Ване достаточно прибавить $10$ к любому из этих значений. Нам нужно взять максимальное значение S. Ответ: $58$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 71: # если камней в куче стало больше 70
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+10)] # прописываем ходы возможные в партии
    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,71):
    if game(i) == -2: # если в данной позиции Ваня побеждает вторым ходом
        print(i)

Ответ: 58

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

Задача 35#23629Максимум баллов за задание: 1

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

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

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

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

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

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

Из предыдущего задания мы знаем, что при значениях S равных $17$ и $18$ Петя гарантированно побеждает своим вторым ходом. Значение, из которого гарантированно попасть в $17$ или $18$ ,или в область [20;38] будет значением, из которого Ваня гарантированно победит своим вторым ходом. Распишем значение и стратегии, в которых Ваня побеждает своим вторым ходом:

При $S = 16$ Петя может попасть в позиции $17$ , $18$ и $32$ . При $S = 32$ Ваня просто может удвоить количество камней и выиграть. В иных случаях он может прийти в позицию $19$ , после чего произойдет ситуация, описанная в предыдущем задании, где теперь Ваня победит.

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 39: # если камней в куче стало больше 38
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+2),game(first_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,38):
    if game(i) == -2: # если в данной позиции Ваня побеждает вторым ходом
        print(i)

Ответ: 16

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

Задача 36#23632Максимум баллов за задание: 1

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

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

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

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

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

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

Из предыдущего задания мы знаем, что при значениях $6$ , $13$ , $14$ , $15$ , $16$ Петя гарантированно побеждает своим вторым ходом и при значениях [19;54] Петя гарантированно побеждает своим первым ходом. Значение, из которого ВСЕ первые ходы Пети ведут к значениям, описанными выше приводят к победе Вани вторым ходом или первым при неудачной игре Пети. Распишем подробно значение и стратегии, при которых Ваня побеждает своим вторым ходом:

$S = 11$ . Петя может увеличить количество камней до $13$ , $15$ или $33$ . При $13$ и $15$ камнях Ваня побеждает гарантированно своим вторым ходом, при $33$ камнях Ваня побеждает своим первым ходом.

$S = 12$ . Тогда Петя может увеличить количество камней до $14$ , $16$ или $36$ . Если в куче будет $36$ камней, то Ваня просто увеличит их количество в $3$ раза, тем самым выиграет. При значениях $14$ и $16$ Ваня может попасть в $18$ , тем самым разыграв ситуацию, которая была описана в предыдущем задании, и победит.

В ответ нужно указать максимальное значение S. Ответ: $12$ .

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 55: # если камней в куче стало больше 54
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap+4),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,54):
    if game(i) == -2: # если в данной позиции Ваня побеждает вторым ходом
        print(i)

Ответ: 12

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

Задача 37#23635Максимум баллов за задание: 1

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

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

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

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

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

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

Из предыдущего задания мы знаем, что при значениях $7$ , $17$ , $18$ , $19$ , $20$ Петя побеждает гарантированно своим вторым ходом и при значениях [23;67] Петя побеждает своим первым ходом. Значение, из которого ВСЕ первые ходы Пети ведут в значения, описанные выше – это значение, при котором Ваня побеждает своим вторым ходом. Рассмотрим значение и стратегии, при которых Ваня побеждает своим вторым ходом или первым при неудачном ходе Пети:

$S = 15$ . Тогда Петя может увеличить количество камней до $17$ , $19$ или $45$ . Если в куче будет $45$ камней, то Ваня просто увеличит их количество в $3$ раза, тем самым попадет в позицию $135$ и выиграет.

$S = 16$ . Тогда Петя может увеличить количество камней до $18$ , $20$ или $48$ . Если в куче будет $48$ камней, то Ваня просто увеличит их количество в $3$ раза, тем самым попадет в позицию $144$ и выиграет.

В ответ нужно указать максимальное значение S. Ответ: $16$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 68: # если камней в куче стало больше 67
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap+4),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,68):
    if game(i) == -2: # если в данной позиции Ваня побеждает вторым ходом
        print(i)

Ответ: 16

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

Задача 38#23683Максимум баллов за задание: 1

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

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

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

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

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

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

Из предыдущих заданий мы знаем, что в значениях $5$ , $6$ Петя гарантированно побеждает своим вторым ходом и в отрезке значений [9;26] Петя побеждает своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанные значения – это значение, в котором Ваня гарантированно побеждает своим вторым ходом. Распишем значения и стратегии, в которых Ваня побеждает своим вторым ходом:

Возьмём $S = 3$ . Петя может прийти в $5$ и $9$ . Из $9$ Ваня сразу сможет сходить в $27$ , завершив игру победой. Из $5$ же повторится игра из предыдущего задания, только уже по отношению к Ване.

Возьмем $S = 4$ . Петя может прийти в $6$ и $12$ . Из $12$ Ваня сразу сможет сходить в >= $27$ , завершив игру победой. Из $6$ же повторится игра из предыдущего задания, только уже по отношению к Ване.

Ответ: $34$

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 27: # если камней в куче стало больше 26
        return 0 # прекращаем игру
    moves = [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,27):
    if game(i) == -2: # если в данной позиции Ваня побеждает вторым ходом
        print(i)

Решение АР

from functools import lru_cache
def moves(h):
    return (h+2), (h*3)
@lru_cache(None)
def game(h):
    if h >= 27:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    elif all(game(x) == ’WIN2’ or game(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE2’
for s in range(1, 27):
    if game(s) == ’LOSE2’:
        print(s)

Ответ: 34

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

Задача 39#23686Максимум баллов за задание: 1

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

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

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

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

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

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

Из предыдущих заданий мы знаем, что в значениях $3$ , $5$ , $7$ , $8$ Петя побеждает своим вторым ходом и в отрезке значений [11;30] Петя побеждает своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанные значения – это значение, в котором Ваня гарантированно побеждает своим вторым ходом или первым ходом при неудачной игре. Распишем значение и стратегии, при которых Ваня побеждает своим вторым ходом:

$S = 6$ . Петя может увеличить количество камней до $8$ , $12$ или $18$ камней. В первом случае, Ваня победит своим вторым ходом. В оставшихся случаях, Ваня победит первым ходом.

Ответ: $6$

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 31: # если камней в куче стало больше 30
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap*3),game(first_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,31):
    if game(i) == -2: # если в данной позиции Ваня побеждает вторым ходом
        print(i)

Ответ: 6

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

Задача 40#23689Максимум баллов за задание: 1

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

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

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

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

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

Решение БУ

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,i) == -2:
        print(i)

# Таких значений нет - в ответ указываем 0

Ответ: 0