KOI 2026 - Vòng 2 - THCS

Có \(N\) viên xúc xắc lập phương. Mỗi mặt mang một số từ \(1\) đến \(6\), các mặt khác nhau mang các số khác nhau, và tổng số trên hai mặt đối diện luôn bằng \(7\).

Sau khi gieo các xúc xắc, số ở mặt trên của viên \(i\) là \(A_i\). Chọn một hoặc nhiều viên còn trên bàn để tạo một tháp; có thể thay đổi thứ tự các viên nhưng không được xoay chúng. Hai mặt tiếp xúc trong tháp phải mang cùng một số. Lặp lại cho đến khi dùng hết các viên xúc xắc.

Hãy tìm số tháp ít nhất có thể tạo được.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\).

Dữ liệu ra

In ra số tháp nhỏ nhất.

Ràng buộc

• \(2 \le N \le 200000\).
• \(1 \le A_i \le 6\).

Phân nhóm

• Nhóm 1 (8 điểm): \(N = 2\).
• Nhóm 2 (28 điểm): \(A_i\) chỉ là \(3\) hoặc \(4\) với mọi \(i\).
• Nhóm 3 (31 điểm): với mọi \(x \ne y\), số viên có mặt trên là \(x\) khác số viên có mặt trên là \(y\).
• Nhóm 4 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

4
3 3 5 4

2

2
3 4

1

5
1 1 6 1 1

3

Nguồn

KOI 2026 Round 2, problem Dice Tower Stacking. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.

Có \(N\) học sinh và \(N\) loại đồ ăn nhẹ, đều được đánh số từ \(1\) đến \(N\). Học sinh \(i\) thích \(C_i\) loại có chỉ số \(A_{i,1},\ldots,A_{i,C_i}\). Ban đầu mỗi loại đồ ăn có đúng một chiếc.

Đưa các học sinh vào phòng theo một thứ tự. Khi vào, một học sinh lấy tất cả đồ ăn mà mình thích và còn lại trong phòng. Hãy quyết định liệu có thể chọn thứ tự sao cho mọi học sinh lấy đúng một đồ ăn hay không. Nếu có, hãy in một thứ tự như vậy.

Dữ liệu vào

• Dòng đầu chứa \(N\).
• \(N\) dòng tiếp theo: dòng \(i\) chứa \(C_i\) rồi đến \(C_i\) số \(A_{i,j}\).

Dữ liệu ra

In -1 nếu không thể. Ngược lại in một hoán vị \(P_1,\ldots,P_N\) sao cho khi học sinh vào theo thứ tự đó, mỗi người lấy đúng một đồ ăn.

Ràng buộc

• \(1 \le N \le 200000\), \(1 \le C_i \le N\).
• \(1 \le A_{i,j} \le N\).
• \(\sum C_i \le 500000\); các đồ ăn mà cùng một học sinh thích là khác nhau.

Phân nhóm

• Nhóm 1 (6 điểm): \(C_i = 1\) với mọi \(i\).
• Nhóm 2 (11 điểm): nếu tồn tại thứ tự hợp lệ thì thứ tự \(1,2,\ldots,N\) cũng hợp lệ.
• Nhóm 3 (8 điểm): \(N \le 5\).
• Nhóm 4 (12 điểm): \(N \le 18\).
• Nhóm 5 (18 điểm): \(N \le 300\).
• Nhóm 6 (20 điểm): \(N \le 5000\).
• Nhóm 7 (25 điểm): Không có ràng buộc bổ sung.

Ví dụ

3
2 1 2
2 2 3
1 2

3 1 2

Theo thứ tự này, học sinh \(3\) lấy đồ ăn \(2\), học sinh \(1\) lấy đồ ăn \(1\), rồi học sinh \(2\) lấy đồ ăn \(3\); vì vậy mỗi người lấy đúng một món.

2
2 1 2
2 1 2

-1

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

1 2 3 4

Nguồn

KOI 2026 Round 2, problem Snack Distribution. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.

Alice và Bob chơi trong một mê cung gồm \(N\) phòng đánh số từ \(1\) đến \(N\). Phòng \(i\) có lối ra khi \(A_i=1\) và không có lối ra khi \(A_i=0\).

Mê cung có đúng \(M\) cặp phòng được nối. Với mỗi \(i\), có \(c_i\) hành lang khác nhau cùng nối hai phòng \(a_i\) và \(b_i\); vì vậy giữa cùng một cặp phòng có thể có nhiều hành lang song song. Mê cung không nhất thiết liên thông.

Họ chơi \(Q\) ván độc lập. Trong ván \(j\), Alice đi vào phòng \(s_j\) và có thể lặp lại thao tác sau:

1. Nếu đang ở phòng \(x\), Alice chọn đúng \(k_j\) hành lang khác nhau kề với \(x\). Cô có thể chọn nhiều hành lang song song dẫn đến cùng một phòng. Nếu bậc của \(x\) nhỏ hơn \(k_j\), Alice không thể di chuyển.
2. Sau khi Alice chọn, Bob chọn một trong \(k_j\) hành lang đó.
3. Alice đi qua hành lang Bob chọn đến phòng ở đầu kia.

