USACO 2026 - Kỳ thi 1 - Hạng Vàng

Có \(N\) (\(1\le N\le 2\cdot 10^5\)) con bò được đánh số \(1\dots N\) trong trang trại của Farmer John, mỗi con bò sống trong một chuồng riêng. Mỗi con bò \(i\) có một người bạn thân nhất \(a_i\) (\(1\le a_i\le N\)). Một con bò có thể là bạn thân nhất của chính nó, và nhiều con bò có thể có cùng một người bạn thân nhất. Những con bò rất thích tiệc tùng, vì vậy chúng quyết định tổ chức tiệc trong \(M\) (\(1\le M\le 2\cdot 10^5\)) đêm liên tiếp.

Vào đêm thứ \(i\), bò \(c_i\) sẽ quyết định tổ chức một bữa tiệc loại \(t_i\) tại chuồng của mình, với \(t_i\in \texttt{"COW"}\). Bữa tiệc này cũng sẽ tồn tại trong tất cả các đêm sau đó, cho đến khi bò \(c_i\) quyết định tổ chức một bữa tiệc thuộc loại khác.

Mỗi đêm, mỗi con bò sẽ cố gắng đi đến một bữa tiệc. Nếu một con bò không tổ chức tiệc, nó sẽ kiểm tra chuồng của người bạn thân nhất; nếu ở đó không có tiệc, nó sẽ đi theo người bạn thân nhất đến bất cứ nơi nào người bạn ấy đang đi (người bạn này cũng có thể đi theo bạn thân nhất của mình, và cứ tiếp tục như vậy). Có thể một con bò không bao giờ tìm thấy bữa tiệc nào và khi đó sẽ bỏ cuộc trong đêm ấy.

Với mỗi đêm, hãy tính số bò cuối cùng đến dự bữa tiệc loại \(C\), \(O\) và \(W\), theo thứ tự đó.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), số lượng bò.

Dòng thứ hai chứa \(a_1,\dots,a_N\), trong đó \(a_i\) là người bạn thân nhất của bò \(i\).

Dòng thứ ba chứa \(M\), số lượng đêm.

\(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(c_i\) (\(1\le c_i\le N\)) và một ký tự \(v_i\), lần lượt biểu thị con bò tổ chức tiệc và loại của bữa tiệc.

Dữ liệu ra

In ra \(M\) dòng, trong đó dòng thứ \(i\) gồm \(3\) số nguyên cách nhau bởi dấu cách, lần lượt là số bò đi đến các bữa tiệc loại \(C\), \(O\) và \(W\) trong đêm thứ \(i\).

Ví dụ

5
2 3 4 5 4
4
2 C
4 C
4 W
2 O

2 0 0
5 0 0
2 0 3
0 2 3

Phân nhóm

• Dữ liệu vào 2: \(N,M\leq 100\).
• Dữ liệu vào 3–4: \(N,M\leq 4000\).
• Dữ liệu vào 5–9: \(\{a_i\}\) là một hoán vị của \(\{1,\dots,N\}\).
• Dữ liệu vào 10–21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 1, Gold Division — “COW Traversals”. Tác giả đề: Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1545

Bessie đã thách đấu Farmer John trong một trò chơi với những xô sữa! Có \(N\) \((2\leq N\leq 2\cdot 10^5)\) xô sữa xếp thành một hàng. Xô thứ \(i\) tính từ bên trái ban đầu chứa \(a_i\) \((0\leq a_i\leq 10^9)\) gallon sữa.

Trò chơi gồm hai giai đoạn:

Giai đoạn 1: Farmer John có thể đổi chỗ hai xô kề nhau bất kỳ. Ông có thể thực hiện bao nhiêu lần đổi chỗ tùy thích, nhưng mỗi lần tốn \(1\) đồng xu.

Giai đoạn 2: Sau khi đổi chỗ, Farmer John thực hiện thao tác sau cho đến khi chỉ còn lại một xô: Chọn hai xô kề nhau có lượng sữa là \(a_i\) và \(a_{i+1}\), rồi thay cả hai xô bằng một xô đặt tại vị trí của chúng và chứa \(\frac{a_i+a_{i+1}}2\) gallon sữa.

Hãy xác định số đồng xu ít nhất Farmer John phải dùng trong giai đoạn đổi chỗ để tối đa hóa lượng sữa trong xô cuối cùng sau khi hoàn tất mọi phép gộp.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(T\) \((1\leq T\leq 100)\): số lượng bộ test độc lập.

Sau đó, với mỗi bộ test, dòng đầu tiên chứa một số nguyên \(N\): số lượng xô sữa. Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\), cách nhau bởi dấu cách: số gallon sữa trong mỗi xô.

