USACO 2026 - US Open

Bạn được cho một xâu bit \(s_{1\dots N}\) có độ dài \(N\) (\(2\le N\le 10^9\)). Trong một thao tác, bạn có thể đảo ngược đoạn \(s_{l\dots r}\) nếu các điều kiện sau được thỏa mãn:

1. Độ dài của đoạn là số chẵn.
2. Nửa đầu của đoạn chỉ gồm một ký tự (hoặc \(0\) hoặc \(1\)), và nửa sau chứa ký tự còn lại.
3. Hoặc \(l=1\), hoặc \(s_{l-1}\neq s_l\).
4. Hoặc \(r=N\), hoặc \(s_{r+1}\neq s_r\).

Hãy tìm số thao tác ít nhất để đưa tất cả các ký tự \(1\) lên đầu xâu, hoặc cho biết điều đó là không thể. Nếu có thể, hãy đồng thời in ra số dãy thao tác đạt được số thao tác ít nhất này, lấy modulo \(10^9+7\).

Dữ liệu vào

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

Xâu bit được cho dưới dạng nén. Dòng đầu tiên chứa \(R\), là số đoạn liên tiếp gồm các ký tự giống nhau trong xâu (\(2\le R\le 800\)), và ký tự đầu tiên của xâu (hoặc \(0\) hoặc \(1\)).

Dòng tiếp theo chứa \(R\) số nguyên cách nhau bởi dấu cách \(l_1,l_2,l_3,\ldots,l_R\) (\(0<l_i<10^9\)), là độ dài của các khối liên tiếp cực đại gồm các ký tự giống nhau trong \(s\). Đảm bảo rằng \(N=\sum_{i=1}^R l_i\le 10^9\).

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

Dữ liệu ra

Với mỗi bộ test, in ra số thao tác ít nhất để đưa tất cả các ký tự \(1\) lên đầu xâu, hoặc \(-1\) nếu điều đó là không thể, cùng với số dãy thao tác đạt được số thao tác ít nhất này lấy modulo \(10^9+7\).

Ví dụ

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

1 1
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1

5
2 1
1 1
4 1
1 1 1 1
6 1
1 1 1 1 1 1
8 1
1 1 1 1 1 1 1 1
10 1
1 1 1 1 1 1 1 1 1 1

0 1
1 1
2 1
3 3
4 9

(1)
   10101010
-> 11001010
-> 11001100
-> 11110000

(2)
   10101010
-> 10110010
-> 10001110
-> 11110000

(3)
   10101010
-> 10101100
-> 11001100
-> 11110000

Phân nhóm

• Input 3: \(N\leq 10\), tất cả các bộ test đôi một khác nhau.
• Input 4: \(R\le 10\).
• Inputs 5-8: \(R\le 100\), tổng \(R^2\) trên tất cả các bộ test không vượt quá \(10^5\), và đảm bảo số thao tác ít nhất bằng \(R/2-1\).
• Inputs 9-12: \(R\le 100\), tổng \(R^2\) trên tất cả các bộ test không vượt quá \(10^5\).
• Inputs 13-16: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 US Open, Open Division — Arranging Cows. Tác giả: Sujay Konda.
https://usaco.org/index.php?page=viewproblem2&cpid=1602

Lưu ý: Giới hạn thời gian của bài này là 2.5 giây.

Farmer John có \(N\) chồng kiện cỏ khô (\(1\leq N\leq 5\cdot 10^5\)), trong đó chồng thứ \(i\) chứa \(a_i\) kiện cỏ khô (\(1\leq a_i\leq 10^9\)). Ông muốn dọn hết các kiện cỏ này và có \(M\) con bò (\(1\leq M\leq 2500\)) sẵn sàng giúp đỡ. Nếu được thuê với chi phí \(c_i\) (\(1\leq c_i\leq 10^9\)), con bò thứ \(i\) sẽ lặp lại việc sau \(s_i\) lần (\(1\leq s_i\leq 100\)):