Alice thắng ngay khi đến một phòng có lối ra, kể cả khi phòng xuất phát \(s_j\) đã có lối ra; cô được phép thực hiện \(0\) lần di chuyển. Alice cố gắng bảo đảm chiến thắng còn Bob cố ngăn cô thắng. Nói cách khác, Alice thắng nếu có một chiến lược thích nghi với các lựa chọn trước đó để cuối cùng luôn đến được một phòng có lối ra, bất kể Bob chọn thế nào.

Với mỗi ván, hãy xác định Alice có thể bảo đảm chiến thắng hay không.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(N,M,Q\).
• Dòng thứ hai chứa \(A_1,A_2,\ldots,A_N\).
• \(M\) dòng tiếp theo: dòng \(i\) chứa \(a_i,b_i,c_i\), cho biết có \(c_i\) hành lang nối phòng \(a_i\) và \(b_i\).
• \(Q\) dòng tiếp theo: dòng \(j\) chứa \(s_j,k_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng \(j\) là YES nếu Alice có thể bảo đảm thắng ván \(j\), ngược lại là NO.

Ràng buộc

• \(1\le N\le200\,000\).
• \(0\le M\le400\,000\).
• \(1\le Q\le200\,000\).
• \(A_i\in\{0,1\}\) với mọi \(1\le i\le N\).
• \(1\le a_i<b_i\le N\) và \(1\le c_i\le10^9\) với mọi \(1\le i\le M\).
• Các cặp \((a_i,b_i)\) đôi một khác nhau.
• \(1\le s_j\le N\) và \(1\le k_j\le10^{18}\) với mọi \(1\le j\le Q\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(M=N-1\); với mọi \(1\le i\le M\), \(a_i=i\) và \(b_i=i+1\); chỉ phòng \(1\) có lối ra, tức \(A_1=1\) và \(A_2=A_3=\cdots=A_N=0\).
2. \(8\) điểm: \(M=N-1\); với mọi \(1\le i\le M\), \(a_i=1\) và \(b_i=i+1\).
3. \(7\) điểm: \(k_1=k_2=\cdots=k_Q=1\).
4. \(14\) điểm: \(k_1=k_2=\cdots=k_Q\).
5. \(15\) điểm: \(s_1=s_2=\cdots=s_Q\).
6. \(16\) điểm: \(N\le3\,000\), \(M\le3\,000\) và \(k_j\le3\,000\) với mọi \(1\le j\le Q\).
7. \(34\) điểm: không có ràng buộc thêm.

Ví dụ

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

YES
YES
YES
NO
NO

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

YES
YES
NO
YES

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

YES
YES
NO

2 0 2
1 0
1 1
2 1

YES
NO

Nguồn

KOI 2026 Round 2, bài Game. Tài liệu, dữ liệu chấm và mã nguồn mẫu của Korean Olympiad in Informatics, phát hành theo giấy phép CC BY-NC-SA 4.0.

Cho hoán vị \(A=[A_1,\ldots,A_N]\) và dãy \(B=[B_1,\ldots,B_M]\) có các phần tử khác nhau. Ban đầu \(X=A\). Có thể lặp lại hai thao tác: đổi chỗ hai phần tử kề nhau \(X_i<X_{i+1}\), hoặc gộp hai phần tử kề nhau thành \(\min(X_i,X_{i+1})\).

Hãy quyết định có thể biến \(X\) thành \(B\) không. Nếu có, in bất kỳ dãy thao tác hợp lệ nào; không cần tối thiểu số thao tác.

Dữ liệu vào

• Dòng đầu: \(N\), \(M\).
• Dòng thứ hai: dãy \(A\).
• Dòng thứ ba: dãy \(B\).

Dữ liệu ra

In NO nếu không thể. Nếu có thể, in YES, số thao tác \(Q\) (\(0\le Q\le N^2\)), rồi \(Q\) dòng thao tác theo thứ tự thực hiện: 1 i để đổi chỗ hoặc 2 i để gộp vị trí \(i\) và \(i+1\). Mỗi chỉ số phải hợp lệ đối với độ dài hiện tại của \(X\); thao tác loại 1 còn đòi hỏi \(X_i<X_{i+1}\). Sau mọi thao tác, \(X\) phải bằng đúng \(B\).

Ràng buộc

• \(1\le M\le N\le3000\).
• \(A\) là hoán vị của \(1,\ldots,N\).
• \(1\le B_i\le N\) với mọi \(1\le i\le M\), và các phần tử của \(B\) đôi một khác nhau.

Phân nhóm

• Nhóm 1 (7 điểm): \(N\le8\).
• Nhóm 2 (8 điểm): \(M=1\).
• Nhóm 3 (12 điểm): \(M=N\).
• Nhóm 4 (10 điểm): \(A_i=i\).
• Nhóm 5 (13 điểm): \(M=N-1\).
• Nhóm 6 (15 điểm): \(B\) là dãy con của \(A\).
• Nhóm 7 (30 điểm): \(N\le300\).
• Nhóm 8 (5 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 2
1 4 2 3
3 1

YES
6
1 1
1 2
1 3
2 1
1 1
2 2

Sáu thao tác trên lần lượt biến đổi

nên kết quả đúng bằng \(B\).

2 1
1 2
2

NO

4 4
3 2 1 4
3 1 2 4

NO

4 2
1 3 2 4
1 3

NO

Nguồn

KOI 2026 Round 2, problem Sequence Operations. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.