COCI 2026 - Vòng 1 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	COCI 2026 - Rima	100 (p)	1.0s	512M
2	COCI 2026 - Krugomet	100 (p)	1.0s	512M
3	COCI 2026 - Harmonija	100 (p)	3.0s	1G
4	COCI 2026 - Kraljica	100 (p)	5.0s	512M
5	COCI 2026 - Zagi	100 (p)	3.0s	512M

1. COCI 2026 - Rima

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

Trong giờ Ngữ văn Croatia, Jakov đọc một bài thơ gồm \(n\) dòng và \(n/4\) khổ. Bốn dòng liên tiếp tạo thành một khổ; mỗi dòng có đúng \(m\) từ.

Hai dòng vần khi \(k\) chữ cái cuối của từ cuối cùng của chúng trùng nhau. Nếu một từ cuối có ít hơn \(k\) chữ cái thì hai dòng không vần. Một khổ có thể có các sơ đồ vần sau:

AABB: dòng 1 vần dòng 2, dòng 3 vần dòng 4;
ABAB: dòng 1 vần dòng 3, dòng 2 vần dòng 4;
ABBA: dòng 1 vần dòng 4, dòng 2 vần dòng 3.

Hãy đếm số khổ có từng sơ đồ vần. Một khổ có thể thỏa nhiều sơ đồ vần.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n\le500\), \(n\) chia hết cho \(4\), \(1\le m,k\le20\)). \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) từ; mỗi từ có không quá \(20\) chữ cái thường tiếng Anh.

Dữ liệu ra

In ba số: số khổ có vần AABB, ABAB, ABBA, theo thứ 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

\(15\) điểm: \(n=4\).
\(15\) điểm: mọi từ chỉ có một ký tự.
\(20\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

8 2 3
aa bb
cc bb
dd ee
ff ee
auu aaaaaahh
auu wer
asdf power
lol kldahh

Output

0 0 1

Ví dụ 2

Input

8 2 2
ja programiram
mjesec listopad
ponekad chillam
voda vodopad
banana jabuka
fiziku znam
teska odluka
njam njam

Output

0 2 0

Ví dụ 3

Input

4 4 2
pas konj zec macka
trokut teziste poluravnina tocka
nogomet tenis ragbi odbojka
sir mlijeko kulen sunka

Output

1 1 1

Nguồn

COCI 2025/2026 - Vòng 1, bài Rima.

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

Đ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 đứng thành vòng tròn. Học sinh \(i\) đang có \(a_i\) quả bóng và chọn một người mình thích \(s_i\) (có thể là chính mình). Trò chơi có \(k\) lượt; trong mỗi lượt, mọi người đồng thời ném toàn bộ bóng cho người mình thích và luôn bắt được toàn bộ bóng gửi đến.

Sau \(k\) lượt, hãy xác định số bóng lớn nhất mà một học sinh có và tất cả chỉ số học sinh đạt số bóng đó, theo thứ tự tăng dần.

Dữ liệu vào

Dòng đầu chứa \(n,k\) (\(1\le n\le10^5\), \(1\le k\le10^9\)). Dòng hai chứa \(n\) số \(a_i\) (\(1\le a_i\le1000\)). Dòng ba chứa \(n\) số \(s_i\) (\(1\le s_i\le n\)).

Dữ liệu ra

Dòng đầu in số bóng lớn nhất. Dòng hai in các chỉ số học sinh đạt giá trị đó theo thứ tự tăng dầ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

\(14\) điểm: \(n,k\le1000\).
\(26\) điểm: dãy \(s\) là hoán vị.
\(30\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

2 1
5 6
2 1

Output

6
1

Ví dụ 2

Input

4 2
5 5 5 5
1 2 1 1

Output

15
1

Ví dụ 3

Input

4 10000000
1 2 3 4
2 1 4 3

Output

4
4

Nguồn

COCI 2025/2026 - Vòng 1, bài Krugomet.

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

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

Cho cây \(n\) đỉnh. Đỉnh \(i\) có giá trị đỏ \(c_i\) và xanh \(p_i\). Với mỗi truy vấn đường đi ngắn nhất từ \(A\) đến \(B\), duyệt các đỉnh trên đường theo thứ tự và chọn đỏ hoặc xanh cho từng đỉnh.

Một tiền tố của đường đi là hài hòa nếu số lần chọn một màu không nhiều hơn màu còn lại ít nhất ba lần. Mọi thời điểm trong quá trình chọn màu phải hài hòa. Giá trị của đường đi là tổng giá trị theo các màu đã chọn. Hãy tìm giá trị lớn nhất của một cách tô hài hòa cho mỗi truy vấn.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n,q\le10^5\)). Dòng hai chứa \(c_i\) và dòng ba chứa \(p_i\) (\(-10^9\le c_i,p_i\le10^9\)). \(n-1\) dòng tiếp theo là các cạnh cây. \(q\) dòng cuối chứa \(u,v\) của các truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in giá trị lớn nhất của cách tô hài hòa 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

