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

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

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

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

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

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

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

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

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

Очевидно, что самый сильный ход (добавление в одну из куч количество из другой) произошёл $2$ раза. Рассмотрим позицию $(5,S)$ . Петя добавляет к первой куче $S$ камней, создавая позицию $(5+ S,18)$ . После этого Ваня добавляет ко второй куче $5 + S$ камней, создавая позицию $(5 + S,5+ 2S)$ и выигрывает. При каком $S$ это возможно? При $5 + S + 5 +2S = 10 +3S ≥ 63$ , а минимальное такое целое $S$ равно 18.

Решение БУ

from functools import lru_cache

@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 63:  # Если камней в кучах стало больше 62
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+1), game(first_heap+1, second_heap),
             game(first_heap + second_heap, second_heap),game(first_heap, second_heap + first_heap)]  # Генерация всех возможных ходов
    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,58):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(5+1,i) == 1 or game(5+i,i) == 1 or game(5,i+1) == 1 or game(5,i+5) == 1:
        print(i)
        break

Решение АР

from functools import lru_cache


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


@lru_cache(None)
def game(heap):
    if sum(heap) >= 63:
        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, 58):
    if game((5, s)) == ’V1’:
        print(s)
        break

Ответ: 18

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

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

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

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

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

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

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

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

Очевидно, что при $S ≥ 94$ Петя выигрывает первым ходом, домножая кучу $S$ на $2$ . Однако при $S = 93$ Петя не выигрывает своим первым ходом, а Ваня же выигрывает при любой игре Пети. Меньшие значения S не подходят, так как ни одна из них не ведёт только в позиции выигрыша Пети первым ходом.

Решение БУ

from functools import lru_cache

@lru_cache(None)
def game(first_heap, second_heap,count_moves):  # Функция игры.
    # count_moves это счётчик ходов в партии, его мы добавили для того чтобы избежать ошибки превышения лимита рекурсии.
    # Это работает следующим образом: если в партии больше 6 ходов, то есть по три хода Пети и Вани, а партия до сих пор не завершена.
    # То такая партия нам абсолютно неинтересна, поскольку в задачах у нас просят значения, при которых Ваня или Петя побеждают максимум третьим ходом
    # Получается, что если в партии совершено много ходов, а она так и не завершилась, то мы её прерываем и начинаем просчёт другой позиции,
    # так как эта позиция нам становится неинтересной
    if first_heap * second_heap >= 2048:  # Если произведение камней в кучах стало больше 2047
        return 0  # Прекращаем игру
    if count_moves > 6: # если в игре больше 6 ходов
        return 10**10 # прерываем игру
    moves = [game(first_heap, second_heap+1,count_moves+1), game(first_heap+1, second_heap,count_moves+1),
             game(first_heap * 2, second_heap,count_moves+1),game(first_heap, second_heap * 2,count_moves+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,187):
    # если в данной позиции возможен выигрыш Вани первым ходом
    if game(11,i,0) == -1:
        print(i)
        break

Ответ: 93

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи деталей. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч две детали или увеличить количество деталей в куче в три раза. Например, пусть в одной куче будет $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, second_heap+2), game(first_heap+2, second_heap),
             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(h):
    a, b = h
    return (a + 2, b), (a, b + 2), (a * 3, b), (a, b * 3)


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


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

Ответ: 31

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

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

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

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

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

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

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

Решение БУ

from functools import lru_cache

@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 37:  # Если сумма камней в кучах стала больше 36
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+2), game(first_heap+2, second_heap),
             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,34):
    # если в данной позиции возможен выигрыш Вани первым ходом
    if game(3,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 game(h):
    if sum(h) >= 37:
        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’

for i in range(1, 34):
    if game((3, i)) == ’LOSE1’:
        print(i)

Ответ: 16

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

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

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

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

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 287:  # Если сумма камней в кучах стала больше 286
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+4), game(first_heap+4, second_heap),
             game(first_heap * 5, second_heap),game(first_heap, second_heap * 5)]  # Генерация всех возможных ходов
    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(263,0,-1):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(23+4,i) == 1 or game(23*5,i) == 1 or game(23,i+4) == 1 or game(23,i*5) == 1:
        print(i)
        break

Решение АР

from functools import lru_cache
def moves(h):
    a,b = h
    return (a+4,b),(a*5,b),(a,b+4),(a,b*5)
@lru_cache(None)
def game(h):
    a,b = h
    if a + b >= 287:return ’END’
    if any(game(x) == ’END’ for x in moves(h)):return ’WIN1’

