COCI 2026 - Vòng 2

Marko biết trước vị trí của \(k\) quả mìn trên bảng gồm \(n\) hàng và \(m\) cột; mỗi ô có nhiều nhất một quả mìn. Hãy điền vào mỗi ô không có mìn số lượng mìn nằm trong tám ô kề xung quanh nó. Ô có mìn được ký hiệu là B.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n,m\le500\), \(1\le k\le n\cdot m\)). \(k\) dòng tiếp theo, dòng thứ \(i\) chứa \(r_i,s_i\) (\(1\le r_i\le n\), \(1\le s_i\le m\)), là vị trí của một quả mìn.

Dữ liệu ra

In \(n\) dòng, mỗi dòng gồm \(m\) ký tự cách nhau bởi khoảng trắng, là bảng theo yêu cầu.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(15\) điểm: \(n=1\).
2. \(18\) điểm: \(k=1\).
3. \(17\) điểm: không có ràng buộc thêm.

Ví dụ

1 6 1
1 3

0 1 B 1 0 0

3 3 3
1 1
2 3
1 3

B 3 B
1 3 B
0 1 1

Nguồn

COCI 2025/2026 - Vòng 2, bài Minesweeper.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.

Mỗi học sinh \(i\) ở trường trong khoảng thời gian nửa kín từ mili giây \(l_i\) đến trước \(r_i\). Một lớp phụ đạo cần có ít nhất \(k\) học sinh, và mọi học sinh tham gia phải ở trường trong toàn bộ thời gian của lớp. Hãy tìm thời lượng lớn nhất có thể tổ chức, hoặc \(0\) nếu không thể tổ chức lớp.

Dữ liệu vào

Dòng đầu chứa \(n,k\) (\(1\le n,k\le3\cdot10^5\)). \(n\) dòng tiếp theo chứa \(l_i,r_i\) (\(1\le l_i<r_i\le86\,400\,000\)).

Dữ liệu ra

In thời lượng lớn nhất có thể tổ chức lớp phụ đạo, hoặc 0.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(13\) điểm: \(k=1\).
2. \(27\) điểm: \(n\le1000\), \(k=2\).
3. \(11\) điểm: \(r_i\le100\).
4. \(19\) điểm: không có ràng buộc thêm.

Ví dụ

5 1
1 3
1 4
1 5
1 6
1 7

6

5 2
6 10
8 14
5 9
5 6
4 6

3

Nguồn

COCI 2025/2026 - Vòng 2, bài Dodatna.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.

Dino xuất phát tại ô S của một bảng, nơi có các kiện hàng. Mỗi ô X là một đích cần giao đúng một kiện. Mỗi lần Dino mang được nhiều nhất hai kiện, có thể nhặt hoặc đặt kiện không tốn thời gian, và đi một ô kề cạnh không bị chặn trong một giây. Hãy tìm thời gian nhỏ nhất để giao đủ hàng đến mọi ô X và quay lại S, hoặc -1 nếu không thể.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n,m\le500\), \(1\le k\le67\)). \(n\) dòng tiếp theo mô tả bảng với các ký tự ., #, S, X; ký tự X xuất hiện đúng \(k\) lần.

Dữ liệu ra

In thời gian nhỏ nhất để hoàn thành và trở về ô xuất phát, hoặc -1.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(17\) điểm: \(k=2\).
2. \(26\) điểm: \(k\le16\).
3. \(29\) điểm: \(k\le22\).
4. \(38\) điểm: không có ràng buộc thêm.

Ví dụ

5 5 3
X...X
.....
.....
.....
S...X

24

5 5 4
..X..
#X#..
#...X
.SX#.
.....

16

Nguồn

COCI 2025/2026 - Vòng 2, bài Natjecanje.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.

Một dãy là hợp lệ nếu không giảm. Ivica được phép lặp lại thao tác thay hai phần tử kề nhau bằng tổng của chúng. Hãy tạo một dãy hợp lệ có độ dài lớn nhất có thể từ dãy ban đầu và in một dãy đạt độ dài đó.

Dữ liệu vào

Dòng đầu chứa \(n\) (\(1\le n\le5000\)). Dòng hai chứa \(n\) số \(a_i\) (\(1\le a_i\le10^9\)).

Dữ liệu ra

Dòng đầu in độ dài lớn nhất \(m\). Dòng hai in \(m\) phần tử của một dãy hợp lệ có độ dài \(m\) có thể nhận được. Nếu có nhiều đáp án, in một đáp án bất kỳ.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(10\) điểm: \(n\le20\).
2. \(15\) điểm: \(n\le100\), \(a_i\le100\).
3. \(20\) điểm: \(n\le500\).
4. \(25\) điểm: \(n\le1000\).
5. \(40\) điểm: không có ràng buộc thêm.

Với mỗi testcase, dòng đầu đúng nhận 60% số điểm; 40% còn lại chỉ nhận khi dòng hai là một phép gộp hợp lệ tạo dãy không giảm.

Ví dụ

6
3 2 6 3 3 8

4
5 6 6 8

7
3 6 4 2 6 2 5

5
3 6 6 6 7

Nguồn

COCI 2025/2026 - Vòng 2, bài Rastući.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.

Có đúng một khối lập phương của mỗi kích thước từ \(1\) đến \(n\), màu P hoặc C. Một tháp hợp lệ có các khối theo thứ tự kích thước giảm dần từ dưới lên, và hai khối kề nhau không cùng màu. Với mỗi truy vấn \([l,r]\), hãy tìm số tháp nhỏ nhất để dùng tất cả các khối có kích thước trong đoạn đó.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n,q\le10^5\)). Dòng hai là chuỗi \(s\) độ dài \(n\), mỗi ký tự là P hoặc C; \(s_i\) là màu khối kích thước \(i\). \(q\) dòng tiếp theo chứa \(l_i,r_i\) (\(1\le l_i\le r_i\le n\)).

Dữ liệu ra

Với mỗi truy vấn, in số tháp nhỏ nhất trên một dòng.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(23\) điểm: \(n,q\le10\).
2. \(38\) điểm: \(n,q\le1000\).
3. \(25\) điểm: có nhiều nhất \(20\) khối màu xanh.
4. \(24\) điểm: không có ràng buộc thêm.

Ví dụ

7 4
PPCPPCC
1 7
1 5
3 7
4 5

3
3
2
2

6 2
CCCCCC
1 6
2 5

6
4

16 1
PPPCPCCCCCCPPPPP
1 16

6

Nguồn

COCI 2025/2026 - Vòng 2, bài Tornjevi.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.