USACO 2026 - Circle of Cows
Xem PDFFarmer John có \(N\) (\(2\le N\le 1000\)) chú bò ở các vị trí phân biệt \(l_1,\dots,l_N\) trên một đường tròn có chu vi \(C\) (\(0\le l_1<l_2<\dots<l_N<C\), \(N\le C\le 10^9\)).
FJ sẽ chọn \(k\) cặp bò, với \(1\le k\le \lfloor N/2\rfloor\), và mỗi chú bò được chọn nhiều nhất một lần. Ông muốn chọn các cặp sao cho khoảng cách nhỏ nhất giữa hai chú bò cùng một cặp, tính dọc theo chu vi đường tròn, là lớn nhất có thể.
Với mỗi giá trị của \(k\), hãy giúp FJ xác định giá trị lớn nhất có thể của khoảng cách nhỏ nhất này.
Dữ liệu vào
Dòng đầu tiên chứa \(N\) và \(C\).
Dòng thứ hai chứa \(l_1,\dots,l_N\).
Dữ liệu ra
In ra một dòng gồm \(\lfloor N/2\rfloor\) số nguyên cách nhau bởi dấu cách, lần lượt là đáp án cho \(k=1,\dots,\lfloor N/2\rfloor\).
Ví dụ
Ví dụ 1
Input
4 100
0 25 50 75Output
50 50Note
Với \(k=1\), có thể ghép bò \(1\) với bò \(3\); khoảng cách giữa chúng dọc theo chu vi đường tròn là \(50\), nên đáp án là \(50\).
Với \(k=2\), có thể ghép bò \(1\) với bò \(3\) và bò \(2\) với bò \(4\); khoảng cách giữa hai chú bò trong mỗi cặp dọc theo chu vi đường tròn đều là \(50\), nên đáp án vẫn là \(50\).
Ví dụ 2
Input
4 100
0 1 2 99Output
3 2Note
Với \(k=1\), có thể ghép bò \(3\) với bò \(4\); khoảng cách giữa chúng dọc theo chu vi đường tròn là \(2+100-99=3\), nên đáp án là \(3\).
Với \(k=2\), có thể ghép bò \(1\) với bò \(3\) và bò \(2\) với bò \(4\). Trong mỗi cặp, khoảng cách giữa hai chú bò dọc theo chu vi đường tròn là \(2\), nên đáp án là \(2\).
Phân nhóm
- Các test 3–4: \(2l_N\le C\).
- Các test 5–6: \(N\le 20\).
- Các test 7–14: \(N\le 100\).
- Các test 15–22: Không có ràng buộc bổ sung.
Nguồn
USACO 2026 Contest 2, Platinum Division — bài gốc tiếng Anh “Circle of Cows”. Tác giả: Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1572
Kỳ thi:
- USACO 2026 - Kỳ thi 2 - Hạng Bạch Kim (30 Tháng 1., 2026)
Bình luận