Circle of Cows
플래티넘 II의견: 0
Farmer John has \(N\) (\(2\le N\le 1000\)) cows at distinct locations
\(l_1,\dots, l_N\) along a circle of circumference \(C\)
(\(0\le l_1 < l_2 < \dots < l_N
FJ will select \(k\) pairs of cows, where \(1\le k\le \lfloor N/2\rfloor\), and no
cow is selected more than once. He wants to select the pairs such that the
minimum distance between any two cows in the same pair along the circumference
of the circle is maximized.
For each value of \(k\), help FJ determine the maximum possible minimum distance.
Problem credits: Benjamin Qi
SCORING
- Inputs 3-4: \(2l_N \le C\)
- Inputs 5-6: \(N\le 20\)
- Inputs 7-14: \(N\le 100\)
- Inputs 15-22: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\) and \(C\).
The second line contains \(l_1\dots l_N\).
Output a single line with \(\lfloor N/2\rfloor\) space-separated integers, with the
answers for \(k=1\dots \lfloor N/2\rfloor\) in that order.
4 100
0 25 50 7550 50For \(k = 1\), cow 1 can be paired to cow 3, which is distance \(50\) away along the
circumference of the circle, making the answer \(50\).
For \(k = 2\), cow 1 can be paired to cow 3, and cow 2 can be paired to cow 4,
which is distance \(50\) away from it along the circumference of the circle,
making the answer still \(50\).
4 100
0 1 2 993 2For \(k = 1\), cow 3 can be paired to cow 4, which is distance \(2 + 100 - 99 = 3\)
away from it along the circumference of the circle, making the answer \(3\).
For \(k = 2\), cow 1 can be paired to cow 3 and cow 2 can be paired to cow 4. Each
of these pairs contains two cows at a distance of \(2\) from each other along the
circumference of the circle, making the answer \(2\).
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Platinum
평가 및 의견
Circle of Cows
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Circle of Cows