Đảm bảo tổng \(N\) trên tất cả các bộ test không vượt quá \(5\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in ra số đồng xu ít nhất Farmer John phải dùng để tối đa hóa lượng sữa trong xô cuối cùng.

Ví dụ

2
3
0 0 1
3
0 1 0

0
1

4
4
9 4 9 2
6
0 0 2 0 0 0
3
2 0 1
9
3 3 3 10 3 2 13 14 13

1
2
0
3

Phân nhóm

• Dữ liệu vào 3–4: \(a_i\leq 1\) và \(N\leq 2000\) (tổng \(N\leq 5000\)).
• Dữ liệu vào 5–6: \(a_i\leq 1\).
• Dữ liệu vào 7–9: \(N\leq 2000\) (tổng \(N\leq 5000\)).
• Dữ liệu vào 10–14: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 1, Gold Division — “Milk Buckets”. Tác giả đề: Charlie Yang. https://usaco.org/index.php?page=viewproblem2&cpid=1546

Có \(N\) (\(1\leq N\leq 10^6\)) con bò tại trại hè dành cho bò, được đánh số \(1\dots N\). Mỗi con bò là một trại viên hoặc một huấn luyện viên.

Một tập con không rỗng của các con bò sẽ được chọn để tham gia một chuyến dã ngoại. Nếu con bò thứ \(i\) được chọn, nó sẽ di chuyển đến vị trí \(p_i\) (\(0\leq p_i\leq 10^9\)) trên một trục số, trong đó mảng \(p\) tăng nghiêm ngặt.

Một tập con không rỗng của các con bò được gọi là "tốt" nếu với mỗi trại viên được chọn, có một huấn luyện viên được chọn nằm trong phạm vi \(D\) đơn vị về bên trái, kể cả điểm trại viên đang đứng (\(0\leq D\leq 10^9\)). Có bao nhiêu tập con tốt, theo modulo \(10^9+7\)?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(p_i\) và \(o_i\). \(p_i\) biểu thị vị trí mà con bò thứ \(i\) sẽ di chuyển đến. \(o_i=1\) có nghĩa con bò thứ \(i\) là huấn luyện viên, còn \(o_i=0\) có nghĩa con bò thứ \(i\) là trại viên.

Đảm bảo các giá trị \(p_i\) được cho theo thứ tự tăng nghiêm ngặt.

Dữ liệu ra

In ra số tập con tốt theo modulo \(10^9+7\).

Ví dụ

6 1
3 1
4 0
6 1
7 1
9 0
10 0

11

20 24
3 0
14 0
17 1
20 0
21 0
22 1
28 0
30 0
32 0
33 1
38 0
40 0
52 0
58 0
73 0
75 0
77 1
81 1
84 1
97 0

13094

Phân nhóm

• Dữ liệu vào 3: \(N=20\).
• Dữ liệu vào 4: \(D=0\).
• Dữ liệu vào 5–8: \(N\leq 5000\).
• Dữ liệu vào 9–16: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 1, Gold Division — “Supervision”. Tác giả đề: Agastya Goel, Eva Zhu và Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1547