USACO 2026 - Kỳ thi 2 - Hạng Bạch Kim

Farmer 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ụ

4 100
0 25 50 75

50 50

4 100
0 1 2 99

3 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

Lưu ý: Giới hạn thời gian của bài này là 6 giây, gấp ba lần mặc định. Giới hạn bộ nhớ của bài này là 512 MB, gấp đôi mặc định.

Farmer John có \(N\) (\(1\leq N\leq 5000\)) chú bò đứng quanh một đường đua hình tròn được chia thành \(M\) (\(1\leq M\leq 10^6\)) vị trí cách đều nhau, đánh số từ \(0\) đến \(M-1\) theo chiều kim đồng hồ. Ban đầu, bò \(i\) đứng tại vị trí \(x_i\), trong đó \(0=x_1<x_2<\dots<x_N<M\).

Với mỗi \(1\leq i\leq N\), bò \(i\) sẽ độc lập chọn ngẫu nhiên quay mặt theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, với xác suất riêng của chú bò đó. Sau khi chọn hướng ban đầu, mỗi chú bò bắt đầu di chuyển liên tục theo hướng ấy với vận tốc không đổi là một vị trí mỗi phút. Mỗi khi hai chú bò gặp nhau (tức là cùng chiếm một vị trí), chúng bật ngược lại khỏi nhau: lập tức đảo hướng rồi tiếp tục di chuyển với cùng vận tốc theo hướng mới.

Farmer John muốn biết bò \(1\) sẽ ở đâu. Với mỗi \(0\leq i<M\), hãy tìm xác suất bò \(1\) ở vị trí \(i\) sau \(K\) (\(1\leq K\leq 10^{18}\)) phút.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\leq T\leq 100\)), là số bộ test độc lập. Mỗi bộ test có định dạng như sau:

Dòng đầu tiên của mỗi bộ test chứa \(N\) (\(1\leq N\leq 5000\)), \(M\) (\(1\leq M\leq 10^6\)) và \(K\) (\(1\leq K\leq 10^{18}\)).

Dòng thứ hai chứa \(N\) số nguyên \(p_1,\dots,p_N\) (\(0\leq p_i<10^9+7\)), trong đó nếu \(\frac{a_i}{b_i}\) là xác suất bò \(i\) đi theo chiều kim đồng hồ thì \(p_i\cdot b_i\equiv a_i\pmod{10^9+7}\).

Dòng thứ ba, cũng là dòng cuối cùng, chứa \(N\) số nguyên \(x_1,x_2,\dots,x_N\).

Đảm bảo rằng tổng \(N^2\) trên tất cả các bộ test không vượt quá \(5000^2\), và tổng \(M\) trên tất cả các bộ test không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in ra một dòng mới. Dòng tương ứng với mỗi bộ test có định dạng như sau:

Với mọi \(0\leq i<M\), gọi \(\frac{p_i}{q_i}\) là xác suất bò \(1\) ở vị trí \(i\) sau \(K\) phút. In ra \(M\) số nguyên cách nhau bởi dấu cách \(p_iq_i^{-1}\pmod{10^9+7}\) (trong đó \(p_iq_i^{-1}\cdot q_i\equiv p_i\pmod{10^9+7}\)).

Ví dụ

3
2 2 1
500000004 500000004
0 1
3 3 1
500000004 500000004 500000004
0 1 2
5 10 13
500000004 1 500000004 0 500000004
0 3 4 7 9

500000004 500000004
500000004 250000002 250000002
0 0 0 125000001 375000003 0 125000001 375000003 0 0

Phân nhóm

• Test 2: \(K\leq 100\), \(N\leq 10\).
• Test 3: \(N\leq 10\).
• Các test 4–7: \(\sum N^3\leq 500^3\).
• Các test 8–11: \(K<\frac{M}{2}\).
• Các test 12–15: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Platinum Division — bài gốc tiếng Anh “Cow Circle”. Tác giả: Sujay Konda. https://usaco.org/index.php?page=viewproblem2&cpid=1573

Farmer Nhoj đã nhốt Bessie trên một cây có gốc gồm \(N\) (\(2\le N\le 2\cdot 10^5\)) đỉnh, trong đó đỉnh \(1\) là gốc. Trong sợ hãi và cô độc, mỗi giây Bessie thực hiện bước di chuyển sau:

• Nếu đỉnh hiện tại của Bessie không có con, cô sẽ di chuyển đến một tổ tiên được chọn ngẫu nhiên của đỉnh hiện tại (không tính chính đỉnh đó).
• Nếu không, Bessie sẽ di chuyển đến một đỉnh con được chọn ngẫu nhiên của đỉnh hiện tại.

Ban đầu, Bessie ở đỉnh \(x\), và lối thoát duy nhất của cô nằm tại đỉnh \(y\) (\(1\le x,y\le N\)). Với \(Q\) (\(1\le Q\le 2\cdot 10^5\)) truy vấn độc lập gồm \(x\) và \(y\), hãy tính kỳ vọng số giây để Bessie đến đỉnh \(y\) lần đầu tiên nếu cô bắt đầu tại đỉnh \(x\), theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

Dòng tiếp theo chứa \(N-1\) số nguyên \(p_2,\ldots,p_N\) mô tả cây (\(1\le p_i<i\)). Với mỗi \(2\le i\le N\), có một cạnh nối đỉnh \(i\) và đỉnh \(p_i\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\), biểu diễn các đỉnh của truy vấn đó.

Dữ liệu ra

Với mỗi truy vấn, in ra kỳ vọng số giây để Bessie đến đỉnh \(y\) lần đầu tiên khi bắt đầu tại đỉnh \(x\), theo modulo \(10^9+7\).

Ví dụ

5 5
1 2 2 1
1 1
2 1
3 1
4 1
5 1

0
4
3
3
1

5 5
1 2 2 1
1 1
1 2
1 3
1 4
1 5

0
3
500000011
500000011
6

13 10
1 2 2 4 3 1 5 6 4 7 8 10
1 12
10 6
5 12
1 13
13 10
6 4
7 12
3 1
12 8
2 1

166666700
21
2
166666701
500000023
18
166666704
750000018
800000021
500000018

Phân nhóm

• Các test 4–8: Với mọi truy vấn, \(y=1\).
• Các test 9–13: Với mọi truy vấn, \(x=1\).
• Các test 14–18: Với mỗi \(2\le i\le N\), \(p_i\) được chọn ngẫu nhiên đều trong đoạn \([1,i-1]\).
• Các test 19–23: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Platinum Division — bài gốc tiếng Anh “Dynamic Instability”. Tác giả: Avnith Vijayram. https://usaco.org/index.php?page=viewproblem2&cpid=1574