Задача 14: Пуговицы
Л.Волков
Как уже несомненно
стало известно всем, Екатеринбург добился права на проведение Летних
Олимпийских игр 2032 года. Планируется, что России, как
стране-организатору Олимпийских игр, будет разрешено внести
минимальные изменения в программу Олимпиады. Так, с целью улучшения
общего командного результата, было решено заменить соревнования по
плаванию первенством в абсолютно новой игре "Пуговицы".
Правила игры очень просты. Перед двумя играющими находится кучка из
K пуговиц. Играющие по очереди берут пуговицы из кучки, причем за
один ход каждый из них может взять от 1 до L пуговиц. Выигрывает тот
из спортсменов, которому удастся взять последнюю пуговицу.
Правила олимпийских соревнований будут лишь немного сложнее обычных.
Тот из игроков, которому по жребию выпадает делать первый ход,
получает возможность собственноручно назначить число K,
руководствуясь в своем выборе только ограничениями 3 <= K <= 100 000
000 (именно столько пуговиц заготовлено для олимпийского турнира).
Тот из игроков, который будет ходить вторым, выбирает, в свою
очередь, число L, которое должно отвечать условию 2 <= L < K.
Задача
На вашу команду возлагается очень ответственная задание:
необходимо написать программу, которая помогала бы второму игроку
делать свой выбор. Другими словами, по заданному числу пуговиц в
кучке K, необходимо определить такое число L, которое гарантирует
победу второму игроку при наилучшей игре обеих сторон.
Так, например, если в кучке всего три пуговицы, то победу второму
игроку обеспечивает выбор L=2. В самом деле, если первый игрок своим
ходом заберет одну пуговицу, то второй сможет выиграть, взяв обе
оставшихся пуговицы и, напротив, если первый возьмет две пуговицы,
то второй победит, взяв последнюю.
Исходные данные
Вход для этой задачи состоит из одной строки, в которой записано
единственное число K - количество пуговиц в кучке, выбранное первым
игроком.
Результат
На выход следует записать единственное целое число L -
максимальное количество пуговиц, которое можно взять за один
ход - обеспечивающее победу второму игроку. Если таких чисел
несколько, то следует вывести наименьшее из них. Если таких чисел
нет, то следует вывести число 0.
Пример исходных данных
3
Пример результата
2
Решение:
Это вроде бы простая задача. Нам достаточно разбить число пуговиц на
некоторое число одинаковых групп так, что в каждой группе находится
целое количество пуговиц(l), большее единицы.
Ответом будет количество пуговиц в группе - 1. Это значит, что
независимо от хода первого игрока, второй игрок может дополнить
имеющуюся группу пуговиц до необходимого количества(l).
Реализуется это перебором от 2 до квадратного корня из числа
пуговиц, и проверкой, является ли число делителем количества
пуговиц. В случае если количество пуговиц - простое число, то
ответом будет K-1(легко доказывается).
Далее
ð
