Игры с кучей камней: задания 19, 20, 21
Коротко
Два игрока по очереди увеличивают кучу камней (например, +1 или ×2), выигрывает тот, кто первым получил не меньше заданного числа. Позиция выигрышная, если из неё есть ход в проигрышную; проигрышная — если все ходы ведут в выигрышные. В 19 ищут S, при которых Петя выигрывает первым ходом (или Ваня — первым ходом после неудачного хода Пети), в 20 — Петя выигрывает своим вторым ходом, в 21 — Ваня выигрывает первым или вторым ходом.
Ключевые определения
- Выигрыш за 1 ход: есть ход, сразу достигающий цели.
- П1 (проигрыш за 1): все ходы ведут к позициям, где соперник выигрывает за 1.
- Выигрыш за 2: есть ход в П1.
Пример (цель ≥ 30, ходы +1, ×2)
- Петя выигрывает первым ходом при S ≥ 15 (2·15 = 30).
- S = 14: ходы дают 15 или 28 — из обоих Ваня выигрывает за ход. Значит, при S = 14 Ваня выигрывает первым ходом.
Шаблон на Python
from functools import lru_cache
@lru_cache(None)
def game(s):
if s >= 30:
return 0
res = [game(t) for t in (s + 1, s * 2)]
neg = [r for r in res if r <= 0]
if neg:
return -max(neg) + 1
return -max(res)
Положительное значение k — выигрыш игрока, который ходит, за k ходов; отрицательное — проигрыш.
Типичные ошибки
- Путают «Ваня выигрывает первым ходом» и «Ваня может выиграть».
- В 21 забывают условие «и при этом у него нет стратегии, которая всегда даёт выигрыш первым ходом».
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 19
Пример 1 из 2
Цель ≥ 30, ходы +1 и ×2. При каком наименьшем S Петя выигрывает первым ходом?
- Разбор
- Нужно 2S ≥ 30 или S + 1 ≥ 30 → S ≥ 15.
- Ответ
- 15
Пример 2 из 2
При каком S Ваня выигрывает первым ходом при любой игре Пети?
- Разбор
- Все ходы Пети должны вести в выигрышные позиции: S = 14 → 15 или 28.
- Ответ
- 14
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Когда позиция выигрышная?
Показать ответ
Ответ: Есть ход в проигрышную.
Для игрока, который ходит.
- Вопрос 2 из 5
Когда позиция проигрышная?
Показать ответ
Ответ: Все ходы ведут в выигрышные.
Для соперника.
- Вопрос 3 из 5
Что ищут в задании 19?
Показать ответ
Ответ: S для выигрыша первым ходом.
Петя или Ваня — по условию.
- Вопрос 4 из 5
Что ищут в 20?
Показать ответ
Ответ: Выигрыш Пети вторым ходом.
Ход в проигрышную позицию П1.
- Вопрос 5 из 5
Что ищут в 21?
Показать ответ
Ответ: Выигрыш Вани первым или вторым ходом.
Но не обязательно первым.
Проверьте всё задание 19, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти