Два игрока, Петя и Ваня, играют в игру с одной кучей камней.
Игра организована по следующим правилам:
- Игроки ходя поочередно. Первый ход делает Петя;
- Каждый ход игрок может увеличить количество камней в куче.
Если в куче n камней и число n кратно k (k > 1), то за один ход разрешается добавить в кучу n/k камней.
(Например, если в куче 12 камней, то за один ход можно добавить 1 (12/12),
2 (12/6), 3 (12/4), 4 (12/3) или 6 (12/2) камней.)
- Игра завершается, когда количество камней в куче становится больше M.
Если при этом в числе количества камней, цифра десятков четная,
то Победителем считается игрок, сделавший последний ход,
иначе Победителем считается его противник, при этом считается, что он сделал хож
- В начальный момент в куче было S камней, 2 ≤ S ≤ M.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Примеры для М=45:
- Петя в кучу из 34 камней добавил 17 камней. Игра завершилась с 51 камнем. Победителем считается Ваня,
причем Ваня выиграл своим первым ходом;
- Петя в кучу из 36 камней добавил 12 камней. Игра завершилась с 48 камнем. Победителем считается Петя, .
Задание 19.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход,
но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20.
Найдите наименьшее и наибольшее значения S,
при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Найдите максимальное значение S,
при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Выполните задания для трех значений N:
1 строка - ответы для N=77 (четыре числа в строку через пробел)
2 строка - ответы для N=1580 (четыре числа в строку через пробел)
Пояснение: Для M=45 строка ответов имела бы вид:
31 26 38 37