#PU1430. USACO 2024 US Open Contest, Platinum — Problem 3. Activating Robots

    ID: 1668 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open24来源:usaco.orgscoring:equal_test_cases二分答案

USACO 2024 US Open Contest, Platinum — Problem 3. Activating Robots

USACO 2024 US Open Contest, Platinum — Problem 3. Activating Robots

题目描述

You and a single robot are initially at point 00 on a circle with perimeter LL (1≤L≤1091 \le L \le 10^9). You can move either counterclockwise or clockwise along the circle at 11 unit per second. All movement in this problem is continuous. Your goal is to place exactly R−1R-1 robots such that at the end, every two consecutive robots are spaced L/RL/R away from each other (2≤R≤202\le R\le 20, RR divides LL). There are NN (1≤N≤1051\le N\le 10^5) activation points, the iith of which is located aia_i distance counterclockwise from 00 (0≤ai<L0\le a_i<L). If you are currently at an activation point, you can instantaneously place a robot at that point. All robots (including the original) move counterclockwise at a rate of 11 unit per KK seconds (1≤K≤1061\leq K\leq 10^6). Compute the minimum time required to achieve the goal.

输入格式

The first line contains LL, RR, NN, and KK. The next line contains NN space-separated integers a1,a2,…,aNa_1,a_2,\dots,a_N.

输出格式

The minimum time required to achieve the goal.

数据范围

Inputs 5-6: R=2R=2 Inputs 7-12: R≤10,N≤80R\le 10, N\le 80 Inputs 13-20: R≤16R\le 16 Inputs 21-24: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

10 2 1 2
6
22
We can reach the activation point at $6$ in $4$ seconds by going clockwise. At
this time, the initial robot will be located at $2$. Wait an additional $18$
seconds until the initial robot is located at $1$. Now we can place a robot to
immediately win.

样例 2

10 2 1 2
7
4
We can reach the activation point at $7$ in $3$ seconds by going clockwise. At
this time, the initial robot will be located at $1.5$. Wait an additional second
until the initial robot is located at $2$. Now we can place a robot to
immediately win.

样例 3

32 4 5 2
0 23 12 5 11
48

样例 4

24 3 1 2
16
48