for i in reversed(range(1,264)):
    h = (23,i)
    if any(game(x) == ’WIN1’ for x in moves(h)):
        print(i,game(h))
        break

Ответ: 259

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

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

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

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

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

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

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

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

Максимальный ход, который мы имеем в игре это $∗ 4$ , это значит, что промежуток, в котором игрок выигрывает в один ход располагается от $23$ до $90$ (количество камней во 2-ой куче).

Значит, нам нужно найти минимальное значение, при котором количество камней во 2-ой куче после неудачного хода Пети(неудачный ход в данной ситуации является ход $∗4$ ) будет находиться в промежутке, объявленном в предыдущем предложении.

Это значение будет равняться $6$ .

Решение БУ

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

Ответ: 6

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

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

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

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

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

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

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

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

Минимальное значение количества камней в обеих кучах, при котором игра заканчивается – $80$ . Эта ситуация возможна, например, когда в первой куче $8$ камней, а во второй – $72$ . Значит, чтобы Ваня мог выиграть своим первым ходом, количество камней во второй куче должно быть $≥ 36$ . После первого хода Пети во второй куче должно получиться $36$ камней. Это возможно при значении S = $18$ .

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 80:  # Если сумма камней в кучах стала больше 79
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+3), game(first_heap+3, second_heap),
             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,90):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(8+3,i) == 1 or game(8*2,i) == 1 or game(8,i+3) == 1 or game(8,i*2) == 1:
        print(i)
        break

Ответ: 18

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

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

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

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

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

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

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

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

Минимальное значение количества камней в обеих кучах, при котором игра заканчивается – $77$ . Эта ситуация возможна, например, когда в первой куче $6$ камней, а во второй – $71$ . Значит, чтобы Ваня мог выиграть своим первым ходом, количество камней во второй куче должно быть $≥ 71 = 24 3$ . После первого хода Пети во второй куче должно получиться $24$ камней. Это возможно при значении S = $8$ .

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

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, second_heap+2), game(first_heap+2, second_heap),
             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,71):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(6+2,i) == 1 or game(6*3,i) == 1 or game(6,i+2) == 1 or game(6,i*3) == 1:
        print(i)
        break

Ответ: 8

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

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

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

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

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

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

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

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

Минимальное значение количества камней в обеих кучах, при котором игра заканчивается – $89$ . Рассмотрим две ситуации, при которых возможен выигрыш Вани после неудачного хода Пети:

$3∗ 3∗ 9+ S >= 89 = 81+ S >= 89 = S >= 8 = S = 8$

$9+ 3 ∗3 ∗S >= 89 = 9S >= 80 = S >= 890= S >= 8,88 = S = 9$

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

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 89:  # Если сумма камней в кучах стала больше 88
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+1), game(first_heap+1, second_heap),
             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,80):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(9+1,i) == 1 or game(9*3,i) == 1 or game(9,i+1) == 1 or game(9,i*3) == 1:
        print(i)
        break

Ответ: 8

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

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

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

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

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

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

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

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

Минимальное значения для второй кучи для завершения игры: $77− 7 = 70$ . Промежуток, при котором игрок побеждает одним ходом, при условии, что максимальный ход $⋅2$ : $[35,70]$ . Значит, минимальное количество камней, при котором Ваня выиграет своим первым ходом после неудачного хода Пети: $18$ ( $18⋅2 = 36 ∈ [35,70]$ ).

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

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, second_heap+2), game(first_heap+2, second_heap),
             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+2,i) == 1 or game(7*2,i) == 1 or game(7,i+2) == 1 or game(7,i*2) == 1:
        print(i)
        break

Ответ: 18

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

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

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

Какое наименьшее число камней могло быть суммарно в двух кучах?

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

Возьмём минимально возможную сумму: $61$ . Пусть в одной куче был $1$ камень, тогда, во второй куче камней было от $30$ до $59$ . Так как нам необходимо минимальное количество камней, то берем число $30$ . Общая сумма: $1 + 30 = 31$ .

Программная реализация:

from functools import lru_cache
@lru_cache(None)
def f(a,b,c = 0):
    if a+b >= 61:
        return 0
    if c > 2:
        return 10000
    if a > b: t = [f(a+i,b,c+1) for i in range(1, a+1)]
    else: t = [f(a,b+i,c+1) for i in range(1, b+1)]
    n = [i for i in t if i <= 0]
    if n:
        return -max(n) + 1
    return -max(t)
ans = []
for i in range(1,61):
    for j in range(1,61):
        if f(i,j) == 1:
            ans += [i+j]
print(min(ans))

