P10087 [ROIR 2022] 跳跃机器人 (Day 1)

翻译自 [ROIR 2022 D1T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day1.pdf)。 某公司正在开发一种跳跃机器人。为了测试机器人，他们在一个多边形平台上设置了一个由 $n$ 个特殊平台组成的环形路线，平台从 $1$ 到 $n$ 编号。第 $i$ 个平台与 $i+1$ 个平台之间的距离为 $d_i$，最后一个平台与第一个平台之间的距离为 $d_n$（假设长度分别为 $d_1,d_2,\dots,d_n$ 的边可以组成一个 $n$ 边形）。 机器人配备了人工智能，在测试过程中学习跳得更远。在任何时刻，机器人通过一个整数 $a$ 来表示它的灵敏度。如果 $a$ 大于等于 $d_i$，机器人可以从平台 $i$ 跳到平台 $i+1$；同样地，如果 $a$ 大于等于 $d_n$，机器人可以从最后一个平台跳到第一个平台。每次跳跃后，机器人的灵敏度增加 $1$。

机器人的开发人员选择一个平台作为起始平台。如果机器人可以完成 $n$ 次跳跃，回到原来的平台，他们认为实验是成功的。开发人员需要确定机器人的最小起始灵敏度是多少，并选择哪个平台作为起始平台。

第一行包含一个整数 $n$。 第二行包含一个整数 $f$。 - 如果 $f = 1$，则第三行包含 $n$ 个整数 $d_1, d_2, \dots , d_n$，意义见题目背景。 - 如果 $f = 2$，则第三行包含一个整数 $m$，以及三个整数 $x,y,z$。第四行包含 $m$ 个整数 $c_1, c_2, \dots , c_m$。此时距离值 $d_i$ 根据以下公式计算： - 如果 $1 \le i \le m$，则 $d_i = c_i$。 - 如果 $m + 1 \le i \le n$，则 $d_i = ((x \times d_{i−2} + y \times d_{i−1} + z) \bmod 10^9) + 1$。

输出两个整数，即最小允许的起始灵敏度 $a$ 和可用于放置机器人的起始平台编号。如果有多个最小起始灵敏度对应的起始平台，可以输出任意一个。

样例说明： 在第二个示例中，距离数组为 $[1, 2, 3, 4, 5, 18, 45, 112, 273, 662]$。 根据公式计算 $d_6$ 到 $d_{10}$ 的值： - $d_6 = ((1 \cdot d_4 + 2 \cdot d_5 + 3) \bmod 10^9) + 1 = ((1 \cdot 4 + 2 \cdot 5 + 3) \bmod 10^9) + 1 = 18$； - $d_7 = ((1 \cdot d_5 + 2 \cdot d_6 + 3) \bmod 10^9) + 1 = ((1 \cdot 5 + 2 \cdot 18 + 3) \bmod 10^9) + 1 = 45$； - $d_8 = ((1 \cdot d_6 + 2 \cdot d_7 + 3) \bmod 10^9) + 1 = ((1 \cdot 18 + 2 \cdot 45 + 3) \bmod 10^9) + 1 = 112$； - $d_9 = ((1 \cdot d_7 + 2 \cdot d_8 + 3) \bmod 10^9) + 1 = ((1 \cdot 45 + 2 \cdot 112 + 3) \bmod 10^9) + 1 = 273$； - $d_{10} = ((1 \cdot d_8 + 2 \cdot d_9 + 3) \bmod 10^9) + 1 = ((1 \cdot 112 + 2 \cdot 273 + 3) \bmod 10^9) + 1 = 662$。 本题使用捆绑测试。 | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $0$ | $15$ | $n\le300,f=1,d\le300$ | | $1$ | $17$ | $n\le5000,f=2$ | | $2$ | $10$ | $n\le100000,f=1$ 且保证从第一个平台开始跳是最佳选择 | | $3$ | $20$ | $n\le100000,f=1$ | | $4$ | $5$ | $f=2$ 且保证从第一个平台开始跳是最佳选择 | | $5$ | $33$ | $f=2$ | 对于 $100\%$ 的数据，$3 \le n \le 10^7$。当 $f=1$ 时 $1 \le d_i \le 10^9$，当 $f=2$ 时 $2 \le m \le \min(n, 10^5)$，$0 \le x, y, z \le 10^9$，$1 \le c_i \le 10^9$。 注：本题的算法标签部分参考了官方题解中用到的解法。