2026 年 USACO竞赛 第二场比赛白金组问题一—Circle of Cows

Farmer John has N (2≤N≤1000) cows at distinct locations l1,…,lN along a circle of circumference C (0≤l1<l2<⋯<lN<C,N≤C≤109).

FJ will select k pairs of cows, where 1≤k≤⌊N/2⌋, 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.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and C.

The second line contains l1…lN .

OUTPUT FORMAT (print output to the terminal / stdout):

Output a single line with ⌊N/2⌋space-separated integers, with the answers for k=1…⌊N/2⌋in that order.

SAMPLE INPUT:

4 100
0 25 50 75

SAMPLE OUTPUT:

50 50

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

SAMPLE INPUT:

4 100
0 1 2 99

SAMPLE OUTPUT:

3 2

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

SCORING:

Inputs 3-4: 2lN≤C
Inputs 5-6: N≤20
Inputs 7-14: N≤100
Inputs 15-22: No additional constraints.

Problem credits: Benjamin Qi

历年学员USACO获奖战绩一览

2026赛季5位铂金级
2024-2025赛季5位铂金级
20238位铂金级

USACO 历年战绩

2026赛季战绩

  • 5位铂金级
  • 22位金级
  • 25位银级

2024–2025赛季战绩

翰林考点及辅导学生

  • 5位铂金级
  • 25位金级
  • 38位银级

2023–2024赛季战绩

  • 8位铂金级
  • 32位金级
  • 37位银级

2022–2023赛季战绩

  • 10位铂金级
  • 29位金级
  • 71位银级

篇幅有限,仅展示部分年份战绩。

在线咨询
微信咨询