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

Bạn có một tập hợp các miền tam giác lát kín một mặt phẳng hai chiều vô hạn. Cách lát được định nghĩa như sau (xem hình minh họa để hiểu rõ hơn):

• Nhắc lại rằng công thức Euler phát biểu \(e^{ix}=\cos(x)+i\sin(x)\) với \(x\) thực. Trước tiên, với mọi số nguyên \(x,y\), vẽ một đỉnh tại \(x+y\exp(\pi i/3)\) trên mặt phẳng phức.
• Sau đó, với mỗi bộ ba đỉnh ở bước trên tạo thành một tam giác đều có độ dài cạnh bằng \(1\), vẽ các cạnh tạo nên đường biên của tam giác. Ngoài ra, vẽ một đỉnh tại tâm tam giác và các cạnh nối tâm tam giác với từng đỉnh trong ba đỉnh ngoài.

Bạn được cho \(N\) (\(2\le N\le 2\cdot 10^5\)) điểm đầu vào, mỗi điểm nằm hoàn toàn bên trong một miền nào đó (tức là không nằm trên bất kỳ đỉnh hay cạnh nào). Với mỗi cặp điểm đầu vào, định nghĩa khoảng cách giữa chúng là số cạnh ít nhất bị cắt qua khi vẽ một đường đi từ điểm này đến điểm kia mà không đi qua bất kỳ đỉnh nào.

Hãy in tổng khoảng cách của tất cả \(N(N-1)/2\) cặp điểm đầu vào.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(T\ge 1\)), là số bộ kiểm thử độc lập. Mỗi bộ kiểm thử được mô tả như 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 \(x\), \(y\) và \(z\) (\(0\le x,y<10^6\), \(0\le z<12\)), biểu diễn một điểm tại \(x+y\exp(\pi i/3)+\epsilon\cdot\exp((1+2z)\pi i/12)\) trên mặt phẳng phức (trong đó \(\epsilon\) là một số dương nhỏ).

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

Dữ liệu ra

Với mỗi bộ kiểm thử, in trên một dòng mới tổng khoảng cách của tất cả \(N(N-1)/2\) cặp điểm.

Ví dụ

6
2
0 0 0
0 0 0
2
0 0 0
1 1 7
2
0 0 0
0 0 6
3
0 0 1
0 0 5
0 0 9
2
0 2 11
1 1 1
2
2 0 11
1 1 1

0
3
6
12
2
6

Phân nhóm

• Dữ liệu 2–5: \(N\le 10\), \(0\le x,y<5\).
• Dữ liệu 6–13: \(N\le 10\).
• Dữ liệu 14–21: \(T=1\).

Nguồn

USACO 2026 Contest 3, Platinum — “All Pairs Shortest Paths” — tác giả: Benjamin Qi.
https://usaco.org/index.php?page=viewproblem2&cpid=1596

Bessie đang chơi một trò chơi điện tử, trong đó cô cần đánh bại một hàng gồm \(N\) kẻ địch có lượng HP ban đầu được cho bởi dãy \(v_1\dots v_N\) (\(1\le N\le 2\cdot 10^5\), \(0\le v_i\le 10^9\)). Trong một đòn tấn công, cô có thể thực hiện lần lượt các bước sau:

• Chọn \(i\) sao cho kẻ địch thứ \(i\) vẫn còn sống (tức là \(v_i>0\)).
• Gây một điểm sát thương cho kẻ địch thứ \(i\) và tất cả kẻ địch kề với nó mà vẫn còn sống. Cụ thể, với mỗi \(j\in[\max(i-1,1),\min(i+1,N)]\), nếu \(v_j>0\) thì trừ \(v_j\) đi một.

Hãy giúp Bessie xác định số đòn tấn công ít nhất cần dùng để đánh bại tất cả kẻ địch (tức là giảm mọi \(v_i\) về \(0\)).

Ngoài ra, bạn được cho một tham số \(M\) (\(0\le M\le 2\)). Nếu \(M>0\), hãy in ra một cách thực hiện đạt số đòn tấn công tối thiểu với số lượt tấn công liên tiếp nhỏ, trong đó một lượt là việc tấn công cùng một kẻ địch liên tiếp.