Ответ: 31

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

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Ваня. За один ход игрок может добавить в одну из куч два камня, пять камней, семь камней или увеличить количество камней в куче в три раза. Но нельзя повторять последний ход соперника, то есть нельзя в одну и ту же кучу добавлять столько же камней, что и противник своим последним ходом. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 201. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 16 камней, во второй куче – S камней, 1 $≤$ S $≤$ 150. Известно, что Петя выиграл своим первым ходом после неудачного хода Вани.

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

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

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap,last_move = ""):  # Функция игры.
    # last_move - это переменная для хранения данных о том, в какую кучу какой ход был последний ход.
    # Например, 1_+5 - это ход +5 в 1-ую кучу.
    if first_heap + second_heap >= 201:  # Если сумма камней в кучах стала больше 200
        return 0  # Прекращаем игру
    moves = []  # Список возможных ходов в партии
    if last_move == "": # Если это первый ход в партии (то есть нет предыдущего хода)
        # тогда мы можем использовать любой ход
        moves = [game(first_heap+5,second_heap,"1_+5"),game(first_heap,second_heap+5,"2_+5"),
                 game(first_heap+7,second_heap,"1_+7"),game(first_heap,second_heap+7,"2_+7"),
                 game(first_heap+2,second_heap,"1_+2"),game(first_heap,second_heap+2,"2_+2"),
                 game(first_heap*3,second_heap,"1_*3"),game(first_heap,second_heap*3,"2_*3")]  # Генерация всех возможных ходов
    elif last_move == "1_+5": # если последний ход это +5 в 1-ую кучу
        # тогда мы можем использовать любой ход, кроме этого
        moves = [game(first_heap, second_heap + 5, "2_+5"),
                 game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
                 game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
                 game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
    elif last_move == "2_+5": # если последний ход это +5 в 2-ую кучу
        # тогда мы можем использовать любой ход, кроме этого
        moves = [game(first_heap + 5, second_heap, "1_+5"),
                 game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
                 game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
                 game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
    elif last_move == "1_+7": # если последний ход это +7 в 1-ую кучу
        # тогда мы можем использовать любой ход, кроме этого
        moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
                 game(first_heap, second_heap + 7, "2_+7"),
                 game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
                 game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
    elif last_move == "2_+7": # если последний ход это +7 в 2-ую кучу
        # тогда мы можем использовать любой ход, кроме этого
        moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
                 game(first_heap + 7, second_heap, "1_+7"),
                 game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
                 game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
    elif last_move == "1_+2": # если последний ход это +2 в 1-ую кучу
        # тогда мы можем использовать любой ход, кроме этого
        moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
                 game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
                                                                                                  
                                                                                                  
                 game(first_heap, second_heap + 2, "2_+2"),
                 game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
    elif last_move == "2_+2": # если последний ход это +2 в 2-ую кучу
        # тогда мы можем использовать любой ход, кроме этого
        moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
                 game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
                 game(first_heap + 2, second_heap, "1_+2"),
                 game(first_heap * 3, second_heap, "1_*3"), game(first_heap, second_heap * 3, "2_*3")]
    elif last_move == "1_*3": # если последний ход это *3 в 1-ую кучу
        # тогда мы можем использовать любой ход, кроме этого
        moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
                 game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
                 game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
                 game(first_heap, second_heap * 3, "2_*3")]
    elif last_move == "2_*3": # если последний ход это *3 в 2-ую кучу
        # тогда мы можем использовать любой ход, кроме этого
        moves = [game(first_heap + 5, second_heap, "1_+5"), game(first_heap, second_heap + 5, "2_+5"),
                 game(first_heap + 7, second_heap, "1_+7"), game(first_heap, second_heap + 7, "2_+7"),
                 game(first_heap + 2, second_heap, "1_+2"), game(first_heap, second_heap + 2, "2_+2"),
                 game(first_heap * 3, second_heap, "1_*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,151):
    # если в данной позиции после неудачного хода Вани возможен выигрыш Пети
    if game(16*3,i,"1_*3") == 1 or game(16,i*3,"2_*3") == 1:
        print(i)
        break

Ответ: 51

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

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

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

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

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

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

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

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

Минимальное количество камней в обоих кучах, при котором игра заканчивается в два хода (то есть победой Вани) – 95. Такая ситуация возможна, когда в первой куче 6 камней, а во второй – 89. Чтобы Ваня мог выиграть своим первым ходом, количество камней во второй куче должно быть $≥ 30$ . После первого хода Пети во второй куче должно получиться 30 камней. Это возможно при минимальном значении $S = 10$ .

При $S = 10$ Ваня выиграет своим первым ходом после неудачного хода Пети.

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 95:  # Если сумма камней в кучах стала больше 94
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+2), game(first_heap+2, second_heap),
             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,89):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(6+2,i) == 1 or game(6*3,i) == 1 or game(6,i+2) == 1 or game(6,i*3) == 1:
        print(i)
        break