• Nếu chồng có ít nhất \(p_i\) kiện cỏ khô (\(1\leq p_i\leq 10^9\)), con bò sẽ lấy đi một kiện cỏ.
• Nếu chồng có ít hơn \(p_i\) kiện cỏ khô, con bò không làm gì cả.

Với mỗi chồng, FJ muốn lấy đi toàn bộ các kiện cỏ trong đó. Ông sẽ làm việc này bằng cách lần lượt thuê các con bò (có thể thuê cùng một con bò nhiều lần) cho đến khi chồng trở nên rỗng. Hãy giúp FJ xác định chi phí nhỏ nhất để dọn hết từng chồng.

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ó định dạng như sau:

Dòng đầu tiên chứa một số nguyên \(N\). Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\).

Dòng thứ ba chứa một số nguyên \(M\). Mỗi dòng trong \(M\) dòng tiếp theo chứa \(p_i,s_i,c_i\).

Đảm bảo rằng các con bò có thể lấy đi toàn bộ kiện cỏ trong mọi chồng. Ngoài ra, đảm bảo rằng tổng \(N\) trên tất cả các bộ test không vượt quá \(5\cdot 10^5\), và tổng \(M\) trên tất cả các bộ test không vượt quá \(2500\).

Dữ liệu ra

Với mỗi bộ test, in ra \(N\) số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ \(i\) là chi phí để lấy đi toàn bộ kiện cỏ trong chồng thứ \(i\).

Ví dụ

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

29 155 21
73 328 50

Phân nhóm

• Inputs 2-3: \(a_i\le 100\).
• Inputs 4-5: \(\max(s)=1\).
• Inputs 6-9: \(\max(s)\le 4\).
• Inputs 10-15: \(\max(s)\le 20\).
• Inputs 16-21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 US Open, Open Division — Haybale Stacks. Tác giả: Sujay Konda.
https://usaco.org/index.php?page=viewproblem2&cpid=1603

Lưu ý: Giới hạn bộ nhớ của bài này là 512MB, gấp đôi mức mặc định.

Một cây nhị phân hoàn hảo là một cây có gốc mà mỗi đỉnh không phải lá có đúng hai đỉnh con và tất cả các đỉnh lá cách gốc một khoảng bằng nhau.

Một cây nhị phân hoàn hảo không gốc là một cây không gốc mà khi chọn một trong các đỉnh của nó làm gốc, cây đó trở thành một cây nhị phân hoàn hảo.

Bessie có một cây gồm \(N\) đỉnh (\(1\le N\le 10^5\)). Hãy xác định số cách xóa một tập con các cạnh khỏi cây sao cho rừng thu được là một tập hợp các cây nhị phân hoàn hảo không gốc. Vì đáp án có thể rất lớn, hãy in kết quả lấy modulo \(10^9+7\).

Dữ liệu vào

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

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

Mỗi dòng trong \(N-1\) dòng tiếp theo của mỗi bộ test chứa hai số nguyên \(u_i\) và \(v_i\) (\(1\leq u_i,v_i\leq N\)), biểu thị một cạnh nối hai đỉnh \(u_i\) và \(v_i\).

Đảm bảo rằng trong mỗi bộ test, các cạnh đã cho tạo thành một cây gồm \(N\) đỉnh.

Ngoài ra, tổng \(N\) 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 ra một số nguyên duy nhất: số tập con các cạnh mà khi bị xóa sẽ tạo ra một rừng là tập hợp các cây nhị phân hoàn hảo không gốc, lấy modulo \(10^9+7\).

Ví dụ

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

8
2
14

Phân nhóm

• Inputs 2-3: \(N\le 15\).
• Inputs 4-5: Không đỉnh nào kề với nhiều hơn hai đỉnh khác.
• Inputs 6-9: \(N\le 1000\), tổng \(N\) không vượt quá \(2000\), và không đỉnh nào kề với nhiều hơn ba đỉnh khác.
• Inputs 10-13: Không đỉnh nào kề với nhiều hơn ba đỉnh khác.
• Inputs 14-21: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 US Open, Open Division — Perfect Binary Trees. Tác giả: Avnith Vijayram.
https://usaco.org/index.php?page=viewproblem2&cpid=1604