Заочный тур осенней олимпиады 1999 года по программированию
среди студентов университета.
Во всех задачах ввод данных производится из файла
INPUT.TXT, а вывод результатов - в файл OUTPUT.TXT. Формат
входного файла соответствует спецификации, дополнительные про-
верки не нужны. Время теста указано для 486+ >=100МГц.
Для выхода на очный тур необходимо решить по крайней мере
одну задачу. На очный тур проходят ~18 участников, решивших
наибольшее количество задач за наименьшее количество попыток.
+------------------------------------------------------------+
| 1. Прыг-скок (4 сек на тест) |
+------------------------------------------------------------+
Игра "Прыг-скок" ведется на доске-полоске из N клеток. У
каждого игрока по одной фишке. В начале игры фишка первого иг-
рока находится на левом краю доски (на 1 клетке), а фишка вто-
рого игрока - на правом краю (на N клетке). Игроки ходят по
очереди. Фишка первого игрока делает "прыжки" по M клеток, а
фишка второго игрока - "скачки" по K клеток. Фишка может пры-
гать как влево, так и вправо. Перепрыгивать через фишку про-
тивника или вставать на занятую клетку запрещено. Если игрок
не может сделать прыжок (скачок) своей фишкой, то он проигры-
вает. Кто выигрывает при безошибочной игре противников?
Во входном файле в первой строке содержатся три целых числа
N (2<=N<=30), M (1<=M<=N/2) и K (1<=K<=N/2) через один пробел.
В выходной файл вывести число 1, если выигрывает первый иг-
рок, или 2, если выигрывает второй игрок, или 0, если ни один
из игроков не имеет выигрывающей стратегии.
Пример INPUT.TXT: OUTPUT.TXT для примера:
10 3 5 0
+------------------------------------------------------------+
| 2. Составление палиндрома (4 сек на тест) |
+------------------------------------------------------------+
Дан набор слов, составить палиндром (перевертыш, предложе-
ние, которое одинаково читается слева-направо и справа-налево)
из _всех_ указанных слов.
Во входном файле содержится от 1 до 15 слов длиной до 15
букв, каждое слово на отдельной строке, каждая строка оканчи-
вается символом перехода на новую строку, пробелы отсутствуют;
слова отсортированы по алфавиту, используются только прописные
русские буквы, буква р (Е:) не используется. Из слов, указанных
во входном файле, всегда можно составить палиндром.
В выходной файл вывести на одной строке составленный палин-
дром, _разделяя_ слова ровно одним пробелом. Если возможно сос-
тавить несколько палиндромов, вывести _любой_ из них.
Пример INPUT.TXT:
А
АЗОРА
ЛАПУ
НА
РОЗА
УПАЛА
OUTPUT.TXT для примера:
А РОЗА УПАЛА НА ЛАПУ АЗОРА
+------------------------------------------------------------+
| 3. Числа-палиндромы (4 сек на тест) |
+------------------------------------------------------------+
Возьмем произвольное число большее или равное 1. Если это
число не является числом-палиндромом (которое одинаково чита-
ется слева-направо и справа-налево, например 27372), то запи-
шем его наоборот, а затем сложим его с первоначальным числом.
После нескольких таких шагов для большинства чисел-затравок мы
получаем число-палиндром. Например, для числа 78: 78+87=165,
165+561=726, 726+627=1353, 1353+3531=4884.
Для некоторых чисел, наименьшее среди которых 196, даже
после очень большого числа шагов (более ста тысяч) палиндром
не получается.
Во входном файле содержится несколько (не более 100) чисел
в диапазоне от 1 до 99999, по одному числу в строке. Признаком
конца набора чисел является число 0.
В выходной файл для каждого числа из входного файла вывести
на отдельной строке или само число, если оно уже является чис-
лом-палиндромом, или число-палиндром, которое получается из
указанного за сто или меньшее число шагов, или число 0, если
число-палиндром не может быть получено за сто или меньшее чис-
ло шагов. Для числа 0, являющегося признаком окончания набора
чисел, в выходной файл ничего не выводится.
Пример INPUT.TXT: OUTPUT.TXT для примера:
27372 27372
196 0
78 4884
1999 712217
0