Олимпиадный тренинг

Задача . 19-21_ПР-005


Задача

Темы:

Два игрока, Павел и Родион, играют в следующую игру.
Перед игроками находится ваза с конфетами, в которой изначально лежит S конфет.
Игроки ходят по очереди, первым ходит Павел.

За один ход игрок может выполнить одно из двух следующих действий:

  1. Оставить в вазе количество конфет равное любому "большему делителю" числа конфет, отличным от самого числа
    (назовем такое действие "Великодушие" или команда В)
    Пояснение - число d называется "большим делителем" числа a если выполняются условия:
    • a % d  равно 0
    • d < a, но d*d  уже не меньше a
      Например, для числа 36 "большим делителем" являются числа 6, 9,12, 18
  2. Если пункт 1 выполнить невозможно (количество конфет в вазе простое),
    то игрок уменьшает количество конфет в вазе на  три (назовем такое  действие "Скромность")

Игра завершается, если количество конфет в вазе равно простому числу, не превосходящему 10 (то есть 2, 3, 5, 7)
Игрок, сделавший последний ход считается ПРОИГРАВШИМ (поскольку на вопрос "Ты ел конфеты?", он точно должен ответить утвердительно) 
Другой игрок объявляется победителем. 
Будем говорить, что игрок имеет выигрышную стратегию (ВС), если он может "заставить соперника последним взять конфеты" (то есть победить).
Примеры:

  1. Пусть в вазе 12 конфет.
    ВС есть у Павла - он применяет команду B4 (оставляет 4 конфеты (4*4 > 12),
    Родион может выполнить только команду В2 (оставит 2 конфеты) и ПРОИГРАЕТ.
    Считается, что Павел выиграл "первым ходом"
  2. Пусть в вазе 19 конфет
    Количество конфет в вазе выражается простым числом, значит Павел должен выполнить команду С  (уменьшить на 3 конфеты) оставив в вазе 16 конфет.
    Тогда Родион применив команду В4 оставляет в вазе 4 конфеты, Павел вынужден применить команду В2 (оставит в вазе две конфеты) и проиграет.
    Считается, что ВС есть у Родиона, причем он не имеет "стратегии" для победы "без хода", но имеет  "стратегию" для победы не более чем за 1 ход
  3. Пусть в вазе 44 конфеты
    ВС есть у Павла. Он может выполнить одну из двух команд (В11 и В22). Для  победы должен выбрать В11.
    Родион может выполнить только команду С и оставить в вазе 8 конфет. 
    Павел в ответ вынужден выполнить команду В4 и в вазе останется 4 конфеты. 
    Родион должен выполнить команду B2  и в вазе останется 2 конфеты, значит Родион ПРОИГРАЛ
    Считается, что ВС есть у Павла, причем у него нет "стратегии" для победы менее чем за два хода, но есть "стратегия" для победы в 2 хода

Известно, что в начальный момент в вазе находится S конфет, где 1234 <= S <= 4321.

Выполните задания.

Задание A. Укажите наибольшее значение S, при котором у Родиона есть ВС не более, чем в один ход

Задание B. Найдите наименьшие и наибльшее значения S, при которых у Павла есть ВС для победы не более, чем в два хода, но нет ВС для победы менее, чем за два хода: 

Задание C. Найдите минимальное значение S, при котором  у Родиона есть ВС, позволяющая ему выиграть не более, чем в два хода, но нет ВС для победы менее, чем за два хода.

Как записать ответ. Ответ на каждый вопрос — с новой строки:
           1-я строка — ответ на задание 1: одно число;
           2-я строка — ответ на задание 2: два числа в порядке возрастания через пробел;
           3-я строка — ответ на задание 3: одно число.

 


Статистика успешных решений по компиляторам