A6142 | 「USACO 2024 US Open Platinum」Activating Robots

**题目译自 [USACO 2024 US Open Contest, Platinum](http://usaco.org/index.php?page=open24results) Problem 3. [Activating Robots](http://usaco.org/index.php?page=viewproblem2&cpid=1430)**

你和一个机器人最初位于周长为 $L\ (1\le L\le 10^9)$ 的圆上的 $0$ 点。你可以以每秒 $1$ 个单位的速度沿圆逆时针或顺时针移动。本题中的所有移动都是连续的。

你的目标是放置恰好 $R-1$ 个机器人，使得最后每两个连续的机器人之间的间距为 $L/R$（$2\le R\le 20$，$R$ 整除 $L$）。有 $N\ (1\le N\le 10^5)$ 个激活点，其中第 $i$ 个激活点位于离 $0$ 点逆时针方向的 $a_i\ (0\le a_i<L)$ 处。如果你当前位于某个激活点，则可以在该点瞬间放置一个机器人。所有机器人（包括原机器人）以每 $K\ (1\le K\le 10^6)$ 秒 $1$ 个单位的速度逆时针移动。

计算实现目标所需的最短时间。

第一行四个整数 $L,R,N,K$。

第二行 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出实现目标的最短时间。