Activating Robots

题目描述

你和一个机器人最初都位于周长为 $L$ 的圆上的点 $0$（$1 \le L \le 10^9$）。你可以沿圆逆时针或顺时针移动，速度为每秒 $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$ 个单位的速度逆时针移动（$1\leq K\leq 10^6$）。

请计算达成目标所需的最短时间。

输入格式

第一行包含 $L$、$R$、$N$ 和 $K$。 第二行包含 $N$ 个以空格分隔的整数 $a_1,a_2,\dots,a_N$。

输出格式

输出达成目标所需的最短时间。

10 2 1 2
6

22

10 2 1 2
7

4

32 4 5 2
0 23 12 5 11

48

24 3 1 2
16

48

提示

我们可以顺时针走，在 $4$ 秒内到达位于 $6$ 的激活点。此时，初始机器人将位于 $2$。再等待 $18$ 秒，直到初始机器人位于 $1$。现在我们可以放置一个机器人，从而立即获胜。

我们可以顺时针走，在 $3$ 秒内到达位于 $7$ 的激活点。此时，初始机器人将位于 $1.5$。再等待 $1$ 秒，直到初始机器人位于 $2$。现在我们可以放置一个机器人，从而立即获胜。

评分： 输入 5-6：$R=2$ 输入 7-12：$R\le 10, N\le 80$ 输入 13-20：$R\le 16$ 输入 21-24：无额外限制。 题目来源：Benjamin Qi

标签: USACO|2024|Platinum

来源

USACO|2024|Platinum