Два игрока, Пятачок и Винни, играют в игру с одной кучей камней.
Игра организована по следующим правилам:
- Игроки ходя поочередно. Первый ход делает Пятачок;
- Каждый ход игрока увеличивает количество камней в куче.
Если в куче t камней то игрок своим ходом может:
- увеличить количество камней в k раз, если число t не кратно k (k из множества {2,3,5})
- добавить в кучу а камней, если число t не кратно a ( a из множества{2-10})
- "перейти к следующему простому", то есть добавить в кучу b камней (b>0), так чтобы:
t+b - простое и на отрезке [t+1,t+b-1] - простых чисел нет.
Примеры для k=2, a=3:
если в куче 13 камней, то после хода, количество камней в куче может быть:
16 (13+3), 26 (13*2), 17 (следующее простое),
если в куче 60 камней, то после хода, количество камней в куче может быть:
только 61 (следующее простое)
- Игра завершается, когда количество камней в куче становится не меньше N.
Если при этом количество камней в куче простое число или
кратное p (p - небольшое простое, не равное k, a) , то :
- то Победителем считается игрок, сделавший последний ход,
- иначе Победителем считается его противник, при этом считается, что он сделал ход
- В начальный момент в куче было S камней, L ≤ S ≤ R < N.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Задание 1. Укажите минимальное (x) и максимальное (y) значение S,
при котором Винни имеет выигрышную стратегию.
Задание 2. Найдите количество (z) значений S, при которых у Пяточка есть выигрышная стратегия.
Найденные значения (x, y, z) запишите в ответе в порядке возрастания.
Выполните задания для двух наборов значений:
1 строка - ответы для L=10 , R=25 ,N=100 (три числа в строку через пробел)
2 строка - ответы для L=1000 , R=2000 ,N=10000 (три числа в строку через пробел)
Пояснение для k=2, a=3, p=7, L=5 , R=13 ,N=31 строка ответов имела бы вид:
6 12 4 (x=6, y=12, z=4)