COCI 2026 - Vòng 3

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 COCI 2026 - Kist 100 (p) 1.0s 512M
2 COCI 2026 - Festival 100 (p) 1.0s 512M
3 COCI 2026 - Domjenak 100 (p) 1.5s 512M
4 COCI 2026 - Drzava 100 (p) 2.0s 512M
5 COCI 2026 - Ravnalo 100 (p) 1.0s 512M

1. COCI 2026 - Kist

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Ivo đứng ở ô trung tâm của bảng vuông \(n\times n\) (với \(n\) lẻ). Ban đầu mọi ô là dấu .. Cậu có một chiếc cọ ma thuật độ dày \(k\) và thực hiện lần lượt một chuỗi ký tự in hoa: L, R, U, D lần lượt di chuyển một ô sang trái, phải, lên, xuống; các ký tự in hoa khác không di chuyển mà tô màu ký tự đó lên mọi ô có khoảng cách Manhattan nhỏ hơn \(k\) từ vị trí hiện tại. Lần tô sau có thể ghi đè lần tô trước. Nếu bước di chuyển đi ra ngoài bảng, Ivo bỏ qua bước đó.

Dữ liệu vào

Dòng đầu chứa \(n,k\) (\(1\le n,k\le50\), \(n\) lẻ). Dòng hai chứa chuỗi gồm các chữ cái in hoa tiếng Anh, có độ dài không quá \(50\).

Dữ liệu ra