Gọi \(R\) là số lượt trong cách thực hiện của bạn. Cách thực hiện phải có định dạng sau: in \(R\) trên một dòng riêng, sau đó là \(R\) dòng, mỗi dòng chứa hai số nguyên \(i\) và \(r\) (\(1\le i\le N\), \(0\le r\le 10^9\)), có nghĩa là Bessie tấn công kẻ địch thứ \(i\) liên tiếp \(r\) lần.

Tùy theo giá trị của \(M\), \(R\) phải thỏa mãn một trong các ràng buộc sau:

• \(M=1\): \(R\le 2N\) (có thể chứng minh rằng một cách thực hiện như vậy luôn tồn tại).
• \(M=2\): \(R\le f(N)\), trong đó \(f(N)\) là giá trị lớn nhất, xét trên mọi dãy có độ dài \(N\), của số lượt tối thiểu.

Dữ liệu vào

Mỗi dữ liệu vào gồm \(T\) (\(1\le T\le 10^5\)) bộ kiểm thử độc lập. Dòng đầu tiên chứa \(T\) và \(M\).

Mỗi bộ kiểm thử được mô tả như sau:

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

Dòng thứ hai chứa \(v_1\dots v_N\).

Đảm bảo rằng tổng \(N\) trên tất cả các bộ kiểm thử không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ kiểm thử, ở dòng đầu tiên, in số đòn tấn công tối thiểu.

Sau đó, nếu \(M>0\), in thêm \(R+1\) dòng như mô tả ở trên. Mọi cách thực hiện hợp lệ đều được chấp nhận.

Ví dụ

2 0
1
10
3
6 1 7

10
12

2 1
1
10
3
6 1 7

10
2
1 0
1 10
12
4
2 1
1 5
3 2
3 4

2 2
1
10
3
6 1 7

10
1
1 10
12
3
2 1
3 6
1 5

Phân nhóm

• Dữ liệu 4–7: \(M=0\).
• Dữ liệu 8–11: \(M=1\).
• Dữ liệu 12–13: \(M=2\).

Nguồn

USACO 2026 Contest 3, Platinum — “Blast Damage” — tác giả: Benjamin Qi.
https://usaco.org/index.php?page=viewproblem2&cpid=1597

Bạn được cho các số nguyên \(N,Q\) (\(1\leq N,Q\leq 2\cdot 10^5\)) và \(Q\) ràng buộc được biểu diễn bởi bốn số nguyên \(t_i,l_i,r_i,k_i\) (\(1\leq t_i\leq 2\), \(1\leq l_i\leq r_i\leq N\), \(0\leq k_i\leq 10^9\), mọi \(k_i\) đôi một khác nhau).

Hãy xây dựng một mảng \(a\) gồm \(N\) số nguyên nằm trong khoảng từ \(0\) đến \(10^9\) sao cho với mọi \(1\leq i\leq Q\), \(\min a[l_i\dots r_i]=k_i\) nếu \(t_i=1\), và \(\max a[l_i\dots r_i]=k_i\) nếu \(t_i=2\). Nếu có nhiều mảng hợp lệ, hãy in ra một mảng bất kỳ. Nếu không tồn tại mảng hợp lệ, in \(-1\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(T\) (\(1\leq T\leq 10^4\)), biểu diễn số bộ kiểm thử độc lập.

Với mỗi bộ kiểm thử, dòng đầu tiên chứa hai số nguyên \(N,Q\).

\(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(t_i\), \(l_i\), \(r_i\), \(k_i\).

Đảm bảo rằng cả tổng \(N\) lẫn tổng \(Q\) trên tất cả các bộ kiểm thử đều không vượt quá \(2\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ kiểm thử, nếu tồn tại một mảng hợp lệ, in \(N\) số nguyên \(a_1\dots a_N\), cách nhau bởi dấu cách, trên một dòng mới. Nếu không, in \(-1\).

Ví dụ

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

-1
1 2
0 3 0 0

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

1 2
-1
3 3 0 2 2
1 5 2 6

Phân nhóm

• Dữ liệu 3–4: \(N,Q\leq 100\) và mọi \(t_i\) trong cùng một bộ kiểm thử đều bằng nhau.
• Dữ liệu 5–6: mọi \(t_i\) trong cùng một bộ kiểm thử đều bằng nhau.
• Dữ liệu 7–10: \(N,Q\leq 100\).
• Dữ liệu 11–14: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Platinum — “Min Max Subarrays II” — tác giả: Charlie Yang.
https://usaco.org/index.php?page=viewproblem2&cpid=1598