Ответ: 10

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

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

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

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

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

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

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

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

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

Минимальное значение камней во второй куче, при котором партия завершается равняется: $74− 12 = 62$ (камня).

Максимальный ход, который мы имеем в игре это $∗ 2$ , это значит, что промежуток для второй кучи, в котором игрок выигрывает в один ход располагается от $31$ до $62$ .

Значит, нам нужно найти минимальное значение, при котором количество камней в куче после хода Пети будет находиться в промежутке, объявленном в предыдущем предложении. Это значение будет равняться $16$ .

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 74:  # Если сумма камней в кучах стала больше 73
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+1), game(first_heap+1, second_heap),
             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,62):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(12+1,i) == 1 or game(12*2,i) == 1 or game(12,i+1) == 1 or game(12,i*2) == 1:
        print(i)
        break

Ответ: 16

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

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

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

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 85:  # Если сумма камней в кучах стала больше 84
        return 0  # Прекращаем игру
    moves = []  # Список всех возможных ходов
    if first_heap > second_heap: # если камней в первой куче больше чем во второй
        # то добавляем камни только во вторую кучу
        moves = [game(first_heap,second_heap+3),game(first_heap,second_heap+6),game(first_heap,second_heap*2)] # Генерация ходов
    else: # иначе если во второй куче камней больше чем в первой или количество камней в кучах равно
        # то добавляем камни только во первую кучу
        moves = [game(first_heap+ 3, second_heap ), game(first_heap+ 6, second_heap ),
                 game(first_heap* 2, second_heap)] # Генерация ходов
    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 15 > i:
        # если в данной ситуации после неудачного хода Пети возможен выигрыш Вани
        if game(15,i+3) == 1 or game(15,i+6) == 1 or game(15,i*2) == 1:
            print(i)
            break
    else:
        # если в данной ситуации после неудачного хода Пети возможен выигрыш Вани
        if game(15+3,i) == 1 or game(15+6,i) == 1 or game(15*2,i) == 1:
            print(i)
            break

Ответ: 28

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

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

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

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

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

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

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

Решение БУ

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

Ответ: 7

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

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

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 93:  # Если сумма камней в кучах стала больше 92
        return 0  # Прекращаем игру
    moves = []  # Список всех возможных ходов
    if first_heap > second_heap: # если камней в первой куче больше чем во второй
        # то добавляем камни только во вторую кучу
        moves = [game(first_heap,second_heap+4),game(first_heap,second_heap*2),game(first_heap,second_heap*3)] # Генерация ходов
    else: # иначе если во второй куче камней больше чем в первой или количество камней в кучах равно
        # то добавляем камни только во первую кучу
        moves = [game(first_heap+ 4, second_heap ), game(first_heap*2, second_heap ),
                 game(first_heap* 3, second_heap)] # Генерация ходов
    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,84):
    if 9 > i:
        # если в данной ситуации после неудачного хода Пети возможен выигрыш Вани
        if game(9,i+4) == 1 or game(9,i*2) == 1 or game(9,i*3) == 1:
            print(i)
            break
    else:
        # если в данной ситуации после неудачного хода Пети возможен выигрыш Вани
        if game(9+4,i) == 1 or game(9*2,i) == 1 or game(9*3,i) == 1:
            print(i)
            break

Ответ: 22

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

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

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 74:  # Если сумма камней в кучах стала больше 73
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+4), game(first_heap+4, second_heap),
             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,64):
    # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
    if game(10+4,i) == 1 or game(10,i+4) == 1 or game(10*2,i) == 1 or game(10,i*2) == 1:
        print(i)
        break

Ответ: 16

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

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

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

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

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

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

Какое наименьшее число камней могло быть суммарно в двух кучах?

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

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 109:  # Если сумма камней в кучах стала больше 108
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+7), game(first_heap+7, second_heap),
             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,97):
    # если в данной позиции возможен выигрыш Пети первым ходом
    if game(12,i) == 1:
        print(i+12)
        break

Ответ: 45

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

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры.
    if first_heap + second_heap >= 79:  # Если сумма камней в кучах стала больше 78
        return 0  # Прекращаем игру
    moves = [game(first_heap, second_heap+2), game(first_heap+2, second_heap),
             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(9+2,i) == 1 or game(9,i+2) == 1 or game(9*2,i) == 1 or game(9,i*2) == 1:
        print(i)
        break

Ответ: 18