Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее
W. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет
W или больше камней.
В начальный момент в куче было
S камней,
1 ≤ S ≤ W-1.
Напишите программу, которая определяет:
задание 1) такое значение
S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
задание 2) все значения
S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
задание 3) все значение
S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
При написании программы будет считать, что все игроки действуют оптимально. Другими словами, игрок, у которого имеется выигрышная стратегия будет стремиться выиграть за наименьшее число ходов. Игрок, у которого отсутствует выигрышная стратегия (который проигрывает) будет стараться игру затянуть, т.е. проиграть за наибольшее число ходов.
Формат входных данных
Программа получает на вход целое число W (10 <= W <= 1000).
Формат выходных данных
В ответе должно быть три строки. В первой строке - ответ на задание 1, во второй - на задание 2, в третьей - на задание 3.
В каждой строке, в которой может быть больше одного значения, значения должны быть распечатаны в порядке возрастания, через один пробел
Запрещенные операторы: def
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
|
4
2 3
1
|