Числовой многоугольник (Npolygon)
Как-то раз к Дим Димычу в гости пожаловал его друг Васька. Они вместе готовились к олимпиаде по устному счету и поэтому постоянно складывали все числа, которые попадались им на глаза. Симка решила помочь друзьям и нарисовала N-угольник, к каждой вершине которого приписала число. Васька, увидев изображение, предложил складывать не все числа, а только k (1 < k < N), идущих подряд по часовой стрелке. Дим Димыч предложил не всем вершинам многоугольника приписывать одно и то же число. Друзья с удивлением заметили, что при этом иногда суммы получаются одинаковыми для всех вершин. Они обозначили S(i,k) как сумму чисел в k последовательных вершинах, начиная с вершины i. Друзья решили найти максимальное k, при котором все такие суммы равны.
Формат ввода-вывода:
Программа Npolygon читает с клавиатуры (стандартного устройства ввода) единственное целое число N количество углов N-угольника (3 ≤ N ≤ 1015).
Программа Npolygon выводит на экран (стандартное устройства вывода) единственное число k (1 < k < N) – максимальное количество подряд идущих по часовой стрелке чисел, среди которых хотя бы два разных, таких, что для всех i S(i,k) равны между собой. Если такую последовательность чисел у заданного N-угольника написать нельзя, выведите «-1» (без кавычек).
Пример входных и выходных данных:
|
Ввод |
Вывод |
|
6 |
4 |
|
9 |
6 |
Кондитерская фабрика (fixcandy)
Как и все дети, Дим Димыч большой сладкоежка, а поэтому, когда его спросили, где он хочет работать, когда вырастет, он, естественно, ответил – изготавливать конфеты. Когда же фиксики поинтересовались, представляет ли он, в чем будет заключаться его работа, он ответил, что это не важно, лишь бы можно было есть конфет сколько угодно. Симка решила показать Дим Димычу работу на фабрике по упаковке уже готовых конфет.
Выполняет упаковку фасовочно-упаковочный автомат, который имеет N емкостей, в каждую из которых каждую секунду поступает ровно одна конфета. Конфеты пакуются ровно по k штук в коробке, а потому, как только в одной из емкостей оказывается указанное количество конфет, они отправляются на упаковку и емкость опустошается. Далее заполнение емкости начинается сначала.
Когда Дим Димыч появился на фабрике, в каждой из емкостей автомата находилось некоторое количество конфет. Ему поручили упаковать не менее L коробок по k конфет, а после выполнения задания освободить все емкости от оставшихся конфет. Симка, услышав это, пришла в ужас, прекрасно понимая, что освобождение емкостей превратится в их съедение. А это означало, что больные зубы Дим Димычу обеспечены.
Пока работа только налаживается, она обратилась за помощью к вам: минимизировать количество конфет, подлежащих съедению. А для этого надо определить, за какое минимальное время Дим Димыч гарантированно выполнит (а может, и перевыполнит) задание, а количество конфет в емкостях останется минимально возможным.
Формат ввода-вывода:
Программа fixcandy сначала читает с клавиатуры (стандартного устройства ввода) три целых числа N, K, L (1≤N≤106, 1≤K≤109, 0≤L≤109). Затем считывается N неотрицательных целых чисел a1, a2 ,… aN строго меньших К – количество конфет в каждой из емкостей автомата перед началом работы.
Программа fixcandy выводит на экран (стандартное устройства вывода) одно число – минимальную продолжительность смены, при которой гарантированно выполнен план и при которой Дим Димычу придется съесть минимальное количество конфет.
Пример входных и выходных данных:
|
Ввод |
Вывод |
|
3 3 2 1 1 2 |
2 |
Примечание: В момент времени 0 (начало смены) в емкостях находится (1, 1, 2) конфет.
0 сек: (1, 1, 2)
1 сек: (2, 2, 0) => 1 упаковка
2 сек: (0, 0, 1) => 2 упаковки, итого уже 3
Таким образом, на второй секунде задание уже выполнено, а сумма конфет, подлежащих съедению минимальна.
Пирог с фиксиками (fixpie)
Сегодня у Дим Димыча большой праздник – мама печет пирог. И пока она колдует на кухне, Дим Димыч развлекается запуском детского железнодорожного состава. Все было просто замечательно, пока не появился Нолик. С его сестрой Симкой и ее подругой Шпулей опять случилась неприятность: девчонки баловались на кухне и попали в пирог, который мама уже засунула в духовку. Что делать? Надо как-то обезопасить своих домочадцев от проглатывания винтиков, в которые превращаются фиксики! А для этого, естественно, надо съесть побольше пирога.
Чтобы легче было делить круглый пирог между желающими полакомиться, мама на него нанесла N (N≤360) радиальных отметок для разреза под углами 0.0 ≤ a1 < a2 < … < aN < 360.0. Желающих попробовать пирог ровно K (2 ≤ K ≤ N) человек. Теперь, чтобы даже в худшем случае Дим Димыч мог съесть кусок побольше, ему надо разрезать пирог таким образом, чтобы размер самого маленького из k кусков был как можно больше. Помогите Дим Димычу найти угловой размер L наименьшего куска с точностью до ε = 10-5.
Формат ввода-вывода:
Программа fixpie сначала читает с клавиатуры (стандартного устройства ввода) два целых числа N и k – количество отметок на пироге и количество кусков, которые надо получить. Затем считывается N чисел a1, a2 ,… aN – углы, под которыми нанесены радиальные отметки.
Программа fixpie выводит на экран (стандартное устройства вывода) выводит одно число – ответ на поставленный вопрос.
Пример входных и выходных данных:
|
Ввод |
Вывод |
|
5 3 25.5 70.0 100.5 170.0 220.5 |
75.0 |
Примечание: В этом примере, пирог разрезали под углами 25.5, 100.5 и 220.5, получив три куска с угловыми размерами 75.0 (искомый кусок), 120.0 и 165.0.
Манипулятор (manipul)
После недоразумения, случившегося с манипулятором, напугавшим секретаря Лизоньку, профессор Гений Евгеньевич решил его усовершенствовать и подключил к компьютеру. Для управления манипулятором он написал программу, которая представляла собой огромную таблицу А размером NxN, состоящую из нулей и единиц, причем единицы стояли только в тех ячейках таблицы, у которых остаток от деления номера строки и номера столбика на некоторое число М был одинаковым, т.е. A[row][column]=1 только если row%M=column%M.
Ночью в лабораторию Гения Евгеньевича заглянули фиксики и случайно передвинули на его столе магнит так, что он испортил практически всю информацию на винчестере. Чудом уцелело ровно P-1 единица в программе для манипулятора, все остальные ячейки обнулились. Симка страшно испугалась и попыталась восстановить программу. Однако ей удалось добиться появления всего одной дополнительной единички в таблице, причем на произвольном месте.
Поскольку программа была безнадежно испорчена, профессор предложил Вам найти максимальное из всех возможных значений М для исходной таблицы.
Формат ввода-вывода:
Программа manipul сначала читает с клавиатуры (стандартного устройства ввода) два целых числа N и P (2 ≤ N ≤ 105; 2 ≤ P ≤ min(105,N2)). Затем считывается Р пар целых неотрицательных чисел, не превышающих значение N-1 – позиции сохранившихся единичек. Правда, не известно, какая из этих единичек возникла как побочный эффект после манипуляций Симки.
Программа manipul выводит на экран (стандартное устройства вывода) единственное число – максимально возможное число М для первоначальной таблицы. Если максимальное значение однозначно не определяется, необходимо вывести «-1» (без кавычек). Значение М считается возможным, если в программе для манипулятора, по крайней мере на Р-1 позиции, заданных во входных данных, будет стоять единица.
Пример входных и выходных данных:
|
Ввод |
Вывод |
|
3 5 0 0 0 1 1 0 2 2 2 1 |
1 |
|
5 5 0 0 1 1 0 3 1 3 4 4 |
3 |
|
3 2 0 0 0 1 |
-1 |
Пояснение к входным тестам:
Во втором тесте таблица после воздействия магнитом имеет вид:
10010
01010
00000
00000
00001
Для такой таблицы возможны значения М=2 и М=3. При М=3 программа имеет такой вид:
10010
01001
00100
10010
01001
Т.е. единица в позиции (1,3) была побочным эффектом.
В третьем тесте таблица после воздействия имела вид:
110
000
000
Для такой таблицы подходят все целые числа, поэтому ответ «-1». Для М>1 считается, что вторая единица в первом ряду – побочный эффект.