Сложность: 37%
Компания Flatland Dynamics разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из специальных платформ, пронумерованных от до . Расстояние между -й и -й платформой равно , аналогично расстояние между -й и -й платформой равно .
Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью – целым числом . Робот может перепрыгнуть с платформы на платформу , если . Аналогично, прыжок с -й платформы на -ю возможен, если . При этом после каждого прыжка ловкость робота увеличивается на .
Разработчики робота выбирают одну из платформ в качестве стартовой. Они считают эксперимент удачным, если робот может, совершив прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.
Входные данные
На первой строке ввода находится число ().
Вторая строка содержит одно целое число , которое описывает формат, в котором задан массив расстояний между платформами.
Если , то на третьей строке находятся целых чисел ().
Если , то на третьей строке находится число и три целых числа , и (). На четвертой строке находятся целых чисел (). Значения вычисляются по следующим формулам.
Если , то .
Если , то .
Здесь означает остаток от целочисленного деления, в языках C++,
Java и Python он обозначается символом %
.
Выходные данные
Требуется вывести два целых числа: минимальную допустимую начальную ловкость и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.
Если возможных стартовых платформ для минимальной начальной ловкости несколько, можно вывести любую из них.
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
0 | 0 | - | Тесты из условия |
1 | 15 | - | , , |
2 | 17 | 1 | , , |
3 | 10 | - | , , гарантируется, что оптимально начать с первой платформы |
4 | 20 | 1, 2, 3 | , |
5 | 5 | 3 | , гарантируется, что оптимально начать с первой платформы |
6 | 33 | 1, 2, 3, 4, 5 |
STDIN | STDOUT |
5 1 3 7 4 2 5 | 4 3 |
10 2 5 1 2 3 1 2 3 4 5 | 653 1 |
Примечание
Во втором примере массив расстояний между платформами равен . Значения от до вычисляются по формулам: