COCI 2026 - Vòng 6

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 - Čokolada 100 (p) 1.0s 512M
2 COCI 2026 - Džeparac 100 (p) 1.0s 512M
3 COCI 2026 - Prepisivanje 100 (p) 1.0s 512M
4 COCI 2026 - Skijanje 100 (p) 1.0s 512M
5 COCI 2026 - Učionica 100 (p) 1.5s 512M

1. COCI 2026 - Čokolada

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

Luka có một thanh sô-cô-la gồm \(n\) hàng và \(m\) cột, mỗi ô là sô-cô-la trắng hoặc đen. Luka chỉ muốn ăn phần đen. Trước khi ăn, cậu có thể cắt dọc giữa hai cột, từ mép trên đến mép dưới của thanh, và/hoặc cắt ngang giữa hai hàng, từ mép trái đến mép phải. Sau các lần cắt, các mảnh đều là hình chữ nhật. Hãy tìm số nhát cắt ít nhất để mỗi mảnh chỉ gồm một màu sô-cô-la.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,m\) (\(1\le n,m\le200\)), là số hàng và số cột. Mỗi trong \(n\) dòng tiếp theo chứa \(m\) ký tự 0 hoặc 1: 0 là ô trắng, 1 là ô đen.

Dữ liệu ra

In số nhát cắt nhỏ nhất cần thực hiện.

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. \(5\) điểm: thanh sô-cô-la là bàn cờ; ô hàng \(i\), cột \(j\) màu trắng khi \(i+j\) chẵn và màu đen khi \(i+j\) lẻ.
  2. \(11\) điểm: \(n=1\).
  3. \(11\) điểm: đúng một ô có màu đen.
  4. \(23\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
4 7
0000000
0111000
0111100
0000000
Output 
6
Note

Hình 1: Một cách thực hiện sáu nhát cắt cho ví dụ 1.

Ví dụ 2

Input 
4 5
00000
01100
01100
00000
Output 
4

Ví dụ 3

Input 
4 4
0101
1010
0101
1010
Output 
6

Nguồn

COCI 2025/2026 - Vòng 6, bài Čokolada.

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

2. COCI 2026 - Džeparac

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

Antonija có \(N\) euro và phải dùng hết. Cô được giữ lại một số nguyên không âm \(k\) (\(0\le k\le N\)); số tiền \(N-k\) còn lại được chia đều cho hai con trai trong \(d\) ngày. Mỗi ngày, nếu một người nhận \(x\) euro thì người kia cũng nhận \(x\) euro, với \(x\) là số nguyên dương. Cô cũng có thể không chia tiền, tương ứng với \(k=N,d=0\). Hai cách chia khác nhau nếu khác \(k\), khác \(d\), hoặc dãy số tiền nhận mỗi ngày khác nhau. Hãy đếm số cách chia, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\) (\(1\le N\le10^{18}\)).

Dữ liệu ra

In số cách chia 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. \(12\) điểm: \(N\le10\).
  2. \(17\) điểm: \(N\le1000\).
  3. \(36\) điểm: \(N\le10^6\).
  4. \(5\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
4
Output 
4

Ví dụ 2

Input 
5
Output 
4

Ví dụ 3

Input 
793
Output 
137435472

Nguồn

COCI 2025/2026 - Vòng 6, bài Džeparac.

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

3. COCI 2026 - Prepisivanje

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

Lớp học là ma trận \(n\times m\), mỗi ô là một chỗ ngồi. Giá trị 2 là học sinh ngoan đã ngồi sẵn; 1 là ghế bị cấm; 0 là ghế trống cho học sinh nghịch ngợm. Giáo viên được chọn các ghế trống sẽ có học sinh nghịch ngợm ngồi. Học sinh ngoan không quay cóp, nhưng một học sinh nghịch ngợm sẽ quay cóp nếu có ít nhất một học sinh, ngoan hoặc nghịch ngợm, ở một trong bốn ô kề cạnh trên, dưới, trái, phải. Hãy tìm tổng số học sinh lớn nhất có thể ngồi trong lớp sao cho không có ai quay cóp.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,m\) (\(1\le n,m\le80\)). Mỗi trong \(n\) dòng tiếp theo chứa \(m\) ký tự 0, 1 hoặc 2, mô tả lớp học.

Dữ liệu ra