In \(n\) dòng, mỗi dòng \(n\) ký tự, là trạng thái bảng sau khi thực hiện toàn bộ chuỗi lệnh.

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. \(2\) điểm: \(n=1\).
  2. \(10\) điểm: \(k=1\).
  3. \(15\) điểm: \(k=2\).
  4. \(23\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
1 1
ALURDF
Output 
F

Ví dụ 2

Input 
3 2
LUUADDRCRB
Output 
AA.
ACB
CBB

Nguồn

COCI 2025/2026 - Vòng 3, bài Kist.

Đề 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.

2. COCI 2026 - Festival

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Ivan có \(n\) viên kẹo đôi một khác nhau và cần xếp chúng vào đúng \(k\) hộp giống hệt nhau. Mỗi hộp không rỗng, mỗi viên kẹo thuộc đúng một hộp. Thứ tự các hộp không quan trọng, nhưng thứ tự các viên trong một hộp có ý nghĩa; viên lớn nhất của mỗi hộp phải đứng đầu hộp đó. Hãy đếm số cách xếp, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng duy nhất chứa \(n,k\) (\(1\le n\le5000\), \(1\le k\le n\)).

Dữ liệu ra

In số cách xếp hợp lệ theo modulo \(10^9+7\).

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. \(8\) điểm: \(k=1\).
  2. \(19\) điểm: \(k=2\).
  3. \(14\) điểm: \(n\le10\).
  4. \(29\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
3 1
Output 
2

Ví dụ 2

Input 
3 2
Output 
3

Ví dụ 3

Input 
4 2
Output 
11

Nguồn

COCI 2025/2026 - Vòng 3, bài Festival.

Đề 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.

3. COCI 2026 - Domjenak

Điểm: 100 (p) Thời gian: 1.5s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có \(2N\) người và một đồ thị bạn bè hai phía. Mỗi người đến dự tiệc cùng đúng một người bạn, nhưng các cặp đó đã bị quên; đề bảo đảm có đúng một cách chia tất cả mọi người thành \(N\) cặp bạn bè như vậy. Khi một người biết câu chuyện và người đi cùng họ chưa biết, họ bắt buộc truyền cho người đi cùng trước. Nếu không, họ có thể truyền cho một người bạn khác chưa biết; mỗi người chỉ truyền một lần. Hãy tìm số người lớn nhất có thể nghe câu chuyện và in một thứ tự truyền đạt đạt được số đó.

Dữ liệu vào

Dòng đầu chứa \(N,M\) (\(1\le N\le5\cdot10^5\), \(N\le M\le10^6\)). \(M\) dòng tiếp theo chứa cạnh bạn bè \(u_i,v_i\) (\(1\le u_i,v_i\le2N\), \(u_i\ne v_i\)). Đồ thị có thể chia thành hai nhóm sao cho mỗi cạnh nối hai nhóm khác nhau.

Dữ liệu ra

Dòng đầu in \(K\), số người lớn nhất có thể nghe câu chuyện. Dòng hai in \(K\) số \(a_1,\ldots,a_K\) sao cho kể câu chuyện cho \(a_1\) thì mỗi \(a_i\) có thể truyền cho \(a_{i+1}\). Nếu có nhiều dãy tối ưu, in một dãy 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. \(24\) điểm: \(N\le10\).
  2. \(16\) điểm: mỗi người có nhiều nhất hai người bạn.
  3. \(30\) điểm: \(N\le2000\), \(M\le5000\).
  4. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
2 3
1 2
1 4
3 4
Output 
4
2 1 4 3

Ví dụ 2

Input 
3 5
1 2
2 3
1 4
4 5
2 5
Output 
4
6 1 2 3

Ví dụ 3

Input 
4 8
1 2
2 3
3 4
4 1
2 5
3 6
4 7
7 8
Output 
6
6 3 4 1 2 5

Nguồn

COCI 2025/2026 - Vòng 3, bài Domjenak.

Đề 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.

4. COCI 2026 - Drzava

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một đất nước gồm \(n\) thành phố là một cây. Một quốc gia chọn một thủ đô và một số thành phố phụ thuộc. Với mỗi thành phố phụ thuộc, đường từ thủ đô đến thành phố đó không được đi qua bất kỳ thành phố phụ thuộc nào khác. Với từng \(k\), hãy đếm số quốc gia khác nhau có đúng \(k\) thành phố, modulo \(10^9+7\). Hai lựa chọn khác nhau nếu khác thủ đô hoặc khác ít nhất một thành phố phụ thuộc.

Dữ liệu vào

Dòng đầu chứa \(n\) (\(1\le n\le3000\)). \(n-1\) dòng sau chứa cạnh \(u,v\) (\(1\le u,v\le n\), \(u\ne v\)) của cây. Khoảng cách giữa mọi cặp thành phố trong dữ liệu chính thức nhỏ hơn \(36\) cạnh.

Dữ liệu ra

In \(n\) số: số quốc gia hợp lệ có kích thước từ \(1\) đến \(n\), theo modulo \(10^9+7\).

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. \(18\) điểm: \(n\le15\).
  2. \(17\) điểm: \(n\le200\).
  3. \(26\) điểm: \(n\le600\).
  4. \(49\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
4
1 2
1 3
1 4
Output 
4 12 6 1

Ví dụ 2

Input 
4
1 2
2 3
1 4
Output 
4 12 4 0

Nguồn

COCI 2025/2026 - Vòng 3, bài Drzava.

Đề 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.

5. COCI 2026 - Ravnalo

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Một bức tường gồm \(n\) cột đứng kề nhau, cột \(i\) cao \(a_i\) và rộng \(1\). Cột \(i\) được chia thành \(b_i\) phần có chiều cao bằng nhau. Dùng một nét bút có thể vẽ một đoạn thẳng mà không nhấc bút. Hãy vẽ toàn bộ biên các cột và các đường phân chia bằng số đoạn thẳng ít nhất.

Dữ liệu vào

Dòng đầu chứa \(n\) (\(1\le n\le10^5\)). Dòng hai chứa \(a_1,\ldots,a_n\) (\(1\le a_i\le10^9\)). Dòng ba chứa \(b_1,\ldots,b_n\) (\(1\le b_i\le10^9\)).

Dữ liệu ra

In số đoạn thẳng nhỏ nhất cần vẽ.

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. \(11\) điểm: \(N=1\).
  2. \(13\) điểm: \(N=2\), \(1\le a_i,b_i\le10\).
  3. \(29\) điểm: \(a_i\le10^6\) và \(b_i\) chia hết \(a_i\) với mọi \(i\).
  4. \(57\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
3
4 6 4
2 3 4
Output 
10

Ví dụ 2

Input 
3
4 6 3
3 3 2
Output 
12

Nguồn

COCI 2025/2026 - Vòng 3, bài Ravnalo.

Đề 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.