COCI 2026 - Vòng 4

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 - Zombie Apocalypse 100 (p) 3.0s 512M
2 COCI 2026 - Tomahawk 100 (p) 1.0s 512M
3 COCI 2026 - Magija 100 (p) 1.0s 32M
4 COCI 2026 - Sladoled 100 (p) 1.0s 512M
5 COCI 2026 - Tjelesni 100 (p) 1.0s 512M

1. COCI 2026 - Zombie Apocalypse

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

Vito phải ngăn \(m\) zombie đi từ hang bí mật đến thành phố cách \(n\) mét. Mỗi giây có một zombie mới rời hang, và mọi zombie đang đi tiến thêm một mét; zombie vượt qua mét thứ \(n\) sẽ vào thành phố. Vito đặt \(k\) quả bom. Bom \((x,r,t)\) nổ ở thời điểm \(t\) và tiêu diệt mọi zombie còn trên đoạn đường có vị trí \(y\) thỏa \(|x-y|\le r\). Zombie đã vào thành phố hoặc còn ở trong hang không bị ảnh hưởng. Nhiều bom có thể nổ cùng lúc, kể cả tại cùng vị trí. Hãy đếm số zombie đến được thành phố.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n,m,k\le200\)). Mỗi trong \(k\) dòng tiếp theo chứa \(x,r,t\) (\(1\le x\le n\), \(0\le r\le n\), \(1\le t\le500\)), lần lượt là vị trí, bán kính và thời điểm nổ của một quả bom.

Dữ liệu ra

In số zombie đến được thành phố.

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

Ví dụ

Ví dụ 1

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

Ví dụ 2

Input 
7 7 1
3 2 6
Output 
2

Ví dụ 3

Input 
3 3 1
3 3 3
Output 
0

Nguồn

COCI 2025/2026 - Vòng 4, bài Zombie Apocalypse.

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

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

Miếng bít tết là ma trận \(n\times n\), ban đầu mọi nhiệt độ bằng \(0\). Có \(q\) lần nướng. Với thao tác D x (\(x\le n\)), hàng \(n\) tăng \(x\), hàng \(n-1\) tăng \(x-1\), ..., hàng \(n-x+1\) tăng \(1\). Với L x hoặc R x (\(x\le\lfloor(n+1)/2\rfloor\)), các cột gần cạnh trái hoặc phải tương ứng tăng theo cùng quy luật: cột sát cạnh tăng \(x\), rồi giảm dần đến \(1\). Hãy tìm hiệu giữa nhiệt độ lớn nhất và nhỏ nhất sau tất cả thao tác.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n\le10^9\), \(1\le q\le10^5\)). Mỗi trong \(q\) dòng sau chứa ký tự L, R hoặc D và số \(x\) hợp lệ theo mô tả.

Dữ liệu ra

In hiệu giữa nhiệt độ lớn nhất và nhỏ 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. \(7\) điểm: \(n,q\le20\).
  2. \(22\) điểm: \(n,q\le1000\).
  3. \(31\) điểm: \(n\le1000\).
  4. \(6\) điểm: \(n\) chẵn.
  5. \(4\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
4 2
L 2
R 1
Output 
2

Ví dụ 2

Input 
3 3
R 2
D 3
R 2
Output 
6

Nguồn

COCI 2025/2026 - Vòng 4, bài Tomahawk.

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

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

Có \(n\) người đứng ở các vị trí \(1\) đến \(n\). Ivor dần học các phép đổi chỗ hai đoạn rời nhau cùng độ dài: phép \((l,r,\text{len})\) đổi đồng thời hai đoạn \([l,l+\text{len}-1]\) và \([r,r+\text{len}-1]\). Sau mỗi phép đã học, có thể dùng các phép đã biết với thứ tự bất kỳ, số lần bất kỳ, và không bắt buộc dùng hết. Sự kiện 1 x hỏi vị trí nhỏ nhất và lớn nhất mà người \(x\) có thể đứng; sự kiện 2 l r len thêm một phép đổi chỗ.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n,q\le2\cdot10^5\)). Mỗi sự kiện là 1 x (\(1\le x\le n\)) hoặc 2 l r len, trong đó \(1\le\text{len}\le n\), \(l+\text{len}-1<r\), và \(r+\text{len}-1\le n\).

Dữ liệu ra

Với mỗi sự kiện loại 1, in vị trí nhỏ nhất và lớn nhất của người được hỏi.

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. \(9\) điểm: \(n,q\le5\).
  2. \(14\) điểm: \(n,q\le15\).
  3. \(22\) điểm: \(n,q\le1000\).
  4. \(11\) điểm: \(n\le4000\).
  5. \(17\) điểm: \(n\le10000\).
  6. \(37\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

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

Ví dụ 2

Input 
9 2
2 1 7 2
1 2
Output 
2 8

Nguồn

COCI 2025/2026 - Vòng 4, bài Magija.

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

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

Có \(n\) quầy kem, ban đầu không quầy nào có viên kem. Trong \(q\) ngày, ngày thứ \(i\) nhận cặp \((a,b)\): quầy \(a\) nhận một vị kem có giá trị \(b\). Tại mỗi quầy, một tổ hợp dùng ít nhất một viên kem đang có, mỗi loại được phép dùng không giới hạn lần. Giá trị tổ hợp là tổng các giá trị vị kem; chỉ xét giá trị không vượt quá \(50000\). Sau mỗi ngày, hãy in số giá trị khác nhau có thể tạo tại đúng quầy vừa nhận hàng.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n\le100\), \(1\le q\le10^5\)). Mỗi trong \(q\) dòng tiếp theo chứa \(a,b\) (\(1\le a\le n\), \(1\le b\le50000\)).

Dữ liệu ra

In \(q\) dòng, là đáp án sau từng ngày.

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. \(16\) điểm: \(n=1\), \(q\le20\).
  2. \(33\) điểm: \(q\le100\).
  3. \(61\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input 
1 2
1 3
1 5
Output 
16666
49996

Ví dụ 2

Input 
2 4
2 35625
1 25139
1 37795
2 17791
Output 
1
1
2
3

Nguồn

COCI 2025/2026 - Vòng 4, bài Sladoled.

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

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

\(n\) học sinh có chiều cao đôi một khác nhau từ \(1\) đến \(n\), ban đầu theo hoán vị \(p\). Mỗi lệnh \((l,r)\) lấy các học sinh ở đoạn vị trí \([l,r]\), rồi điền lại từ trái sang phải bằng người thấp nhất còn lại, người cao nhất còn lại, người thấp nhất còn lại, ... xen kẽ. Biết chiều cao \(m\) của Marin, hãy xác định vị trí của Marin sau khi thực hiện lần lượt mọi lệnh.

Dữ liệu vào

Dòng đầu chứa \(n,q,m\) (\(1\le n,q\le10^5\), \(1\le m\le n\)). Dòng hai là hoán vị \(p\) gồm \(n\) số. Mỗi trong \(q\) dòng tiếp theo chứa \(l,r\) (\(1\le l\le r\le n\)).

Dữ liệu ra

In vị trí cuối cùng của Marin.

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. \(7\) điểm: \(n,q\le1000\).
  2. \(11\) điểm: mọi \(l_i=1\).
  3. \(17\) điểm: \(m=1\) hoặc \(m=n\).
  4. \(24\) điểm: \(n,q\le5000\).
  5. \(51\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

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

Ví dụ 2

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

Ví dụ 3

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

Nguồn

COCI 2025/2026 - Vòng 4, bài Tjelesni.

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