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

Farmer John và Farmer Nhoj đưa những chú bò của mỗi người đến ngồi quanh một đống lửa trại với hy vọng giải quyết những bất đồng cá nhân. Tổng cộng có \(N\) (\(2 \leq N \leq 10^5\)) chú bò ngồi thành một vòng tròn. Khi hai người nông dân chuẩn bị đưa bò về trang trại của mình, họ nhận ra một sai lầm nghiêm trọng: vì tất cả các chú bò trông giống hệt nhau và đang ngồi lẫn lộn, họ không thể xác định chú bò nào thuộc về người nào!

Sau đó, \(N\) chú bò được xếp thành một hàng thẳng để hai người nông dân thẩm vấn. Do sự hỗn loạn, thứ tự các chú bò trong hàng, từ \(1\) đến \(N\), có thể không tương ứng với thứ tự của chúng trên vòng tròn quanh đống lửa trại.

Tuy nhiên, những chú bò muốn chơi một trò chơi. Thay vì trả lời trực tiếp mình thuộc về người nông dân nào, mỗi chú bò cho biết những chú bò kề với mình trên vòng tròn ban đầu thuộc về người nông dân nào. Ngoài ra, ta biết rằng bò của Farmer Nhoj luôn nói dối, còn Farmer John đã nuôi dạy bò của mình rất tốt nên chúng luôn nói thật.

Cho các lời khai của những chú bò, liệu có thể gán mỗi chú bò cho Farmer John hoặc Farmer Nhoj sao cho mọi lời khai của những chú bò được gán cho Farmer John đều đúng, còn mọi lời khai của những chú bò được gán cho Farmer Nhoj đều sai hay không?

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 1000\)), số lượng bộ test độc lập, và một số nguyên \(C\in\{0,1\}\) (cho biết có cần in ra một cách xây dựng hay không).

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

Dòng tiếp theo chứa một xâu độ dài \(N\) chỉ gồm các ký tự J hoặc N. Ký tự thứ \(i\) là J nếu bò \(i\) khẳng định rằng chú bò ở bên trái mình trên vòng tròn thuộc về Farmer John; nếu không, ký tự đó là N, tức chú bò ấy khẳng định rằng chú bò bên trái thuộc về Farmer Nhoj.

Dòng tiếp theo chứa một xâu độ dài \(N\) chỉ gồm các ký tự J hoặc N. Ký tự thứ \(i\) là J nếu bò \(i\) khẳng định rằng chú bò ở bên phải mình trên vòng tròn thuộc về Farmer John; nếu không, ký tự đó là N, tức chú bò ấy khẳng định rằng chú bò bên phải thuộc về Farmer Nhoj.

Đả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 ra YES hoặc NO.

Ngoài ra, nếu \(C=1\) và đáp án là YES, hãy in thêm hai dòng mô tả cách xây dựng của bạn:

Dòng đầu tiên chứa một hoán vị \(p_1,p_2,\dots,p_N\) của \(1\dots N\), biểu diễn thứ tự vòng tròn của những chú bò quanh đống lửa trại, trong đó bò \(p_i\) nằm bên trái bò \(p_{i+1}\) với mọi \(i\) từ \(1\) đến \(N-1\), và bò \(p_N\) nằm bên trái bò \(p_1\).

Dòng thứ hai chứa một xâu \(b_1b_2\dots b_N\) chỉ gồm các ký tự J và N, có nghĩa là bò \(p_i\) thuộc về Farmer John nếu \(b_i\) là J, hoặc thuộc về Farmer Nhoj nếu không.

Bất kỳ cách xây dựng hợp lệ nào cũng được chấp nhận.

Ví dụ

6 0
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

YES
NO
NO
YES
NO
YES

6 1
3
JJJ
JJJ
4
JJNJ
NJJJ
6
NJNJNJ
JNNJNJ
4
NNNN
NNNN
3
NNN
NNN
5
JJNNJ
NJNJJ

YES
1 2 3
JJJ
NO
NO
YES
1 2 3 4
NJNJ
NO
YES
4 5 2 1 3
JJJJN

Phân nhóm

• Input 3: \(C=0\) và \(N\le 10\).
• Input 4: \(C=1\) và \(N\le 10\).
• Inputs 5–8: \(C=0\).
• Inputs 9–12: \(C=1\).

Nguồn

USACO 2026 Contest 2, Silver — Cow-libi 2. Tác giả: Chongtian Ma.

https://usaco.org/index.php?page=viewproblem2&cpid=1566

