Условие задачи
Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза.
Например, если в куче было 10 камней, за один ход можно получить 11 или 20 камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 58.
Победителем считается игрок, сделавший последний ход.
В начальный момент в куче было S камней, где 1 ≤ S ≤ 57.
Найдите минимальное значение S, при котором у Вани есть стратегия,
позволяющая ему выиграть первым или вторым ходом при любой игре Пети,
но у Вани нет стратегии, позволяющей гарантированно выиграть своим первым ходом.
В ответе запишите одно целое число.
Подсказка
Нужно найти такую позицию, из которой любой первый ход Пети переводит игру
в позицию, выигрышную для Вани не позднее его второго хода.
Решение
Из предыдущего анализа известно:
- при S ≥ 29 игрок может выиграть за один ход;
- S = 28 — позиция, из которой любой ход отдаёт победу следующему игроку за один ход;
- S = 14 и S = 27 — позиции, из которых игрок может выиграть вторым ходом.
Рассмотрим S = 26. У Пети есть два хода:
26 + 1 = 27
26 * 2 = 52
Если Петя получает 27, то Ваня может перевести игру в 28, после чего Петя любым ходом
отдаёт Ване возможность выиграть следующим ходом.
Если Петя получает 52, то Ваня сразу выигрывает, добавив 6 камней невозможно,
но он может сделать только +1 или ×2. Ход ×2 даёт 104, то есть не менее 58.
Значит, Ваня выигрывает сразу.
При этом Ваня не гарантирует выигрыш своим первым ходом для любого первого хода Пети:
после хода Пети в 27 Ваня не может завершить игру немедленно.
Поэтому минимальное подходящее значение S равно 26.
Ответ: 26.