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

Có một hàng gồm các con bò, ban đầu (tức là tại thời điểm \(t=0\)) chỉ có bò \(0\) ở vị trí \(0\) (ở đây, một con bò ở vị trí \(k\) nếu có \(k\) con bò đứng trước nó). Tại thời điểm \(t\) với \(t=1,2,3,\dots\), con bò ở vị trí \(0\) di chuyển đến vị trí \(\lfloor t/2\rfloor\), mỗi con bò ở các vị trí \(1\dots \lfloor t/2\rfloor\) tiến lên trước một vị trí, và bò \(t\) gia nhập hàng ở 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 thuộc một trong các loại sau:

1. Ngay sau thời điểm \(t\), bò \(c\) ở vị trí nào (\(0\le c\le t\le 10^{18}\))?
2. Ngay sau thời điểm \(t\), con bò nào ở vị trí \(x\) (\(0\le x\le t\le 10^{18}\))?

Dữ liệu vào

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

\(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả một truy vấn, có dạng 1 c t hoặc 2 x 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ụ

2
1 4 9
2 2 9

2
4

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

22
1 0 9
1 1 9
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9
1 7 9
1 8 9
1 9 9
2 0 9
2 1 9
2 2 9
2 3 9
2 4 9
2 5 9
2 6 9
2 7 9
2 8 9
2 9 9
1 0 1000000000000000000
2 0 1000000000000000000

1
3
0
4
2
5
6
7
8
9
2
0
4
1
3
5
6
7
8
9
483992463350322770
148148148148148148

Phân nhóm

• Input 3: \(Q\le 1000, t\le 100\).
• Input 4: \(t\le 5000\).
• Inputs 5–8: Tất cả các truy vấn đều thuộc loại 1.
• Inputs 9–12: Tất cả các truy vấn đều thuộc loại 2.

Nguồn

USACO 2026 First Contest, Silver — bài gốc tiếng Anh “Lineup Queries”, tác giả Agastya Goel: https://usaco.org/index.php?page=viewproblem2&cpid=1542

Bessie đang thiết kế một lò phản ứng hạt nhân để cung cấp năng lượng cho CowWeave, hoạt động kinh doanh trung tâm dữ liệu AI mới đầy lợi nhuận của Nông dân John!

Lõi lò phản ứng gồm \(N\) (\(1\le N\le 2\cdot 10^5\)) thanh nhiên liệu, được đánh số từ \(1\) đến \(N\). Thanh thứ \(i\) có một “phạm vi vận hành ổn định” \([l_i,r_i]\) (\(-10^9\leq l_i\leq r_i\leq 10^9\)), nghĩa là nó chỉ có thể phát điện nếu năng lượng \(a_i\) (do Bessie chọn) thỏa mãn \(l_i\le a_i\le r_i\); nếu không, nó ở trạng thái không hoạt động và không phát điện. Ngoài ra, \(a_i\) luôn phải là một số nguyên. Lưu ý rằng \(a_i\) có thể là bất kỳ số nguyên nào, không bị giới hạn trong \([-10^9,10^9]\).

Tuy nhiên, các tương tác lượng tử giữa những thanh nhiên liệu tạo ra \(M\) ràng buộc có dạng \((x,y,z)\), trong đó Bessie phải thỏa mãn \(a_x+a_y=z\) (\(1\leq x,y\leq N\) và \(-10^9\le z\le 10^9\)) để ngăn lò phản ứng bị nóng chảy.

Hãy giúp Bessie tìm số thanh phát điện tối đa mà cô có thể đạt được trong thiết kế của mình mà không làm lò phản ứng bị nóng chảy!

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
• Dòng thứ hai chứa \(N\) số nguyên \(l_1,\dots,l_N\).
• Dòng thứ ba chứa \(N\) số nguyên \(r_1,\dots,r_N\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x\), \(y\) và \(z\), biểu diễn một ràng buộc.

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

Dữ liệu ra

Nếu không tồn tại cách chọn năng lượng cho các thanh sao cho thỏa mãn mọi ràng buộc, hãy in \(-1\). Nếu có, hãy in số thanh phát điện tối đa mà Bessie có thể đạt được.

Ví dụ

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

-1
2

1
3 2
10 -10 10
10 -10 10
1 2 0
2 3 0

3

5
3 3
1 -1 0
2 1 2
1 2 1
1 3 4
2 3 3
1 1
-100
100
1 1 3
1 1
-100
100
1 1 2
1 2
-100
100
1 1 2
1 1 4
1 2
-100
100
1 1 2
1 1 2

2
-1
1
-1
1

Phân nhóm

• Input 4: \(x=y\) với mọi ràng buộc.
• Inputs 5–7: \(|x-y|=1\) với mọi ràng buộc.
• Inputs 8–10: \(|x-y|\le 1\) với mọi ràng buộc.
• Inputs 11–13: Không có điều kiện bổ sung.

Nguồn

USACO 2026 First Contest, Silver — bài gốc tiếng Anh “Mooclear Reactor”, tác giả Akshaj Arora: https://usaco.org/index.php?page=viewproblem2&cpid=1543

Bessie có một xâu nhị phân ẩn \(b_1b_2\dots b_N\) (\(1\le N\le 2\cdot 10^5\)). Thông tin duy nhất được cung cấp về \(b\) là một xâu nhị phân \(r_1r_2\dots r_{N-K+1}\) (\(1\le K\le N\)), trong đó \(r_i\) là số dư khi chia cho hai số lượng bit \(1\) trong cửa sổ độ dài \(K\) của \(b\) có chỉ số ngoài cùng bên trái là \(i\).

Hãy in số lượng bit \(1\) nhỏ nhất và lớn nhất có thể có trong xâu nhị phân ẩn của Bessie.

Dữ liệu vào

Có \(T\) (\(1\le T\le 10^3\)) bộ test độc lập cần giải quyết. Mỗi bộ test được mô tả như sau:

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

Dòng thứ hai chứa xâu nhị phân \(r_1\dots r_{N-K+1}\), trong đó \(r_i=\sum_{j=i}^{j+K-1}b_j\pmod{2}\).

Đảm bảo tổng \(N\) 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 số lượng bit \(1\) nhỏ nhất và lớn nhất có thể có trong xâu nhị phân ẩn của Bessie, cách nhau bởi đúng một dấu cách.

Ví dụ

7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
0000

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

Phân nhóm

• Input 2: \(N\le 8\).
• Inputs 3–4: \(K\le 8\) và tổng \(N\) trên tất cả các bộ test không vượt quá \(10^4\).
• Inputs 5–11: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 First Contest, Silver — bài gốc tiếng Anh “Sliding Window Summation”, tác giả Benjamin Qi: https://usaco.org/index.php?page=viewproblem2&cpid=1544