Информатика · ЕГЭ · 4 мин чтения

Как определить выигрыш за один ход в игре с камнями?

Редакция Алгоса · Обновлено

Короткий ответ

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

Разберись, что нужно найти

Пусть в куче S камней. За ход разрешено добавить один камень или удвоить кучу. Выигрывает тот, кто первым получает не меньше 10 камней. Из S = 6 можно перейти к 7 или 12. Переход к 12 сразу выигрывает, поэтому позиция допускает победу за один ход, хотя переход к 7 не выигрывает.

Связь условия задачи с нужным действием
Что дано или требуетсяКак это использовать
Собственный выигрышный ходДостаточно одного подходящего действия
Соперник выбирает ответУчитываем каждый разрешённый ответ
Не меньше целиПеребор за границу разрешён

Проследи решение на конкретных данных

Проверка одного хода выглядит как (S + 1 >= 10) or (2 * S >= 10). Здесь ИЛИ соответствует выбору игроком удобного действия. Для начальных положительных S меньше 10 победить сразу можно при S от 5 до 9: удвоение достигает цели. Начальные значения уже не меньше 10 нужно рассматривать по правилам задачи отдельно.

Промежуточные результаты разобранного примера
ШагРезультат
S = 67 или 12: есть победа
S = 45 или 8: оба ответа дают сопернику победу
Пример с объяснением

При S = 4 мгновенной победы нет: доступны 5 и 8. Но из обеих этих позиций соперник может удвоить кучу и выиграть сразу. Значит любой ход первого игрока из четырёх отдаёт сопернику победу за один ход. Чтобы это доказать, проверены оба хода, а не только один неудобный вариант.

Проверь границы способа и реши сам

Слова «существует ход» и «при любом ходе» задают разные проверки. Выбирая собственный выигрышный ход, достаточно одного успешного продолжения. Доказывая защиту от соперника, нужно учесть все его ответы. Также внимательно читай цель: «ровно 10» отличается от «не меньше 10», и удвоение шести в первой игре не достигло бы цели.

Самопроверка: оставь команды +1 и ×2, но поменяй цель на «не меньше 15». Для каких положительных начальных S < 15 можно выиграть одним ходом? Отдельно проверь S = 7 и S = 8, чтобы найти границу.

Ответ и почему так

Нужно S + 1 ≥ 15 или 2S ≥ 15. При целых S второе условие даёт S ≥ 8, поэтому ответы 8…14. Из семи получаются 8 или 14, победы ещё нет. Из восьми удвоение даёт 16 и сразу выполняет условие «не меньше 15».

Что запомнить

Для победы своим ходом достаточно одного подходящего действия; гарантия против соперника требует проверки всех его ответов.

Попробовать на Алгосе

Программирование для ЕГЭ

Продолжи подготовку в курсе: разбирай способы решения и проверяй их на самостоятельных заданиях.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы