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

Hẳn bạn đã từng nghe đến trò chơi "Oẳn tù tì" (Rock, Paper, Scissors). Những chú bò thích chơi một trò tương tự mà chúng gọi là "Móng guốc, Giấy, Kéo" (Hoof, Paper, Scissors).

Luật chơi "Móng guốc, Giấy, Kéo" rất đơn giản. Hai chú bò đấu với nhau. Cả hai cùng đếm đến ba rồi đồng thời ra một ký hiệu tượng trưng cho móng guốc, một tờ giấy hoặc một chiếc kéo. Móng guốc thắng kéo (vì móng guốc có thể đập nát kéo), kéo thắng giấy (vì kéo có thể cắt giấy), và giấy thắng móng guốc (vì móng guốc có thể bị giấy cứa). Ví dụ, nếu chú bò thứ nhất ra "móng guốc" và chú bò thứ hai ra "giấy", thì chú bò thứ hai thắng. Dĩ nhiên, hai chú bò cũng có thể hòa nếu cùng ra một ký hiệu.

Giờ đây có \(N\) (\(3\le N\le 2\cdot 10^5\)) chú bò muốn chơi Móng guốc, Giấy, Kéo, và mỗi chú độc lập sử dụng một chiến thuật lấy ngẫu nhiên theo một phân phối cố định nào đó. Cụ thể, chiến thuật của chú bò thứ \(i\) là ra móng guốc, giấy hoặc kéo với xác suất lần lượt là \(\left(\frac{h_i}{h_i+p_i+s_i}, \frac{p_i}{h_i+p_i+s_i}, \frac{s_i}{h_i+p_i+s_i} \right)\).

Có bao nhiêu bộ ba bò phân biệt \((A,B,C)\) sao cho xét trung bình thì \(A\) thắng \(B\), \(B\) thắng \(C\), và \(C\) thắng \(A\)? Hai bộ ba được coi là giống nhau nếu một bộ có thể thu được từ bộ kia bằng một phép dịch vòng.

Dữ liệu vào

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

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

\(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm \(h_i\), \(p_i\), \(s_i\) (\(0\le h_i,p_i,s_i\le 10^9\), \(h_i+p_i+s_i>0\)).

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

Dữ liệu ra

In ra số bộ ba.

Lưu ý: Do các số nguyên xuất hiện trong bài có thể rất lớn, bạn có thể cần sử dụng kiểu số nguyên 64 bit (chẳng hạn long long trong C/C++).

Ví dụ

2
4
1 0 0
1 0 0
0 1 0
0 0 1
10
20410069 21445597 257862632
114108992 287498302 113278897
607994331 143503714 631122722
337497016 270153603 320256324
633717786 631078144 493265815
202783212 612643590 560838949
713379081 42803063 58996167
293262767 470686180 220651551
656404313 408797935 345461691
959196297 827681918 591519393

2
32

Phân nhóm

• Các test 2–3: \(N\le 10\).
• Các test 4–9: \(N\le 7500\), tổng \(N\) trên tất cả các bộ test không vượt quá \(10^4\).
• Các test 10–21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 First Contest, Platinum Division — "Hoof, Paper, Scissors Triples". Tác giả: Richard Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1548

Có một hàng bò, ban đầu (tức tại thời điểm \(t=0\)) chỉ gồm chú bò \(0\) ở vị trí \(0\) (ở đây, một chú bò ở vị trí \(k\) nếu có \(k\) chú bò đứng trước nó). Tại thời điểm \(t\), với \(t=1,2,3,\dots\), chú bò ở vị trí \(0\) di chuyển đến vị trí \(\lfloor t/2\rfloor\), mỗi chú bò ở các vị trí \(1\dots \lfloor t/2\rfloor\) tiến lên trước một vị trí, và chú bò \(t\) gia nhập ở cuối hàng (vị trí \(t\)).

Hãy trả lời \(Q\) (\(1\le Q\le 10^5\)) truy vấn độc lập, mỗi truy vấn có dạng sau:

• Trong số các chú bò \(l_1\dots r_1\), có bao nhiêu chú nằm tại các vị trí \(l_2\dots r_2\) ngay sau thời điểm \(t\)? (\(0\le l_1\le r_1\le t\), \(0\le l_2\le r_2\le t\), \(t\le 10^{18}\))

Dữ liệu vào

Dòng đầu tiên chứa \(Q\), là số truy vấn.

\(Q\) dòng tiếp theo, mỗi dòng chứa năm số nguyên mô tả một truy vấn theo dạng "\(l_1\) \(r_1\) \(l_2\) \(r_2\) \(t\)".

Dữ liệu ra

In đáp án của mỗi truy vấn trên một dòng riêng.

Ví dụ

4
0 9 0 9 9
3 5 4 5 9
4 5 3 5 9
1 1 3 3 9

10
2
1
1

t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9

1
0 1000000000000000000 0 1000000000000000000 1000000000000000000

1000000000000000001

Phân nhóm

• Test 3: \(Q\le 1000\), \(t\le 100\).
• Các test 4–7: \(l_1=r_1\) đối với mọi truy vấn.
• Các test 8–14: \(r_1\leq 2\cdot l_1\) đối với mọi truy vấn.
• Các test 15–21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 First Contest, Platinum Division — "Lineup Counting Queries". Tác giả: Agastya Goel và Benjamin Qi. https://usaco.org/index.php?page=viewproblem2&cpid=1549

Nông dân John từng sơn một lưới hình chữ nhật trên mặt đất ở đồng cỏ của mình. Trong mỗi ô, ông sơn dấu \(+\) hoặc dấu \(-\) (lần lượt biểu diễn \(+1\) và \(-1\)).

Theo thời gian, lớp sơn phai dần, và giờ đây Nông dân John chỉ nhớ giá trị của một số ô. Tuy nhiên, Nông dân John vẫn nhớ một tính chất quan trọng của bức vẽ ban đầu:

Trong mỗi hàng và mỗi cột, tổng các giá trị của mọi đoạn con liên tiếp luôn nằm trong khoảng từ \(-1\) đến \(2\) (tính cả hai đầu).

Ví dụ, xét hàng \(\texttt{+ - - +}\). Hàng này không thỏa mãn điều kiện vì đoạn con \(\texttt{+ [ - - ] +}\) có tổng bằng \(-2\).

Ngược lại, hàng \(\texttt{- + + -}\) thỏa mãn điều kiện.

[ - ] + + -    tổng = -1
[ - + ] + -    tổng = 0
[ - + + ] -    tổng = +1
[ - + + - ]    tổng = 0

- [ + ] + -    tổng = +1
- [ + + ] -    tổng = +2
- [ + + - ]    tổng = +1
- + [ + ] -    tổng = +1
- + [ + - ]    tổng = 0
- + + [ - ]    tổng = -1

Hãy đếm số lưới khác nhau phù hợp với những gì Nông dân John nhớ.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 100\)), là số bộ test độc lập. Mỗi bộ test được mô tả như sau:

Dòng đầu tiên chứa \(R\), \(C\) và \(X\) (\(1\le R,C\le 5\cdot 10^5\), \(0\le X\le \min(10^5,RC)\)), cho biết lưới có kích thước \(R\times C\) và Nông dân John nhớ giá trị của \(X\) ô khác nhau trong lưới.

\(X\) dòng tiếp theo, mỗi dòng chứa một ký tự \(v\in\{+,-\}\), theo sau là hai số nguyên \(r\) và \(c\) (\(1\le r\le R\), \(1\le c\le C\)), cho biết giá trị tại hàng thứ \(r\), cột thứ \(c\) của lưới là \(v\). Đảm bảo rằng không có cặp có thứ tự \((r,c)\) nào xuất hiện nhiều hơn một lần trong cùng một bộ test.

Ngoài ra, đảm bảo rằng cả tổng \(R\) lẫn tổng \(C\) trên tất cả các bộ test đều không vượt quá \(10^6\), và tổng \(X\) trên tất cả các bộ test không vượt quá \(2\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in số lưới trên một dòng riêng.

Ví dụ

2
1 3 3

+ 1 3
+ 1 1
- 1 2
1 3 3
+ 1 1
+ 1 3
+ 1 2

1
0

1
2 2 0

7

++
++

++
+-

++
-+

+-
++

+-
-+

-+
++

-+
+-

Phân nhóm

• Các test 3–4: \(\min(R,C)=1\) đối với mọi bộ test.
• Các test 5–6: \(R,C\le 10\) đối với mọi bộ test.
• Các test 7–11: \(\sum \max(R,C)^2\le 10^6\).
• Các test 12–14: \(\sum RC\le 10^6\).
• Các test 15–22: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 First Contest, Platinum Division — "Pluses and Minuses". Tác giả: Alex Chen. https://usaco.org/index.php?page=viewproblem2&cpid=1550