시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 5 | 3 | 3 | 60.000% |
Компания <<Flatland Dynamics>> разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из $n$ специальных платформ, пронумерованных от $1$ до $n$. Расстояние между $i$-й и $i+1$-й платформой равно $d_i$, аналогично расстояние между $n$-й и $1$-й платформой равно $d_n$.
Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью --- целым числом $a$. Робот может перепрыгнуть с платформы $i$ на платформу $i+1$, если $a \ge d_i$. Аналогично, прыжок с $n$-й платформы на $1$-ю возможен, если $a \ge d_n$. При этом после каждого прыжка ловкость робота увеличивается на $1$.
Разработчики робота выбирают одну из платформ в качестве стартовой. Они считают эксперимент удачным, если робот может, совершив $n$ прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.
На первой строке ввода находится число $n$ ($3 \le n \le 10^7$).
Вторая строка содержит одно целое число $f$, которое описывает формат, в котором задан массив расстояний между платформами.
Если $f = 1$, то на третьей строке находятся $n$ целых чисел $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le 10^{9}$).
Если $f = 2$, то на третьей строке находится число $m$ $\left(2 \le m \le \min(n, 10^5)\right)$ и три целых числа $x$, $y$ и $z$ ($0 \le x, y, z \le 10^9$). На четвертой строке находятся $m$ целых чисел $c_1, c_2, \ldots, c_m$ ($1 \le c_i \le 10^9$). Значения $d_i$ вычисляются по следующим формулам.
Если $1 \le i \le m$, то $d_i = c_i$.
Если $m + 1 \le i \le n$, то $d_i = \left((x\cdot d_{i-2} + y\cdot d_{i-1} + z)\bmod 10^9\right) + 1$.
Здесь $\bmod$ означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом <<\%
>>.
Требуется вывести два целых числа: минимальную допустимую начальную ловкость $a$ и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.
Если возможных стартовых платформ для минимальной начальной ловкости несколько, можно вывести любую из них.
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | $n \le 300$, $f=1$, $d_i \le 300$ |
2 | 17 | $n \le 5000$, $f=1$ |
3 | 10 | $n \le 100\,000$, $f=1$, гарантируется, что оптимально начать с первой платформы&&первая ошибка |
4 | 20 | $n \le 100\,000$, $f=1$ |
5 | 5 | $f=2$, гарантируется, что оптимально начать с первой платформы &3&первая ошибка |
6 | 33 | $f=2$ |
5 1 3 7 4 2 5
4 3
10 2 5 1 2 3 1 2 3 4 5
653 1
Во втором примере массив расстояний между платформами равен $[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$. Значения от $d_6$ до $d_{10}$ вычисляются по формулам:
$d_6 = \left((1\cdot d_4+2\cdot d_5 + 3) \bmod 10^9\right)+1 = \left((1\cdot 4+2\cdot 5+3)\bmod 10^9\right)+1=18$
$d_7 = \left((1\cdot d_5+2\cdot d_6 + 3) \bmod 10^9\right)+1 = \left((1\cdot 5+2\cdot 18+3)\bmod 10^9\right)+1=45$
$d_8 = \left((1\cdot d_6+2\cdot d_7 + 3) \bmod 10^9\right)+1 = \left((1\cdot 18+2\cdot 45+3)\bmod 10^9\right)+1=112$
$d_9 = \left((1\cdot d_7+2\cdot d_8 + 3) \bmod 10^9\right)+1 = \left((1\cdot 45+2\cdot 112+3)\bmod 10^9\right)+1=273$
$d_{10} = \left((1\cdot d_8+2\cdot d_9 + 3) \bmod 10^9\right)+1 = \left((1\cdot 112+2\cdot 273+3)\bmod 10^9\right)+1=662$
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2022 2번