COCI 2026 - Vòng 5

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 - Škare 100 (p) 3.0s 512M
2 COCI 2026 - Težina 100 (p) 2.0s 512M
3 COCI 2026 - Pet 100 (p) 1.0s 512M
4 COCI 2026 - Slaganje 100 (p) 1.0s 512M
5 COCI 2026 - Struktura 100 (p) 1.0s 512M

1. COCI 2026 - Škare

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

Fran ban đầu có một dải giấy dài \(n\) cm. Lana đưa ra \(k\) chỉ dẫn dạng: cắt dải thứ \(x\) tại vị trí cách đầu trái \(l\) cm. Nếu hiện có dãy độ dài \(a_1,a_2,\ldots,a_m\), sau chỉ dẫn này dải \(a_x\) được thay trong dãy bằng hai dải có độ dài \(l\) và \(a_x-l\); thứ tự của các dải còn lại không đổi. Sau khi thực hiện hết các lần cắt, hãy tính có bao nhiêu độ dài dải giấy khác nhau còn lại.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,k\) (\(2\le n\le500\), \(1\le k<n\)), lần lượt là độ dài ban đầu và số chỉ dẫn. Dòng thứ \(i\) trong \(k\) dòng sau chứa \(x_i,l_i\) (\(1\le x_i\le i\), \(1\le l_i<L\)), trong đó \(L\) là độ dài của dải thứ \(x_i\) ngay trước lần cắt thứ \(i\); các dải được đánh số từ trái sang phải trong dãy hiện thời.

Dữ liệu ra

In một số nguyên: số độ dài dải giấy khác nhau sau mọi lần cắt.

Ràng buộc

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

Phân nhóm

  1. \(9\) điểm: \(k\le3\).
  2. \(6\) điểm: \(l_i=1\) với mọi \(i\).
  3. \(13\) điểm: \(x_i=i\) với mọi \(i\).
  4. \(22\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
5 1
1 2
Output 
2

Ví dụ 2

Input 
6 2
1 4
1 2
Output 
1

Ví dụ 3

Input 
10 3
1 2
2 3
3 2
Output 
2

Nguồn

COCI 2025/2026 - Vòng 5, bài Škare.

Đề 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 - Težina

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

Cho mảng \(a\) gồm \(n\) vật nặng và số nguyên \(k\), là số loại tạ Karlo có thể dùng. Với từng loại tạ \(j\) từ \(1\) đến \(k\), và với từng vật có khối lượng \(a_i\), Karlo lần lượt lấy phần nguyên của \(a_i/j\), nhân kết quả với \(a_i+2\), rồi thay giá trị đó bằng \(10^8\) nếu nó lớn hơn \(10^8\). Tổng các giá trị thu được trên mọi vật là sức mạnh của loại tạ \(j\). Hãy tính tổng sức mạnh của tất cả \(k\) loại tạ.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,k\) (\(1\le n,k\le10^5\)), lần lượt là số vật và số loại tạ. Dòng thứ hai chứa \(n\) số nguyên \(a_i\) (\(1\le a_i\le10^5\)), là khối lượng các vật.

Dữ liệu ra

In một số nguyên: tổng sức mạnh cần tìm.

Ràng buộc

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

Phân nhóm

  1. \(17\) điểm: \(k\le300\).
  2. \(19\) điểm: mảng \(a\) có không quá \(300\) giá trị phân biệt.
  3. \(34\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
1 2
2
Output 
12

Ví dụ 2

Input 
2 1
3 4
Output 
39

Ví dụ 3

Input 
7 19
1 2 3 4 5 6 7
Output 
414

Nguồn

COCI 2025/2026 - Vòng 5, bài Težina.

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

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

Hồ được biểu diễn bởi ma trận \(n\times m\): 0 là nước và 1 là lá sen. Từ một lá sen, ếch Maša có thể nhảy tới bất kỳ lá sen khác nào cùng hàng hoặc cùng cột. Nếu lần nhảy trước thay đổi cột, lần nhảy kế tiếp phải thay đổi hàng; nếu lần nhảy trước thay đổi hàng, lần nhảy kế tiếp phải thay đổi cột. Ngay sau khi Maša rời một lá sen, lá đó chìm và không thể được dùng lại. Maša được chọn tùy ý lá sen đầu tiên và phải đi qua đúng \(5\) lá sen, kể cả lá bắt đầu. Hãy đếm số đường đi có thể. Hai đường đi là khác nhau nếu vị trí của ít nhất một trong năm lá sen trên đường đi khác nhau.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,m\) (\(1\le n,m\le2000\)). \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) ký tự 0 hoặc 1, mô tả các ô của hồ.

