Задача #4370

Задания 19–21

Уровень ЕГЭ

Общее условие для 19–21

(А. Шуруха) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 5 камней либо увеличить количество камней в куче в 3 раза.
Например, из кучи в 20 камней за один ход можно получить кучу из 25 или 60 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее чем в четыре раза больше первоначального. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой камней не менее 4S, где S — количество камней в начальный момент. В начальный момент в куче было S камней; 1 ≤ S ≤ 150. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Вопрос для задания 20

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

Задание 19 Задание 21

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

Общий разбор связки

def moves(s):
  return [s + 5, 3 * s]
def f(s, m, lim):
  if s >= lim: return m % 2 == 0
  if m == 0: return False
  h = [f(x, m - 1, lim) for x in moves(s)]
  return any(h) if m % 2 else all(h)

a19 = [s for s in range(1, 151) if f(s, 2, 4 * s)]
a20 = [s for s in range(1, 151) if f(s, 3, 4 * s) and not f(s, 1, 4 * s)]
a21 = [s for s in range(1, 151) if f(s, 4, 4 * s) and not f(s, 2, 4 * s)]
print('19', len(a19))
print('20', min(a20), max(a20))
print('21', min(a21))

Решение для задания 20

Номер