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

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

Задача 1#19956

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

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

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

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

from functools import lru_cache

# c = 1 если в прошлый ход меняли кучи местами
def moves(h):
    a, b, c = h
    res = []

    res.append((a, b * 2, 0))
    if c == 0:
        res.append((b, a, 1))

    return tuple(res)

@lru_cache(None)
def f(h):
    if sum(h[:2]) >= 199:
        return "END"
    if any((f(x) == "END") for x in moves(h)):
        return "P1"
    if any((f(x) == "P1") for x in moves(h)):
        return "V1"

for s in range(1, 100):
    h = 99, s, 0
    if f(h) == "V1":
        print(s, "V1")

Ответ: 1

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

Задача 2#25911

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней в куче в три раза, добавить в кучу один камень, или 3 камня, при этом после каждого хода в куче должно быть нечетное количество камней. Например, пусть в куче было 8 камней. Тогда за один ход можно получить кучу из 9 камней или из 11 камней (увеличить количество камней в три раза нельзя, т.к. после этого хода получится четное количество камней – 24). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 51.

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

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

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

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


def f(h):
    if h >= 51:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if any(f(x) == ’P1’ for x in moves(h)) and len(moves(h)) >= 2:
        return ’V1’


for i in range(1, 51):
    if f(i) == ’V1’:
        print(i)
        break

Ответ: 14

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

Задача 3#28815

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

Например, если в начале игры в куче $3$ камня, Петя может первым ходом получить кучу из $4,5$ или $9$ камней. Если Петя получил кучу из $5$ камней (добавил $2$ камня), то следующим ходом Ваня может получить $6$ или $15$ камней. Получить $7$ камней Ваня не может, так как для этого нужно добавить $2$ камня, а такой ход только что сделал Петя.

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

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

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

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

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

from functools import lru_cache

def moves(h):
    k = h[0]
    m = h[1]
    if m == 0:
        return (k + 1, 1), (k + 2, 2), (k * 3, 3)
    if m == 1:
        return (k + 2, 2), (k * 3, 3)
    if m == 2:
        return (k + 1, 1), (k * 3, 3)
    if m == 3:
        return (k + 1, 1), (k + 2, 2)

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

for i in range(1, 43):
    h = i, 0
    if f(h) == ’LOSE1’:
        print(i)

Ответ: 14

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

Задача 4#30400

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

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

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

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

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

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

Для начала найдём все позиции типа $WIN1$ . Это позиции $S = 60,$ $S = 62$ и все нечётные позиции $S ≥ 21.$ Тогда из позиции $S = 7$ Петя может сходить только в $S = 21$ и Ваня также умножит количество камней в куче на $3$ и победит.

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

from functools import lru_cache


def moves(heap):
    m = []
    if (heap + 1) % 2 != 0:
        m += [heap + 1]
    if (heap + 3) % 2 != 0:
        m += [heap + 3]
    if (heap * 3) % 2 != 0:
        m += [heap * 3]
    return m


@lru_cache(None)
def game(heap):
    if heap >= 63:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’


for s in range(1, 63):
    if game(s) == ’LOSE1’:
        print(s)
        break

Ответ: 7

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

Задача 5#30406

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

Например, если в начале игры в куче $3$ камня, Петя может первым ходом получить кучу из $4,5$ или $9$ камней. Если Петя получил кучу из $5$ камней (добавил $2$ камня), то следующим ходом Ваня может получить $6$ или $15$ камней. Получить $7$ камней Ваня не может, так как для этого нужно добавить $2$ камня, а такой ход только что сделал Петя.

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

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

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

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

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

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

Для начала найдём все позиции $WIN1$ . Это позиции $S ≥ 17.$ Рассмотрим позицию $S = 16.$ Из неё Петя утроением камней достигнет позиции $S = 48,$ из которой Ваня выиграет добавив в кучу $2$ камня.

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

from functools import lru_cache


def moves(heap):
    h, k = heap
    m = []
    if k != 0:
        m += [(h + 1, 0)]
    if k != 1:
        m += [(h + 2, 1)]
    if k != 2:
        m += [(h * 3, 2)]
    return m