Dữ liệu ra

In một số nguyên: số đường đi hợp lệ.

Ràng buộc

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

Phân nhóm

  1. \(8\) điểm: \(n,m\le4\).
  2. \(27\) điểm: \(n,m\le10\).
  3. \(58\) điểm: \(n,m\le400\).
  4. \(17\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
2 3
111
110
Output 
4

Ví dụ 2

Input 
4 4
1111
1111
1111
1111
Output 
2304

Ví dụ 3

Input 
2 5
11110
01111
Output 
48

Nguồn

COCI 2025/2026 - Vòng 5, bài Pet.

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

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

Cho một cây có \(N\) đỉnh được gán nhãn từ \(1\) đến \(N\). Cũng có một đa giác đều \(N\) đỉnh với các vị trí được đánh số từ \(1\) đến \(N\). Hãy đặt \(N\) bản sao của cây lên đa giác: trong mỗi bản sao, các đỉnh cây được đặt vào các vị trí khác nhau. Tương đương, cần in các số \(p_{ij}\) sao cho mỗi hàng \((p_{i1},p_{i2},\ldots,p_{iN})\) là một hoán vị của \(1..N\), và với mọi cặp vị trí \(a<b\), tồn tại một hàng \(i\) mà \(p_{ia}\) và \(p_{ib}\) là hai đầu mút của một cạnh cây. Nói cách khác, hợp các cạnh của mọi bản sao phải phủ mọi cạnh và đường chéo của đa giác. Đề bài bảo đảm luôn tồn tại lời giải.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\) (\(3\le N\le2000\)), là số đỉnh của cây và của đa giác. \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) (\(1\le u,v\le N\)), biểu diễn một cạnh của cây.

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(i\) chứa \(p_{i1},p_{i2},\ldots,p_{iN}\) theo thứ tự. Mỗi hàng phải là một hoán vị hợp lệ; chấp nhận bất kỳ cấu trúc nào thỏa các điều kiện trên.

Ràng buộc

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

Phân nhóm

  1. \(10\) điểm: tồn tại một đỉnh thuộc mọi cạnh của cây.
  2. \(15\) điểm: \(N\le10\).
  3. \(20\) điểm: cây là một đường đi.
  4. \(25\) điểm: \(N\le300\).
  5. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

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

Ví dụ 2

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

Ví dụ 3

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

Nguồn

COCI 2025/2026 - Vòng 5, bài Slaganje.

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

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

Petar chọn ngẫu nhiên và độc lập \(n\) số nguyên từ \(1\) đến \(k\), tạo thành mảng \(a\). Mảng \(a\) được gọi là cấu trúc khi đồng thời thỏa hai điều kiện: mỗi số từ \(1\) đến \(n\) xuất hiện đúng một lần trong mảng; và với mọi chỉ số \(i\) (\(1\le i\le n\)), có \(|a_i+i-n-1|\le1\). Hãy tính xác suất để mảng ngẫu nhiên là một cấu trúc.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,k\) (\(1\le n,k\le10^9\)).

Dữ liệu ra

Có thể biểu diễn xác suất dưới dạng phân số tối giản \(P/Q\), trong đó \(Q\) không chia hết cho \(10^9+7\). In \(P\cdot Q^{-1}\pmod {10^9+7}\).

Ràng buộc

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

Phân nhóm

  1. \(17\) điểm: \(n,k\le7\).
  2. \(23\) điểm: \(n\le7\), \(k\le100\).
  3. \(19\) điểm: \(n\le20\), \(k\le100\).
  4. \(25\) điểm: \(n,k\le10^6\).
  5. \(26\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
2 1
Output 
0

Ví dụ 2

Input 
2 2
Output 
500000004

Ví dụ 3

Input 
7 94
Output 
100976822

Nguồn

COCI 2025/2026 - Vòng 5, bài Struktura.

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