USACO 2026 Second Contest, Bronze

Bessie có một chiếc máy tính với bàn phím chỉ có hai chữ cái là M và O.

Bessie muốn gõ tiếng bò yêu thích của mình là \(S\), gồm \(N\) chữ cái, mỗi chữ cái là M hoặc O. Tuy nhiên, máy tính của cô đã bị nhiễm vi-rút. Mỗi khi cô cố gõ chữ O, mọi chữ cái cô đã gõ từ trước đến lúc đó đều bị đảo, từ M thành O hoặc từ O thành M, rồi chữ O mới xuất hiện.

Liệu Bessie có thể gõ được tiếng bò yêu thích của mình hay không?

Ngoài ra, Bessie được cho một tham số \(k\) có giá trị bằng \(0\) hoặc \(1\).

• Nếu \(k=0\), Bessie chỉ cần xác định liệu có thể gõ được tiếng bò yêu thích của mình hay không.
• Nếu \(k=1\), Bessie còn phải đưa ra một ví dụ về dãy phím cần nhấn để gõ được tiếng bò yêu thích của mình.

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số lượng bộ test độc lập (\(1\le T\le 10^4\)), và \(k\) (\(0\le k\le 1\)).

Dòng đầu tiên của mỗi bộ test chứa \(N\) (\(1\le N\le 2\cdot 10^5\)).

Dòng thứ hai của mỗi bộ test chứa \(S\). Đảm bảo rằng \(S\) không chứa ký tự nào ngoài M và O.

Tổng \(N\) trên tất cả các bộ test không vượt quá \(4\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, hãy in một hoặc hai dòng theo quy trình sau.

Nếu Bessie không thể gõ được \(S\), hãy in NO trên một dòng.

Ngược lại, ở dòng đầu tiên hãy in YES. Ngoài ra, nếu \(k=1\), ở dòng thứ hai hãy in một xâu độ dài \(N\), gồm các ký tự theo đúng thứ tự Bessie cần gõ để tạo ra tiếng bò yêu thích của mình. Nếu có nhiều xâu thỏa mãn, có thể in bất kỳ xâu nào.

Ví dụ

2 0
3
MOO
5
OOMOO

YES
YES

2 1
3
MOO
5
OOMOO

YES
OMO
YES
MOOMO

Phân nhóm

• Test 3–4: \(k=0\).
• Test 5–6: \(k=1\), \(T\le 10^3\), \(N\le 10\).
• Test 7–9: \(k=1\), \(T\le 10\), \(N\le 1000\).
• Test 10–16: \(k=1\).

Nguồn

USACO 2026 Contest 2, Bronze Division — bài gốc It's Mooin' Time IV, tác giả: Nick Wu.
https://usaco.org/index.php?page=viewproblem2&cpid=1563

Bessie đang chơi trò chơi nổi tiếng "Moo Hunt". Trong trò chơi này, có \(N\) (\(3\le N\le 20\)) ô nằm trên một hàng, được đánh số từ \(1\) đến \(N\). Mỗi ô chứa ký tự M hoặc O, trong đó ô thứ \(i\) chứa ký tự \(s_i\).

Bessie dự định thực hiện \(K\) (\(1\le K\le 2\cdot 10^5\)) lượt chơi. Trong lượt thứ \(i\), Bessie sẽ chạm vào \(3\) ô khác nhau \((x_i,y_i,z_i)\) (\(1\le x_i,y_i,z_i\le N\)). Bessie nhận được một điểm nếu \(s_{x_i}=M\) và \(s_{y_i}=s_{z_i}=O\). Nói cách khác, Bessie nhận được một điểm nếu tạo thành xâu MOO bằng cách lần lượt chạm vào các ô \(x_i,y_i,z_i\) theo thứ tự đó.

Farmer John muốn giúp Bessie lập kỷ lục mới. Ông muốn bạn tìm điểm số lớn nhất Bessie có thể đạt được trong số tất cả các bảng có thể có khi cô thực hiện \(K\) lượt chơi, đồng thời tìm số lượng bảng khác nhau cho phép Bessie đạt được điểm số lớn nhất này. Hai bảng được coi là khác nhau nếu tồn tại một ô mà ký tự tương ứng tại ô đó khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\), lần lượt là số ô và số lượt chơi Bessie sẽ thực hiện.

Mỗi dòng trong \(K\) dòng tiếp theo chứa \(x_i,y_i,z_i\), mô tả lượt chơi thứ \(i\) của Bessie (\(x_i,y_i,z_i\) đôi một khác nhau).

Dữ liệu ra

In ra điểm số lớn nhất Bessie có thể đạt được, tiếp theo là số lượng bảng khác nhau cho phép Bessie đạt được điểm số lớn nhất này.

Ví dụ

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

4 2

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

6 3

Phân nhóm

• Test 3–5: \(N\le 8\), \(K\le 10^4\).
• Test 6–12: Có một test ứng với mỗi \(N\in\{14,15,16,17,18,19,20\}\) và không có thêm ràng buộc nào đối với \(K\).

Nguồn

USACO 2026 Contest 2, Bronze Division — bài gốc Moo Hunt, tác giả: Alex Liang.
https://usaco.org/index.php?page=viewproblem2&cpid=1564

Nhân Ngày Sữa Quốc gia, Farmer John đang đưa ra mức giá đặc biệt cho các xô sữa! Ông có \(N\) (\(1\leq N\leq 10^5\)) ưu đãi được đánh số từ \(1\) đến \(N\). Với ưu đãi thứ \(i\), ông bán \(2^{i-1}\) xô sữa với giá \(a_i\) (\(1\leq a_i\leq 10^9\), \(a_i<a_{i+1}\)) mooney. Có thể sử dụng cùng một ưu đãi với số lần là bất kỳ số nguyên không âm nào.

Bạn đang cân nhắc \(Q\) (\(1\leq Q\leq 10^4\)) truy vấn độc lập. Với mỗi truy vấn, bạn nghĩ đến một số nguyên \(x\) (\(1\leq x\leq 10^9\)) và muốn biết chi phí nhỏ nhất để mua ít nhất \(x\) xô sữa.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).

Dòng tiếp theo chứa \(a_1,a_2,\ldots,a_N\).

Mỗi dòng trong \(Q\) dòng tiếp theo chứa một số nguyên \(x\), biểu diễn một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in chi phí nhỏ nhất trên một dòng mới.

Lưu ý rằng các số nguyên có giá trị lớn trong bài toán này có thể yêu cầu sử dụng kiểu số nguyên 64 bit (ví dụ: long long trong C/C++).

Ví dụ

2 4
10 15
1
2
6
7

10
15
45
55

4 10
10 25 30 70
1
2
3
4
5
6
7
8
15
101

10
20
30
30
40
50
60
60
120
760

Phân nhóm

• Test 3–4: \(N\leq 2\).
• Test 5–8: \(N\leq 10\).
• Test 9–16: Không có thêm ràng buộc.

Nguồn

USACO 2026 Contest 2, Bronze Division — bài gốc Purchasing Milk, tác giả: Chongtian Ma.
https://usaco.org/index.php?page=viewproblem2&cpid=1565