You and a single robot are initially at point 0 on a circle with perimeter L
(1≤L≤109). You can move either counterclockwise or clockwise along the circle at 1 unit per second. All movement in this problem is continuous.
Your goal is to place exactly R−1 robots such that at the end, every two consecutive robots are spaced L/R away from each other (2≤R≤20, R
divides L). There are N (1≤N≤105) activation points, the ith of which is located ai distance counterclockwise from 0(0≤ai<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 1 unit per K seconds (1≤K≤106).
Compute the minimum time required to achieve the goal.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains L, R, N, and K.
The next line contains N
space-separated integersa1,a2,…,aN.
OUTPUT FORMAT (print output to the terminal / stdout):
The minimum time required to achieve the goal.
SAMPLE INPUT:
10 2 1 2
6
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
10 2 1 2
7
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
32 4 5 2
0 23 12 5 11
SAMPLE OUTPUT:
48
SAMPLE INPUT:
24 3 1 2
16
SAMPLE OUTPUT:
48
SCORING:
Inputs 5-6: R=2
Inputs 7-12: R≤10,N≤80
Inputs 13-20: R≤16
Inputs 21-24: No additional constraints.
Problem credits: Benjamin Qi
扫码免费领取USACO试题答案+详细解析
咨询一对一备赛规划