In tổng số học sinh lớn nhất thỏa điều kiện.

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: \(n,m\le4\).
  2. \(15\) điểm: mọi ô của ma trận đều là 0.
  3. \(16\) điểm: \(n=2\).
  4. \(52\) điểm: \(n\le15\).
  5. \(19\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
4 4
0100
0202
1000
2120
Output 
6

Ví dụ 2

Input 
4 4
0000
0000
0000
0000
Output 
8

Nguồn

COCI 2025/2026 - Vòng 6, bài Prepisivanje.

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

4. COCI 2026 - Skijanje

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

Khu nghỉ trượt tuyết có \(n\) điểm apres-ski tạo thành một cây gốc tại điểm \(1\). Mỗi dốc được hướng từ nhãn nhỏ hơn sang nhãn lớn hơn. Với mỗi \(i>1\), dốc \(i\) đi từ \(p_i\) đến \(i\), trong đó \(p_i<i\); dốc này có độ vui \(z_i\) và tốc độ \(b_i\). Mia chọn một lượt đi gồm nhiều nhất \(k\) dốc liên tiếp theo chiều các dốc. Gọi \(z_{first}\) và \(z_{last}\) là độ vui của dốc đầu và cuối; độ hỗn loạn của lượt đi là

\[z_{last}\cdot\left(z_{last}+\sum b_i\right)+z_{first}^2,\]

trong đó tổng lấy trên các dốc của lượt đi. Khi \(k=1\), công thức vẫn giữ nguyên và hai dốc đầu, cuối trùng nhau. Hãy tìm độ hỗn loạn lớn nhất.

Dữ liệu vào

Dòng đầu chứa \(n,k\) (\(1\le k\le n\le3\cdot10^5\)). Dòng thứ hai chứa \(n-1\) số nguyên, số thứ \(i\) là \(p_{i+1}\) (\(1\le p_i<i\)). Dòng thứ ba chứa \(n-1\) số \(z_2,\ldots,z_n\) (\(1\le z_i\le10^5\)). Dòng thứ tư chứa \(n-1\) số \(b_2,\ldots,b_n\) (\(-10^5\le b_i\le10^5\)).

Dữ liệu ra

In độ hỗn loạn lớn nhất.

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. \(14\) điểm: \(n\le1000\).
  2. \(23\) điểm: với mọi \(1\le i<n\), có \(z_i=1\) và \(b_i>1\).
  3. \(35\) điểm: \(n\le50000\).
  4. \(38\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

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

Ví dụ 2

Input 
9 2
1 2 1 1 4 3 6 5
1 3 7 8 4 1 8 2
1 -7 -1 -6 3 8 -1 6
Output 
120

Nguồn

COCI 2025/2026 - Vòng 6, bài Skijanje.

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

5. COCI 2026 - Učionica

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

Có \(k\) người bạn muốn vào một lớp học là ma trận \(n\times m\). Mỗi ghế hoặc trống (giá trị \(0\)), hoặc đã có học sinh với chiều cao bằng giá trị tại ô. Nhóm chọn một hàng \(i\) và \(k\) ghế trống liên tiếp từ cột \(j\) đến \(j+k-1\); họ được ngồi theo bất kỳ thứ tự nào. Một người chỉ ngồi được tại ghế khi mọi học sinh ở phía trước, tức cùng cột và có chỉ số hàng nhỏ hơn, đều thấp hơn nghiêm ngặt người đó. Hãy đếm số tập \(k\) ghế liên tiếp mà nhóm có thể sắp xếp để tất cả đều nhìn rõ.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n,m\le2000\), \(1\le k\le m\)). Dòng hai chứa chiều cao \(h_1,h_2,\ldots,h_k\) của các bạn. \(n\) dòng sau, mỗi dòng chứa \(m\) số nguyên \(a_{i,j}\); \(a_{i,j}=0\) nếu ghế trống, còn \(a_{i,j}\ge1\) là chiều cao của học sinh đang ngồi.

Dữ liệu ra

In số tập ghế liên tiếp phù hợp.

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: \(k\le2\).
  2. \(13\) điểm: \(n,m\le200\).
  3. \(29\) điểm: \(n,m\le500\).
  4. \(57\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
3 4 2
2 6
0 0 3 1
8 0 0 0
0 0 1 0
Output 
3

Ví dụ 2

Input 
2 4 4
5 2 4 3
1 2 3 4
0 0 0 0
Output 
1

Ví dụ 3

Input 
5 5 3
17 3 17
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Output 
15

Nguồn

COCI 2025/2026 - Vòng 6, bài Učionica.

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