Có \(N\) thí sinh tham gia một cuộc thi, mỗi người có một thứ hạng khác nhau từ \(1\) đến \(N\). Có \(C\) tiêu chí được dùng để mời thí sinh tham dự vòng chung kết, và thí sinh xếp hạng \(i\) thỏa mãn một số lượng \(n_i\) tiêu chí đã cho (\(1\le n_i\le C\)).

Quá trình mời diễn ra như sau. Đầu tiên, \(f_1\) thí sinh có thứ hạng cao nhất trong số những người thỏa mãn tiêu chí thứ \(1\) sẽ được mời. Sau đó, trong số tất cả thí sinh chưa được mời, \(f_2\) người có thứ hạng cao nhất thỏa mãn tiêu chí thứ \(2\) sẽ được mời (hoặc mời tất cả những người còn lại nếu có ít hơn \(f_2\) người). Quá trình này được lặp lại với từng \(i\) từ \(1\) đến \(C\) (\(1\le f_i\le N\)).

Tuy nhiên, một số thí sinh sẽ từ chối tham dự vòng chung kết; khi đó, họ sẽ bị bỏ qua trong lúc xác định những người được mời.

Bạn được cho một hoán vị \(p_1,p_2,\dots,p_N\) của \(1\dots N\). Với mỗi \(i\) từ \(0\) đến \(N-1\), hãy xác định tổng thứ hạng của các thí sinh sẽ được mời nếu những thí sinh có thứ hạng là \(i\) phần tử đầu tiên của \(p\) từ chối tham dự.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(C\) (\(1\le N,C\le 10^5\)).

Dòng tiếp theo chứa \(f_1,f_2,\dots,f_C\).

Dòng tiếp theo chứa \(p_1,\dots,p_N\).

\(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(n_i\) (\(1\le n_i\le C\)), sau đó là \(n_i\) số nguyên phân biệt thuộc \([1,C]\), biểu diễn các tiêu chí mà thí sinh xếp hạng \(i\) thỏa mãn. Đảm bảo \(\sum n_i\le 10^6\).

Dữ liệu ra

In ra \(N\) dòng, mỗi dòng là tổng thứ hạng của những người được mời trước mỗi lần từ chối.

Ví dụ

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

6
6
9
6
4

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

10
14
12
9
5

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

21
20
16
10
5
3

Phân nhóm

• Inputs 4–6: \(N,C\le 10^3\), \(\sum n_i\le 10^4\).
• Inputs 7–8: \(C=1\).
• Inputs 9–10: \(C=2\).
• Inputs 11–16: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Silver — Declining Invitations. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1567

Farmer John có một mảng \(A\) gồm \(N\) số nguyên (\(1\le N\le 5\cdot 10^5\), \(1\le A_i\le N\)). Ông chọn chỉ số yêu thích \(j\) của mình và lấy ra một tờ giấy chỉ ghi \(A_j\). Sau đó, ông có thể thực hiện thao tác sau một số lần tùy ý:

• Dịch vòng tất cả các phần tử trong \(A\) sang trái một vị trí hoặc sang phải một vị trí. Sau đó, ghi \(A_j\) lên tờ giấy.

Gọi \(S\) là tập hợp các số nguyên phân biệt xuất hiện trong \(A\). Farmer John muốn biết số thao tác ít nhất phải thực hiện để tờ giấy chứa tất cả các số nguyên xuất hiện trong \(S\).

Vì không rõ chỉ số yêu thích của FJ là gì, hãy in đáp án cho mọi chỉ số yêu thích có thể có \(1\le j\le N\). Lưu ý rằng đối với mỗi chỉ số, \(A\) được khôi phục về trạng thái ban đầu trước khi thực hiện bất kỳ thao tác nào.

Dữ liệu vào

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

Dòng tiếp theo chứa \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

In ra \(N\) số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ \(i\) là đáp án khi chỉ số yêu thích của Farmer John là \(j=i\).

Ví dụ

6
1 2 3 1 3 4

4 3 3 4 3 3

12
1 1 2 1 1 3 1 1 4 1 1 1

8 7 6 7 8 9 8 7 6 7 8 9

Phân nhóm

• Inputs 3–5: \(N\le 500\).
• Inputs 6–8: \(N\le 10^4\).
• Inputs 9–17: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 2, Silver — Farmer John Loves Rotations. Tác giả: Chongtian Ma.

https://usaco.org/index.php?page=viewproblem2&cpid=1568