Задание №19. Короткий конспект
Победа за один ход, различие возможности и гарантии, проверка всех выходов и минимальности.
Позиция — состояние перед ходом: число камней или пара чисел вместе с очередью игрока. После каждого действия сначала проверяется конец игры. Из законченной, или терминальной, позиции ходов уже нет. Петя начинает; Ваня отвечает.
Смысл вопроса
| Условие | Проверка |
|---|---|
| Победа за один ход | Есть хотя бы одно завершающее действие |
| После неудачного хода Пети | Есть незавершающий ход Пети, допускающий победный ответ Вани |
| После любого хода Пети | Все ходы Пети оставляют игру незаконченной и дают Ване победу за ход |
В последней строке ответ Вани может зависеть от выбора Пети. Одна заранее выбранная операция для всех ветвей не требуется. Гарантия означает наличие ответа в каждой ветви, а не в одной удачной партии.
Порядок решения
- Выписываются начальные ограничения, все разрешённые действия и точный порог победы. Для двух куч сохраняется пара, поскольку одинаковая сумма может давать разные результаты умножения.
- Находятся продолжающиеся позиции, из которых ходящий может сразу победить. Их удобно обозначать W_1. Уже завершённые позиции в этот набор не включаются.
- Для «после неудачного» ищется один ход Пети в W_1. Для «после любого» проверяются все его ходы; немедленная победа Пети исключается.
- Из подходящих начальных значений выбирается требуемое условием. Минимум подтверждается исключением всех меньших допустимых значений.
Опорная проверка
В игре с уменьшением кучи ↗ начало S\ge11, действия — убрать три, убрать пять или разделить на четыре с округлением вниз. Победа — не более десяти камней.
Позиции W_1: от 11 до 43. Из 44 Петя получает 41, 39 или 11; Ваня отвечает соответственно 10, 9 или 8. Все три ветви заканчиваются его победой. Меньшие допустимые значения позволяют Пете победить сразу, поэтому минимум — 44.
Возможные ловушки
Округление к ближайшему вместо округления вниз изменит границу: \lfloor43/4\rfloor=10. Продолжение после достижения порога добавит несуществующий ход. А в игре после ошибки Пети ↗ проверка всех его ходов вместо одного усилит условие. Для проверки результата существенные слова вопроса сопоставляются с каждой рассмотренной ветвью.