Пример 1
Два игрока, Петя и Ваня, играют в игру. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход можно добавить в кучу один камень, добавить четыре камня или увеличить количество камней в два раза. Игра завершается, когда в куче становится не менее 45 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в куче S камней, 1 ≤ S ≤ 44.
Укажите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любом ходе Пети.
Показать решение и ответ
1. Ваня выигрывает первым ходом, если любой ход Пети оставляет кучу, из которой можно сразу получить 45 или больше.
2. Сразу выиграть можно из кучи 23 и больше: 23 · 2 = 46. Из 22 — нельзя: 22 · 2 = 44, 22 + 4 = 26.
3. Значит, при S < 23 Петя не выигрывает первым ходом, а нам нужно, чтобы все его ходы вели в кучу ≥ 23.
4. Ход «+1» даёт S + 1 ≥ 23 → S ≥ 22. При S = 22: 23, 26 и 44 — из каждой Ваня выигрывает удвоением или «+1».
5. Минимальное S = 22.
Проверка программой — общей для заданий 19–21:
from functools import lru_cache # запоминаем уже посчитанные позиции, иначе перебор очень долгий
def moves(s): # все ходы из позиции s
return [s + 1, s + 4, s * 2] # +1 камень, +4 камня, удвоение
@lru_cache(None) # кэш результатов для каждой позиции
def game(s): # итог позиции для того, кто сейчас ходит
if s >= 45: # игра уже окончена — ходящий проиграл
return 'L0' # L0: проигрыш «за 0 ходов соперника»
res = [game(t) for t in moves(s)] # итоги позиций после каждого нашего хода (для соперника)
lose = [r for r in res if r[0] == 'L'] # ходы, после которых соперник проигрывает
if lose: # такой ход есть — мы выигрываем
return 'W' + str(min(int(r[1:]) for r in lose) + 1) # побеждаем как можно быстрее
return 'L' + str(max(int(r[1:]) for r in res)) # все ходы плохие — проигрываем как можно позжеОбозначения: W1 — ходящий выигрывает первым ходом, W2 — вторым; L1 — соперник выигрывает своим первым ходом при любом ходе ходящего, L2 — первым или вторым.
print(min(s for s in range(1, 45) if game(s) == 'L1')) # минимальное S, где Ваня выигрывает первым ходом: 22Ответ: 22