「USACO 2024 US Open Platinum」Activating Robots

题目描述

题目译自 USACO 2024 US Open Contest, Platinum Problem 3. Activating Robots

你和一个机器人最初位于周长为 $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$。

输出格式

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

样例 1

输入

10 2 1 2
6

输出

22

说明
我们可以花 $4$ 秒钟沿顺时针方向到达 $6$ 处的激活点。此时，最初的机器人会位于 $2$。等待 $18$ 秒直到初始机器人位于 $1$。此时我们可以放置机器人，然后达成目标。

样例 2

输入

10 2 1 2
7

输出

4

说明
我们可以花 $3$ 秒沿顺时针方向到达 $7$ 处的激活点。此时，最初的机器人会位于 $1.5$。等待一秒直到初始机器人位于 $2$。此时我们可以放置机器人，然后达成目标。

样例 3

输入

32 4 5 2
0 23 12 5 11

输出

48

样例 4

输入

24 3 1 2
16

输出

48

数据范围与提示

• 测试点 5-6：$R=2$
• 测试点 7-12：$R\le 10,N\le 80$
• 测试点 13-20：$R\le 16$
• 测试点 21-24：无附加限制

供题：Benjamin Qi