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