@lru_cache(None)
def game(heap):
    if heap[0] >= 50:
        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, 50):
    if game((s, -1)) == ’V1’:
        print(s)

Ответ: 16

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

Задача 6#56420

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

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

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

Решение

Максимальный ход, который мы имеем в игре это +15, это значит, что промежуток, в котором игрок выигрывает в один ход располагается от 76 до 91(по сумме количества камней в кучах).

Значит, Ваня выиграет первым ходом, если после хода Пети сумма камней в кучах будет находится в определённом ранее промежутке.

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

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

from functools import lru_cache
lru_cache(None)
def f(a,b,c = 0):# Параметр ’с’ в этой программе - это счётчик,сделанных ходов в данной партии.
    # В данной задаче он обязателен,поскольку изначальное кол-во камней может быть слишком мало,а также есть ходы,которые не так сильно увеличивают кол-во камней в куче(+2,+5),как,например ход (+15).
    # По этой причине у нас может возникнуть ошибка,связанная с превышением глубины рекурсии или же программа будет слишком долго высчитывать значения.
    if a+b >= 91:
        return 0
    if c > 10:
        return 1000
    if a < b:
        t = [f(a+2,b,c+1),f(a+5,b,c+1),f(a+15,b,c+1)]
    else:
        t = [f(a,b+2,c+1),f(a,b+5,c+1),f(a,b+15,c+1)]
    n = [i for i in t if i <= 0]
    if n:
        return -max(n) + 1
    return -max(t)
for i in range(1,61):
    if f(15,i) == -1:
        print(i)

Ответ: 5960

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

Задача 7#64026

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить три камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок. Например, если в начале игры в куче 4 камня, Петя может первым ходом получить кучу из 5, 7 или 12 камней. Если Петя добавил 1 камень и получил кучу из 5 камней, то следующим ходом Ваня может либо добавить 3 камня (и получить 8 камней), либо утроить количество камней в куче (их станет 15). Получить 6 камней Ваня не может, так как для этого нужно добавить 1 камень, а такой ход только что сделал Петя. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

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

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

# s — кол-во камней,
# m — кол-во оставшихся доступных ходов
# (чётное изначальное m фактически означает требование к победе Вани,
#  нечётное — к победе Пети, ниже разберём, к чему),
# last — какой ход был предыдущим
def f(s,m,last = ’’):
    # Если возникло нужное кол-во камней — выясняем, победил ли наш фаворит
    # Работает это так: если победа настала после m ходов,
    # то остаток от деления на 2 будет 0, значит фаворит победил;
    # Но если победа настала раньше, разбираем следующим путём: глядя на вызываемые функции, видим, что значение m уменьшается на 1.
    # Чтобы победил Петя, нужно, чтобы прошло нечётное количество ходов,
    # таким образом, разность нечётных чисел(m и количество случившихся ходов) даёт нам чётный результат.
    # Чтобы победил Ваня, соответственно, нужно, чтобы прошло чётное количество ходов,
    # что даёт нам чётный результат при разности m и количества случившихся ходов(то есть здесь оба числа чётные),
    # отсюда и проверка на чётность.
    if s >= 100:return m % 2 == 0

    # Если m ходов прошло, а победителя нет — завершаем.
    if m == 0:return 0

    # Здесь формируем списки ходов, исходя из последнего хода противника
    if last == ’’:h = [f(s+1,m-1,’+1’),f(s+3,m-1,’+3’),f(s*3,m-1,’+3’)]
    if last == ’+1’:h = [f(s+3,m-1,’+3’),f(s*3,m-1,’+3’)]
    if last == ’+3’:h = [f(s+1,m-1,’+1’),f(s*3,m-1,’*3’)]
    if last == ’*3’:h = [f(s+1,m-1,’+1’),f(s+3,m-1,’+3’)]

    # any(h) — для ходов фаворита, где нам важен хотя бы один выигрышный ход,
    # all(h) — для ходов соперника, где нам важно, чтобы при любом его ходе фаворит имел выигрышную стратегию
    return any(h) if (m-1) %2 == 0 else all(h)

# Перебор количества камней
print([s for s in range(1,100) if f(s,2)])

Ответ: 33

19.05 Ограничение по ходам