\(27\) điểm: \(n,q\le15\).
\(41\) điểm: \(n,q\le1000\).
\(19\) điểm: \(q\le10000\).
\(23\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

4 1
10 10 10 10
-10 0 -10 0
1 2
2 3
3 4
1 4

Output

Ví dụ 2

Input

5 3
-5 -4 0 -3 3
3 1 -5 0 0
3 2
1 4
3 5
1 2
2 5
5 3

Output

4
3
3

Nguồn

COCI 2025/2026 - Vòng 1, bài Harmonija.

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

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

Nữ hoàng Sofia ở bàn cờ \(n\times m\) có ô bắt đầu S, ô thoát E, ô trống ., và ô chặn #. Một chữ số từ 1 đến 9 nếu xuất hiện sẽ xuất hiện đúng hai lần; khi đáp xuống ô số, Sofia có thể dịch chuyển tức thời sang ô cùng số mà không tốn thêm bước. Sau dịch chuyển tức thời, cô không thể tiếp tục đi cùng hướng mà không trả thêm một bước.

Trong một bước, Sofia có thể nhảy tới bất kỳ ô nào cùng hàng, cột hoặc đường chéo, miễn không có ô chặn giữa hai ô (kể cả hai đầu mút). Hãy tìm số bước ít nhất từ S đến E, hoặc -1 nếu không thể.

Dữ liệu vào

Dòng đầu chứa \(n,m\) (\(1\le n,m\le1000\)). \(n\) dòng tiếp theo chứa bảng gồm các ký tự S, E, ., # và các chữ số 1--9.

Dữ liệu ra

In số bước ít nhất, hoặc -1 nếu không thể đến ô thoá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

\(24\) điểm: \(n,m\le5\).
\(32\) điểm: không có cổng dịch chuyển.
\(18\) điểm: \(n,m\le500\).
\(36\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

4 4
S..1
####
1.#E
....

Output

Ví dụ 2

Input

3 3
S..
.#.
..E

Output

Ví dụ 3

Input

5 4
S.21
####
2##1
###.
E..#

Output

Nguồn

COCI 2025/2026 - Vòng 1, bài Kraljica.

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

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

Krastoboj là trò chơi hai người trên các dãy số nguyên dương. Ở một lượt, người chơi chọn một dãy hiện có và một giá trị \(x\) xuất hiện trong dãy, xóa mọi lần xuất hiện của \(x\); các đoạn còn lại tạo thành các dãy mới. Người không thể đi thua.

Ban đầu có một dãy con liên tiếp của dãy mẫu \(a\). Với mỗi truy vấn \([l,r]\), hãy cho biết người thắng khi Toni đi trước và cả hai chơi tối ưu.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n,q\le10^5\)). Dòng hai chứa \(a_i\) (\(1\le a_i\le32\)). \(q\) dòng tiếp theo chứa \(l,r\) (\(1\le l\le r\le n\)).

Dữ liệu ra

Với mỗi truy vấn, in Toni hoặc Jakov 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

\(15\) điểm: \(n,q\le10\).
\(11\) điểm: \(n,q\le1000\) và \(a_i\le2\).
\(18\) điểm: \(n,q\le1000\).
\(14\) điểm: \(a_i\le2\).
\(23\) điểm: \(a_{l_i}=a_{r_i}\) với mọi truy vấn.
\(29\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

6 4
1 3 2 3 1 2
1 1
2 3
2 4
1 3

Output

Toni
Jakov
Toni
Toni

Ví dụ 2

Input

10 5
3 3 3 1 2 2 1 2 2 1
2 3
9 10
5 6
5 8
3 7

Output

Toni
Jakov
Toni
Toni
Toni

Nguồn

COCI 2025/2026 - Vòng 1, bài Zagi.

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