Тренажёр: стратегия первого или второго хода
Та же игра, что в заданиях 19 и 20: второй игрок (Ваня) должен выиграть первым или вторым ходом при любой игре Пети, но без гарантии победы первым ходом. Найдите минимальное S.
Правила и цель
Перед игроками куча из S камней. За ход можно убрать несколько камней или уменьшить кучу в несколько раз (с округлением вниз). Игра заканчивается, когда камней становится не больше порога: побеждает тот, кто сделал последний ход.
Здесь выигрывает второй игрок (Ваня). Нужно минимальное S, при котором у Вани есть стратегия выиграть первым или вторым ходом при любой игре Пети.
Мгновенная победа
Игрок выигрывает за один ход, если после хода куча становится не больше порога. У каждой команды своё условие. Например, убрать 5 — это S − 5 ≤ 30; уменьшить в 4 раза — это ⌊S / 4⌋ ≤ 30. Все команды вместе задают зону мгновенной победы: S ≤ A.
Почему нет гарантии первого хода
Условие требует, чтобы Ваня не выигрывал гарантированно первым ходом. Значит, существует ход Пети, после которого у Вани нет хода в кучу не больше порога. При этом на любой ход Пети Ваня должен побеждать не позже второго хода.
Как проверять
Взяли кандидата — разыграйте все ходы Пети. Каждый должен вести в позицию, где Ваня выигрывает первым или вторым ходом; и хотя бы один ход Пети не должен давать Ване мгновенной победы. Берите минимальное подходящее S.
Как пользоваться этим режимом. Прочитайте правила раунда, найдите минимальное <span class="ent">S</span> и введите число. Затем «Проверить»; при трудностях откройте «Показать решение» с разбором по ходам.