Activating Robots
다이아몬드 IV의견: 0
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
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.
Problem credits: Benjamin Qi
SCORING
- Inputs 5-6: \(R=2\)
- Inputs 7-12: \(R\le 10, N\le 80\)
- Inputs 13-20: \(R\le 16\)
- Inputs 21-24: No additional constraints.
Problem credits: Benjamin Qi
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
622We 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
74We 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 114824 3 1 2
1648riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Platinum
평가 및 의견
Activating Robots
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Activating Robots