| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 14 | 8 | 7 | 77.778% |
You and a single robot are initially at point 0ドル$ on a circle with perimeter $L$ (1ドル \le L \le 10^9$). 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ドル\le R\le 20,ドル $R$ divides $L$). There are $N$ (1ドル\le N\le 10^5$) activation points, the $i$th of which is located $a_i$ distance counterclockwise from 0ドル$ (0ドル\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 1ドル$ unit per $K$ seconds (1ドル\leq K\leq 10^6$).
Compute the minimum time required to achieve the goal.
The first line contains $L,ドル $R,ドル $N,ドル and $K$.
The next line contains $N$ space-separated integers $a_1,a_2,\dots,a_N$.
The minimum time required to achieve the goal.
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.
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.
32 4 5 2 0 23 12 5 11
48
24 3 1 2 16
48