Е19-21.40 когда количество камней в куче становится не менее 58

Администратор

2 года назад

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

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

ЕГЭ по информатике Основная волна 08.06.2024 kompege.ru – задание №19-21

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

Ответ:

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

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

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

Ответ:

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

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

Если найдено несколько значений S, в ответе запишите наименьшее из них.

Ответ:

Решение на Python

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

def f(s, m):
    if s>=58: return m%2==0
    if m==0: return 0
    h= [f(s+1, m-1), f(s+4,m-1), f(s*2,m-1)]
    return any(h) if (m-1)%2==0 else all(h)
print('19)', [s for s in range(1, 58) if f(s, 2)])
print('20)', [s for s in range(1, 58) if not f(s, 1) and f(s, 3)])
print('21)', [s for s in range(1, 58) if not f(s, 2) and f(s, 4)])

def f(s, m):

if s>=58: return m%2==0

if m==0: return 0

h= [f(s+1, m-1), f(s+4,m-1), f(s*2,m-1)]

return any(h) if (m-1)%2==0 else all(h)

print('19)', [s for s in range(1, 58) if f(s, 2)])

print('20)', [s for s in range(1, 58) if not f(s, 1) and f(s, 3)])

print('21)', [s for s in range(1, 58) if not f(s, 2) and f(s, 4)])

19) [28]
20) [14, 24, 27]
21) [23, 26]

Объяснение кода

Функция f(s, m) определяет, есть ли выигрышная стратегия для текущего игрока с параметрами s и m:


def f(s, m):
    if s >= 58:
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(s + 1, m - 1), f(s + 4, m - 1), f(s * 2, m - 1)]
    return any(h) если (m - 1) % 2 == 0, иначе all(h)

def f(s, m):

if s >= 58:

return m % 2 == 0

if m == 0:

return 0

h = [f(s + 1, m - 1), f(s + 4, m - 1), f(s * 2, m - 1)]

return any(h) если (m - 1) % 2 == 0, иначе all(h)

if s >= 58: return m % 2 == 0: Если количество камней в куче больше или равно 58, игра заканчивается. Возвращаем True, если текущий игрок выиграл (количество ходов четное).
if m == 0: return 0: Если ходов не осталось, возвращаем False.
Создаем список h, содержащий результаты всех возможных ходов (добавление 1 камня, добавление 4 камней, умножение количества камней на 2).
return any(h) if (m - 1) % 2 == 0 else all(h): Возвращаем any(h), если количество ходов четное, иначе all(h).

Задача 19

Определить значения S, при которых Ваня может выиграть своим первым ходом независимо от хода Вани:


print('19)', [s for s in range(1, 58) if f(s, 2)])

print('19)', [s for s in range(1, 58) if f(s, 2)])

Задача 20

Определить значения S, при которых Петя не может выиграть за один ход, но может выиграть своим вторым ходом:


print('20)', [s for s in range(1, 58) если not f(s, 1) и f(s, 3)])

print('20)', [s for s in range(1, 58) если not f(s, 1) и f(s, 3)])

Задача 21

Определить значения S, при которых Ваня не может выиграть гарантированно за один ход, но может выиграть своим вторым ходом:


print('21)', [s for s in range(1, 58) если not f(s, 2) и f(s, 4)])

print('21)', [s for s in range(1, 58) если not f(s, 2) и f(s, 4)])