USACO 2025 - US Open - Hạng Bạc

Gần đây, những chú bò ở trang trại của Farmer John mê mẩn bộ phim Apothecowry Dairies. Bộ phim xoay quanh CowCow, một thám tử bò thông minh chuyên giải quyết đủ loại vấn đề. Bessie tìm thấy một bài toán mới trong phim, nhưng phải đến tập tiếp theo sau một tuần lời giải mới được tiết lộ! Hãy giải bài toán giúp cô.

Bạn được cho hai số nguyên \(M\) và \(K\) (\(1 \leq M \leq 10^9\), \(1 \leq K \leq 31\)). Hãy chọn một số nguyên dương \(N\) và xây dựng một dãy \(a\) gồm \(N\) số nguyên không âm sao cho các điều kiện sau được thỏa mãn:

• \(1 \le N \le 100\).
• \(a_1+a_2+\dots+a_N=M\).
• \(\operatorname{popcount}(a_1)\oplus\operatorname{popcount}(a_2)\oplus\dots\oplus\operatorname{popcount}(a_N)=K\).

Nếu không tồn tại dãy như vậy, in ra \(-1\).

\(\dagger\ \operatorname{popcount}(x)\) là số bit bằng \(1\) trong biểu diễn nhị phân của số nguyên \(x\). Chẳng hạn, popcount của \(11\) là \(3\) và popcount của \(16\) là \(1\).

\(\dagger\ \oplus\) là phép XOR theo bit.

Dữ liệu vào gồm \(T\) (\(1 \le T \le 5\cdot 10^3\)) bộ dữ liệu độc lập.

Dữ liệu vào

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

Dòng đầu tiên và duy nhất của mỗi bộ dữ liệu chứa \(M\) và \(K\).

Đảm bảo mọi bộ dữ liệu đều khác nhau.

Dữ liệu ra

In lời giải cho \(T\) bộ dữ liệu như sau:

Nếu không tồn tại đáp án, dòng duy nhất cho bộ dữ liệu đó phải là \(-1\).

Ngược lại, dòng đầu tiên cho bộ dữ liệu đó chứa một số nguyên \(N\), là độ dài của dãy (\(1 \le N \le 100\)).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách thỏa mãn các điều kiện (\(0 \le a_i \le M\)).

Ví dụ

3
2 1
33 5
10 5

2
2 0
3
3 23 7
-1

Phân nhóm

• Dữ liệu 2: \(M\le 8, K\le 8\).
• Dữ liệu 3–5: \(M>2^K\).
• Dữ liệu 6–18: Không có ràng buộc bổ sung.

Đề bài: Aakash Gokhale.

Nguồn

USACO 2025 US Open Contest, Silver — Sequence Construction: https://usaco.org/index.php?page=viewproblem2&cpid=1518

Ở sâu trong vùng nông thôn, những chú bò của Farmer John không chỉ là những vật nuôi bình thường — chúng là thành viên của một mạng lưới tình báo bò bí mật. Mỗi con bò mang một mã số ID được các chuyên gia mật mã bò tinh nhuệ gán cẩn thận. Tuy nhiên, do hệ thống gắn thẻ khá tùy tiện của Farmer John, một số con bò có cùng ID.

Farmer John ghi nhận có \(N\) (\(1\le N\le 2\cdot 10^5\)) giá trị ID phân biệt; với mỗi ID phân biệt \(d_i\) (\(0\le d_i\le 10^9\)), có \(n_i\) (\(1\le n_i\le 10^9\)) con bò cùng mang ID đó.

Các con bò chỉ có thể liên lạc theo cặp, và phương thức mã hóa bí mật của chúng có một quy tắc nghiêm ngặt: hai con bò chỉ có thể trao đổi thông tin nếu chúng không phải cùng một con và tổng ID của chúng bằng \(A\) hoặc \(B\) (\(0\le A\le B\le 2\cdot 10^9\)). Mỗi con bò chỉ có thể tham gia một cuộc trò chuyện tại một thời điểm (tức là không con bò nào thuộc nhiều hơn một cặp).

Farmer John muốn tối đa hóa số cặp liên lạc rời nhau để luồng thông tin đạt hiệu quả cao nhất. Hãy xác định số cuộc trò chuyện lớn nhất có thể diễn ra đồng thời.

Dữ liệu vào

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

\(N\) dòng tiếp theo, mỗi dòng chứa \(n_i\) và \(d_i\). Không có hai giá trị \(d_i\) nào bằng nhau.

Dữ liệu ra

In ra số cặp bò liên lạc rời nhau lớn nhất có thể được tạo thành cùng lúc.

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu số nguyên 64-bit (chẳng hạn long long trong C/C++).

Ví dụ

4 4 5
17 2
100 0
10 1
200 4

118

4 4 5
100 0
10 1
100 3
20 4

30

Phân nhóm

• Dữ liệu 3–4: \(A=B\).
• Dữ liệu 5–7: \(N\le 1000\).
• Dữ liệu 8–12: Không có ràng buộc bổ sung.

Đề bài: Benjamin Qi.

Nguồn

USACO 2025 US Open Contest, Silver — Compatible Pairs: https://usaco.org/index.php?page=viewproblem2&cpid=1519

Bessie đang đi trượt tuyết cùng bạn bè. Ngọn núi có \(N\) điểm mốc (\(1\leq N\leq 10^5\)), được đánh số \(1,2,\ldots,N\) theo thứ tự độ cao tăng dần (điểm mốc \(1\) nằm dưới chân núi).

Với mỗi điểm mốc \(i>1\), có một đường trượt bắt đầu tại điểm mốc \(i\) và kết thúc tại điểm mốc \(p_i\) (\(1\le p_i<i\)). Đường trượt này có độ khó \(d_i\) (\(0\leq d_i\leq 10^9\)) và độ thú vị \(e_i\) (\(0\leq e_i\leq 10^9\)).

Mỗi người trong số \(M\) người bạn của Bessie (\(1\leq M\leq 10^5\)) sẽ làm như sau: họ chọn một điểm mốc ban đầu \(i\), rồi đi theo các đường trượt xuống dưới (đến \(p_i\), rồi đến \(p_{p_i}\), v.v.) cho tới khi đến điểm mốc \(1\).

Độ thú vị mà mỗi người nhận được bằng tổng độ thú vị của các đường trượt họ đi qua. Mỗi người cũng có một trình độ kỹ năng \(s_j\) (\(0\leq s_j\leq 10^9\)) và mức độ can đảm \(c_j\) (\(0\leq c_j\leq 10\)) khác nhau; vì thế họ chỉ được chọn điểm mốc ban đầu sao cho hành trình có nhiều nhất \(c_j\) đường trượt có độ khó lớn hơn \(s_j\).

Với mỗi người bạn, hãy tính độ thú vị lớn nhất họ có thể nhận được.

Dữ liệu vào

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

Tiếp theo, với mỗi \(i\) từ \(2\) đến \(N\), có một dòng chứa ba số nguyên cách nhau bởi dấu cách \(p_i\), \(d_i\), \(e_i\).

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

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(s_j\) và \(c_j\).

Dữ liệu ra

In ra \(M\) dòng, mỗi dòng là đáp án của một người bạn.

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu số nguyên 64-bit (chẳng hạn long long trong C/C++).

Ví dụ

4
1 20 200
2 30 300
2 10 100
8
19 0
19 1
19 2
20 0
20 1
20 2
29 0
30 0

0
300
500
300
500
500
300
500

Phân nhóm

• Dữ liệu 2–4: \(N,M\le 1000\).
• Dữ liệu 5–7: Mọi \(c_j=0\).
• Dữ liệu 8–17: Không có ràng buộc bổ sung.

Đề bài: Brandon Wang.

Nguồn

USACO 2025 US Open Contest, Silver — Ski Slope: https://usaco.org/index.php?page=viewproblem2&cpid=1520