USACO 2026 - Kỳ thi 3 - Hạng Bạc

Nông dân John đang chơi một trò chơi bài chiến thuật nổi tiếng với cô bò Bessie thân yêu. FJ có \(N\) (\(2\le N\le 2\cdot 10^5\)) lá bài, được đánh số từ \(1\) đến \(N\). Nếu FJ muốn đánh lá bài thứ \(i\), lá bài đó tốn \(a_i\) (\(1 \leq a_i \leq 10^9\)) moolixir.

Tại mọi thời điểm, tay bài của FJ luôn gồm \(H\) lá (\(1\le H<N\)). Ban đầu, tay bài gồm các lá từ \(1\) đến \(H\). Những lá còn lại nằm trong một hàng đợi rút bài. Mỗi khi FJ đánh một lá trên tay, anh sẽ rút lá ở đầu hàng đợi lên tay để thay thế, rồi đưa lá vừa đánh xuống cuối hàng đợi. Ban đầu, các lá từ \(H+1\) đến \(N\) được xếp theo đúng thứ tự đó từ đầu đến cuối hàng đợi.

Trong trò chơi này, thời gian được tính bằng số giây nguyên. Trò chơi bắt đầu ở thời điểm \(0\), khi FJ có \(0\) moolixir. Ngay trước mỗi thời điểm nguyên \(t=1,2,3,\dots\), lượng moolixir tăng thêm \(1\). Tại mỗi thời điểm nguyên, FJ có thể chọn đánh một lá trên tay nếu chi phí của nó không vượt quá lượng moolixir hiện có; khi đó, lượng moolixir của FJ giảm đi đúng bằng chi phí của lá bài.

FJ đánh dấu một tập con các lá bài \(s_1,s_2,\ldots,s_k\) làm điều kiện thắng (\(1\le k\le N\), \(1\le s_i\le N\)). Nếu trên tay FJ có ít nhất một lá điều kiện thắng, lá tiếp theo anh đánh bắt buộc phải là một lá điều kiện thắng.

FJ hỏi bạn \(Q\) (\(1\le Q\le 2\cdot 10^5\)) truy vấn. Mỗi truy vấn có dạng: trong vòng \(t\) đơn vị thời gian (\(1\le t\le 10^{18}\)), số lá điều kiện thắng lớn nhất mà FJ có thể đánh xuống là bao nhiêu?

Dữ liệu vào

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

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\).

Dòng thứ ba chứa số nguyên \(k\), là số lá điều kiện thắng.

Dòng thứ tư chứa \(k\) số nguyên phân biệt \(s_1,s_2,\ldots,s_k\).

Dòng thứ năm chứa số nguyên \(Q\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa một số nguyên \(t\), là thời điểm cần trả lời cho truy vấn tương ứng.

Dữ liệu ra

Với mỗi truy vấn, hãy in ra số lá điều kiện thắng lớn nhất mà FJ có thể đánh xuống trong vòng \(t\) đơn vị thời gian.

Ví dụ

6 3
2 4 3 5 7 6
2
1 4
6
1
2
3
7
10
1000000000000000

0
1
1
2
2
142857142857143

Phân nhóm

• Test 2–3: \(N,Q\le 100\).
• Test 4–5: \(H=1\).
• Test 6–11: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Silver Division — bài gốc tiếng Anh “Clash!”. Tác giả: Chongtian Ma. https://usaco.org/index.php?page=viewproblem2&cpid=1590

Có \(N\) (\(1\le N\le 2\cdot 10^5\)) chiếc xô xếp thành một chồng, trong đó chiếc xô thứ \(i\) tính từ trên xuống có sức chứa \(a_i\) gallon (\(1\le a_i\le 10^9\)). Một vòi ở phía trên chiếc xô đầu tiên rót mỗi giây một gallon sữa vào chiếc xô này. Bên dưới xô \(N\) còn có một bể chứa.

Khi một chiếc xô đạt sức chứa của nó sau \(t\) giây, vào đầu giây thứ \(t+1\), nó lật úp để đổ lượng sữa bên trong vào chiếc xô phía dưới nếu nó không phải xô cuối cùng, hoặc vào bể chứa nếu không còn xô nào bên dưới (chiếc xô trở lại trạng thái hứng sữa vào cuối giây thứ \(t+1\)). Một chiếc xô không thể hứng sữa khi đang lật úp; mọi lượng sữa chảy tới chiếc xô đó từ phía trên trong giây này đều bị mất. Ngoài ra, mọi lượng sữa vượt quá sức chứa của chiếc xô phía dưới cũng bị mất.

Hãy xử lý \(Q\) (\(1\le Q\le 3\cdot 10^5\)) truy vấn, mỗi truy vấn được mô tả bởi ba số nguyên \(i\), \(v\) và \(t\):

1. Trước tiên, gán \(a_i=v\) (\(1\le i\le N\), \(1\le v\le 10^9\)).
2. Sau đó trả lời câu hỏi sau: Giả sử tại thời điểm \(0\), tất cả các xô và bể chứa đều rỗng. Hãy xác định số gallon sữa trong bể sau \(t\) giây (\(1\le t\le 10^{18}\)).

Các cập nhật \(a_i=v\) vẫn có hiệu lực trong những truy vấn tiếp theo.

Dữ liệu vào

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

Dòng thứ hai chứa \(a_1,\dots,a_N\).

Dòng tiếp theo chứa \(Q\).

Mỗi dòng trong \(Q\) dòng sau chứa ba số nguyên \(i\), \(v\) và \(t\). Điều này có nghĩa là bạn cần gán \(a_i=v\), rồi trả lời câu hỏi ứng với \(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ụ

3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 10

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

2
1 2
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10

0
0
0
0
2
2
2
2
4
4

3
1 1 1
1
1 1 1000000000000000000

499999999999999999

Phân nhóm

• Test 4–5: \(N\le 10\), \(Q\le 100\) và mọi \(t\le 10^4\).
• Test 6–11: \(N\le 10^3\), \(Q\le 10^4\).
• Test 12–23: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Silver Division — bài gốc tiếng Anh “Milk Buckets”. Tác giả: Akshaj Arora. https://usaco.org/index.php?page=viewproblem2&cpid=1591

Bạn có \(N\) (\(2\le N\le 10^5\), \(N\) chẵn) điểm \((x_i,y_i)\) (\(1\le x_i,y_i\le 10^6\)) trên một mặt phẳng tọa độ hai chiều vô hạn.

Bạn có thể thực hiện hai loại thao tác sau đây bao nhiêu lần tùy ý:

• Chọn hai điểm kề trực tiếp với nhau (khoảng cách Manhattan bằng \(1\)) và xóa cả hai điểm.
• Chọn hai điểm bất kỳ và hoán đổi tọa độ \(y\) của chúng. Cụ thể, hai điểm \((a,b)\) và \((c,d)\) lần lượt trở thành \((a,d)\) và \((c,b)\).

Hãy xác định liệu có thể xóa hết tất cả các điểm trên mặt phẳng hay không. Lưu ý rằng hai điểm có thể nằm tại cùng một tọa độ; chúng vẫn phải được coi là hai điểm khác nhau. Bạn cũng không được trực tiếp xóa hai điểm nằm tại cùng một tọa độ, vì xét theo đúng định nghĩa, chúng không kề trực tiếp với nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 5000\)), là số lượng bộ test.

Dòng đầu tiên của mỗi bộ test chứa số nguyên \(N\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\).

Đả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 YES hoặc NO trên một dòng mới.

Ví dụ

4
2
1 1
1 1
4
6 10
7 11
8 1
8 1
6
1 2
1 3
1 4
1 5
10 10
11 10
6
1 1
1 1
1 1
1 1
10 10
11 11

NO
YES
YES
NO

Phân nhóm

• Test 2: \(T\le 1000\), \(N\le 6\).
• Test 3–5: \(N\le 100\).
• Test 6–11: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Silver Division — bài gốc tiếng Anh “Point Elimination”. Tác giả: Alex Pylypenko và Chongtian Ma. https://usaco.org/index.php?page=viewproblem2&cpid=1592