Задание

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи 7 камней или уменьшить количество камней в 2 раза. Убирать 7 камней можно только тогда, когда в куче есть не менее 7 камней. Если количество камней не кратно 2, то при уменьшении количества камней в два раза остается количество камней равное результату целочисленного деления текущего количества на 2.

Например, из кучи из 19 камней можно получить кучу из 12 камней или кучу из 9 камней. Игра завершается в тот момент, когда из кучи убирается последний камень. Победителем считается игрок, сделавший последний ход, т. е. убравший из кучи последний камень.

В начальный момент в куче было S камней; S > 0.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Найдите наименьшее значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

– Петя не может выиграть за один ход;

– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.