KOI 2026 - Vòng 2 - Tiểu học

Có \(N\) học sinh đứng trên một trục số. Học sinh được đánh số từ \(1\) đến \(N\) và phải đứng theo thứ tự từ trái sang phải; mọi vị trí đều là số nguyên.

Gọi \(B_i\) là vị trí của học sinh \(i\). Với mỗi \(i\), học sinh \(i\) không được đứng bên phải \(A_i\), tức là \(B_i \le A_i\). Hai học sinh liên tiếp phải cách nhau ít nhất \(K\), tức là \(B_{i+1} - B_i \ge K\). Khi \(K = 0\), nhiều học sinh có thể đứng cùng một vị trí.

Mọi \(B_i\) phải là số nguyên nhưng không có cận dưới; vị trí âm vẫn được phép.

Hãy tìm một dãy \([B_1, B_2, \ldots, B_N]\) thỏa các điều kiện trên và làm lớn nhất có thể giá trị \(B_1\). Nếu có nhiều dãy tối ưu, in ra bất kỳ dãy nào. Có thể chứng minh luôn tồn tại ít nhất một dãy hợp lệ.

Dữ liệu vào

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

Dữ liệu ra

In ra \(N\) số nguyên \(B_1, B_2, \ldots, B_N\). Dãy phải hợp lệ và \(B_1\) phải lớn nhất có thể.

Ràng buộc

• \(1 \le N \le 100\).
• \(0 \le K \le 10\).
• \(1 \le A_i \le 100\).

Phân nhóm

• Nhóm 1 (25 điểm): \(A_{i+1} - A_i \ge K\) với mọi \(1 \le i < N\).
• Nhóm 2 (35 điểm): \(K = 0\).
• Nhóm 3 (30 điểm): tồn tại một dãy hợp lệ có \(0 \le B_1 \le 100\).
• Nhóm 4 (10 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 2
1 4 10 9 13

1 4 6 9 12

4 0
5 2 7 3

2 2 3 3

4 3
2 1 5 9

-2 1 5 8

Nguồn

KOI 2026 Round 2, problem Distancing. 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\) 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.