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). 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.

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.

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > US Open > Platinum