JOI 2026 - Vòng loại 2 - 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	JOI 2026 - Class Division	100 (p)	2.0s	1G
2	JOI 2026 - Ultimate Dango Maker	100 (p)	2.0s	1G
3	JOI 2026 - JOI Eliminator	100 (p)	2.0s	1G
4	JOI 2026 - Shopping 3	100 (p)	2.0s	1G
5	JOI 2026 - Bitaro's Travel 3	100 (p)	2.0s	1G
6	JOI 2026 - Cesenatico	100 (p)	2.0s	1G

1. JOI 2026 - Class Division

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

Có \(N\) học sinh lớp 10 của trường JOI, được đánh số từ \(1\) đến \(N\). Điểm thi của học sinh \(i\) là \(A_i\) và không phải tất cả điểm đều bằng nhau.

Dựa trên kết quả kỳ thi này, nhà trường chia lớp cho năm học tiếp theo. Chọn một số nguyên \(x\): học sinh có điểm ít nhất \(x\) vào lớp nâng cao, các học sinh còn lại vào lớp thường. Mỗi lớp phải có ít nhất một học sinh. Cách chia được chọn sao cho chênh lệch số học sinh giữa hai lớp là nhỏ nhất; nếu vẫn có nhiều cách, chọn cách có ít học sinh lớp nâng cao hơn.

Hãy tìm điểm thấp nhất trong lớp nâng cao của cách chia được chọn.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1, A_2, \ldots, A_N\).

Dữ liệu ra

In điểm thấp nhất của một học sinh trong lớp nâng cao.

Ràng buộc

\(2 \le N \le 500000\).
\(1 \le A_i \le 10^9\).
Tồn tại \(i < j\) sao cho \(A_i \ne A_j\).
Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

\(20\) điểm: \(N = 3\).
\(20\) điểm: mỗi \(A_i\) thuộc \(\{500, 800, 1000\}\).
\(20\) điểm: các \(A_i\) đôi một khác nhau.
\(40\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

3
1000 500 800

Output

Giải thích

Chẳng hạn, chọn \(x=900\) thì học sinh \(1\) vào lớp nâng cao, còn học sinh \(2,3\) vào lớp thường. Cách chia còn lại là cho học sinh \(1,3\) vào lớp nâng cao và học sinh \(2\) vào lớp thường, có thể thực hiện bằng cách chọn \(x=800\). Cả hai cách đều có chênh lệch sĩ số bằng \(1\), nên chọn cách thứ nhất vì lớp nâng cao có ít học sinh hơn. Điểm thấp nhất của lớp này là \(1000\).

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(4\).

Ví dụ 2

Input

6
100 75 41 75 13 89

Output

Giải thích

Chọn \(x=89\) thì học sinh \(1,6\) vào lớp nâng cao, còn học sinh \(2,3,4,5\) vào lớp thường. Điểm thấp nhất của lớp nâng cao là \(89\).

Ví dụ này thỏa mãn các nhóm \(4\).

Ví dụ 3

Input

6
20 25 12 7 13 16

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(3\), \(4\).

Ví dụ 4

Input

8
364353982 103422534 437367896 91518637 364353982 221490368 437367896 103422534

Output

364353982

Giải thích

Ví dụ này thỏa mãn các nhóm \(4\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Class Division.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

2. JOI 2026 - Ultimate Dango Maker

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

JOI-kun là một người làm bánh dango. Cậu có \(A_i\) chiếc bánh dango màu \(i\), với \(1 \le i \le N\). Một xiên dango dùng đúng ba chiếc bánh. Nếu màu của ba chiếc là \(c_1,c_2,c_3\), mọi hiệu tuyệt đối giữa hai màu phải không vượt quá \(1\).

Mỗi chiếc bánh chỉ được dùng cho nhiều nhất một xiên. Hãy tìm số xiên dango lớn nhất có thể tạo.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1, A_2, \ldots, A_N\).

Dữ liệu ra

In số xiên dango lớn nhất có thể tạo.

Ràng buộc

\(1 \le N \le 200000\).
\(0 \le A_i \le 10^9\).
Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

\(6\) điểm: \(N=1\).
\(9\) điểm: \(N \le 2\).
\(10\) điểm: mọi \(A_i\) chia hết cho \(3\).
\(17\) điểm: mọi \(A_i=2\).
\(21\) điểm: mọi \(A_i \le 3\).
\(37\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

3
3 1 2

Output

Giải thích

Có thể làm một xiên bằng ba chiếc bánh màu \(1\), và một xiên bằng một chiếc bánh màu \(2\) cùng hai chiếc bánh màu \(3\). Xiên thứ nhất hợp lệ vì \(|1-1|=0\le1\); xiên thứ hai hợp lệ vì \(|2-3|\le1\) và \(|3-3|\le1\). Không thể làm hơn hai xiên, nên in \(2\).

Ví dụ này thỏa mãn các nhóm \(5\), \(6\).

Ví dụ 2

Input

1
99

Output

Giải thích

Có thể làm \(33\) xiên, mỗi xiên gồm ba chiếc bánh màu \(1\). Không thể làm nhiều hơn, nên in \(33\).

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(6\).

Ví dụ 3

Input

2
5 6

Output

Giải thích

Có thể làm một xiên gồm ba chiếc bánh màu \(1\), một xiên gồm hai chiếc bánh màu \(1\) và một chiếc bánh màu \(2\), cùng một xiên gồm ba chiếc bánh màu \(2\). Tổng cộng có ba xiên và không thể làm nhiều hơn, nên in \(3\).

Ví dụ này thỏa mãn các nhóm \(2\), \(6\).

Ví dụ 4

Input

6
0 2 2 3 1 2

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(5\), \(6\).

Ví dụ 5

Input

1
0

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(5\), \(6\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Ultimate Dango Maker.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

3. JOI 2026 - JOI Eliminator

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

Cho chuỗi \(S\) độ dài \(N\) chỉ gồm các ký tự J, O, I. JOI-kun lặp lại thao tác sau cho đến khi không thể thực hiện: chọn một đoạn liên tiếp JOI và thay bằng OIJ.

Có thể chứng minh thao tác luôn kết thúc và chuỗi cuối cùng không phụ thuộc vào thứ tự chọn đoạn. Hãy in chuỗi cuối cùng.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa chuỗi \(S\).

Dữ liệu ra

In chuỗi sau khi không còn thao tác nào thực hiện được.

Ràng buộc

\(3 \le N \le 500000\).
\(S\) chỉ gồm J, O, I và có độ dài \(N\).
Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

\(14\) điểm: \(N \le 100\).
\(27\) điểm: \(N\) chia hết cho \(3\) và \(S\) là JOI lặp lại \(N/3\) lần.
\(29\) điểm: tồn tại \(2 \le k \le N\) sao cho \(k\) ký tự đầu là J và phần còn lại không chứa J.
\(30\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

6
JOIJOI

Output

OIOIJJ

Giải thích

Một cách thực hiện là:

Ban đầu, \(S=\) JOIJOI.
Thao tác trên các vị trí \(1\) đến \(3\), thu được OIJJOI.
Thao tác trên các vị trí \(4\) đến \(6\), thu được OIJOIJ.
Thao tác trên các vị trí \(3\) đến \(5\), thu được OIOIJJ.

Không thể tiếp tục thao tác, nên in OIOIJJ.

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(4\).

Ví dụ 2

Input

8
JJJOIOIO

Output

OIOIJJJO

Giải thích

Ví dụ này thỏa mãn các nhóm \(1\), \(3\), \(4\).

Ví dụ 3

Input

20
JJOIJOIJOOIJOIIJJOIO

Output

OIOIJJJJOOIOIJIOIJJO

Giải thích

Ví dụ này thỏa mãn các nhóm \(1\), \(4\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài JOI Eliminator.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

4. JOI 2026 - Shopping 3

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

Cửa hàng JOI có \(N\) mặt hàng, đánh số từ \(1\) đến \(N\); mặt hàng \(i\) có giá niêm yết \(A_i\). Khi mua hàng qua Internet, khách có thể sử dụng phiếu giảm giá. Có \(Q\) loại phiếu, đánh số từ \(1\) đến \(Q\). Với phiếu loại \(j\), nếu dùng \(k\) phiếu, với \(k\) là một số nguyên không âm, cùng áp dụng cho tất cả mặt hàng thì giá mỗi mặt hàng \(i\) trở thành \(\max(0,A_i-D_jk)\), đồng thời trả thêm một khoản phí chung \(C_jk\) cho cả lần mua hàng, không phải cho từng mặt hàng.

Trong mỗi truy vấn \(j\), chỉ được dùng phiếu loại \(j\) với số lượng tùy ý để mua mỗi mặt hàng một lần. Hãy tìm tổng tiền nhỏ nhất cho từng truy vấn.

Dữ liệu vào

Dòng đầu chứa \(N,Q\). Dòng thứ hai chứa \(A_1,\ldots,A_N\). \(Q\) dòng tiếp theo, dòng \(j\) chứa \(C_j,D_j\).

Dữ liệu ra

In \(Q\) dòng; dòng \(j\) là đáp án của truy vấn \(j\).

Ràng buộc

\(1 \le N,Q \le 300000\).
\(1 \le A_i,C_j,D_j \le 10^9\).
Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

\(6\) điểm: \(N=1\), \(Q \le 3000\).
\(3\) điểm: \(N,Q \le100\), \(A_i\le100\).
\(8\) điểm: \(N,Q\le3000\), mọi \(D_j=1\).
\(22\) điểm: \(N,Q\le3000\).
\(15\) điểm: mọi \(D_j=1\).
\(18\) điểm: mọi \(A_i\le1000000\).
\(28\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Với truy vấn \(1\), dùng một phiếu loại \(1\) làm giá các mặt hàng thành \(3,5,0\). Tổng tiền là \(3+5+0+12\times1=20\). Không thể trả ít hơn \(20\).

Với truy vấn \(2\), dùng bốn phiếu loại \(2\) làm giá các mặt hàng thành \(0,2,0\). Tổng tiền là \(0+2+0+3\times4=14\). Không thể trả ít hơn \(14\).

Với truy vấn \(3\), dùng hai phiếu loại \(3\) làm giá các mặt hàng thành \(0,2,0\). Tổng tiền là \(0+2+0+3\times2=8\). Không thể trả ít hơn \(8\).

Với truy vấn \(4\), không dùng phiếu nào, giá các mặt hàng là \(8,10,3\) và tổng tiền là \(8+10+3+100\times0=21\). Không thể trả ít hơn \(21\). Vì thế lần lượt in \(20,14,8,21\).

Ví dụ này thỏa mãn các nhóm \(2\), \(4\), \(6\), \(7\).

Ví dụ 2

Input

Output

34
67
83

Giải thích

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(4\), \(6\), \(7\).

Ví dụ 3

Input

15 3
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
1 1
10 1
20 1

Output

9
67
77

Giải thích

Ví dụ này thỏa mãn các nhóm \(2\), \(3\), \(4\), \(5\), \(6\), \(7\).

Ví dụ 4

Input

6 3
1000000000 999999999 999999998 999999997 999999996 999999995
1000000000 1
1 1000000000
900000000 900000000

Output

5999999985
1
1499999985

Giải thích

Ví dụ này thỏa mãn các nhóm \(4\), \(7\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Shopping 3.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

5. JOI 2026 - Bitaro's Travel 3

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

JOI có đồ thị vô hướng đơn với \(N\) thành phố và \(M\) con đường. Bitaro bắt đầu tại thành phố \(s\). Một hành trình có độ dài ít nhất \(1\), có thể đi qua một thành phố nhiều lần, và được biểu diễn bằng dãy thành phố \(v_1,v_2,\ldots,v_l\) sao cho \(v_1=s\), hai thành phố liên tiếp có cạnh nối, và các bước đi luân phiên tăng rồi giảm theo nhãn: ở bước lẻ \(v_j<v_{j+1}\), ở bước chẵn \(v_j>v_{j+1}\).

Ví dụ, \((2)\) và \((1,4,1,5,3)\) thỏa mãn điều kiện luân phiên tăng giảm, còn \((3,2)\) thì không.

Với từng \(s=1,2,\ldots,N\), hãy đếm số thành phố không xuất hiện trong bất kỳ hành trình hợp lệ nào bắt đầu tại \(s\).

Dữ liệu vào

Dòng đầu chứa \(N,M\). \(M\) dòng tiếp theo chứa \(A_i,B_i\), mô tả một cạnh với \(A_i<B_i\).

Dữ liệu ra

In \(N\) dòng. Dòng \(s\) là số thành phố không thể đến được khi bắt đầu tại \(s\).

Ràng buộc

\(1 \le N \le 300000\) và \(0 \le M \le 300000\).
\(1 \le A_i<B_i\le N\).
Không có cạnh trùng nhau.
Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

\(12\) điểm: \(N\le1000\), đồ thị có \(M=N-1\) cạnh và tồn tại một hoán vị \(P\) của \(1,2,\ldots,N\) sao cho có cạnh nối \(P_i\) với \(P_{i+1}\) với mọi \(1\le i<N\).
\(19\) điểm: \(N,M\le1000\).
\(15\) điểm: đồ thị có \(M=N-1\) cạnh và tồn tại một hoán vị \(P\) của \(1,2,\ldots,N\) sao cho có cạnh nối \(P_i\) với \(P_{i+1}\) với mọi \(1\le i<N\).
\(17\) điểm: mọi đỉnh có bậc không quá \(2\).
\(37\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Khi \(s=1\), một số hành trình hợp lệ là \((1)\), \((1,2)\), \((1,3)\), \((1,4,1)\) và \((1,4,1,2)\). Không có thành phố nào không thể đến.

Khi \(s=2\), hành trình hợp lệ duy nhất là \((2)\); không thể đến các thành phố \(1,3,4\).

Khi \(s=3\), có thể chọn \((3)\) hoặc \((3,4,1,2)\), nên không có thành phố nào không thể đến.

Khi \(s=4\), hành trình hợp lệ duy nhất là \((4)\); không thể đến các thành phố \(1,2,3\).

Ví dụ này thỏa mãn các nhóm \(2\), \(5\).

Ví dụ 2

Input

2 0

Output

1
1

Giải thích

Khi \(s=1\), hành trình hợp lệ duy nhất là \((1)\), nên không thể đến thành phố \(2\). Khi \(s=2\), hành trình hợp lệ duy nhất là \((2)\), nên không thể đến thành phố \(1\).

Ví dụ này thỏa mãn các nhóm \(2\), \(4\), \(5\).

Ví dụ 3

Input

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(4\), \(5\).

Ví dụ 4

Input

Output

Giải thích

Ví dụ này thỏa mãn các nhóm \(2\), \(4\), \(5\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Bitaro's Travel 3.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

6. JOI 2026 - Cesenatico

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

Cesenatico là một thành phố cảng của Ý bên bờ biển Adriatic, nổi tiếng với con kênh có nhiều thuyền neo đậu. Xét mô hình đơn giản sau: con kênh thẳng và chỉ một đầu thông ra biển. Trên kênh có \(N\) thuyền được đánh số từ \(1\) đến \(N\), ở các khoảng cách tăng dần \(A_1<A_2<\cdots<A_N\) tính từ biển. Để chuẩn bị cho lễ hội của thị trấn, bạn sơn mỗi thuyền bằng một trong \(N\) màu được đánh số từ \(1\) đến \(N\) sao cho không màu nào xuất hiện đúng một lần; một màu có thể không được dùng. Với mỗi màu xuất hiện ít nhất hai lần, dãy khoảng cách từ biển đến các thuyền mang màu đó, sau khi sắp xếp tăng dần, phải là một cấp số cộng.

Khoảng cách giữa hai thuyền phân biệt \(i,j\) là \(|A_i-A_j|\). Độ đẹp là khoảng cách nhỏ nhất giữa hai thuyền phân biệt cùng màu. Hãy tìm độ đẹp lớn nhất có thể, hoặc xác định không có cách tô hợp lệ.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

In -1 nếu không có cách tô hợp lệ; ngược lại in độ đẹp lớn nhất.

Ràng buộc

\(2 \le N \le 3500\).
\(1 \le A_i\le10^9\).
\(A_i<A_{i+1}\).
Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

\(8\) điểm: \(A_i=i\).
\(11\) điểm: \(N\le7\).
\(12\) điểm: \(N\le100\).
\(39\) điểm: \(N\le700\).
\(30\) điểm: không có ràng buộc thêm.

Ví dụ

Ví dụ 1

Input

2
1 2

Output

Giải thích

Nếu sơn thuyền \(1\) bằng màu \(1\) và thuyền \(2\) bằng màu \(2\), cách sơn không hợp lệ vì có màu xuất hiện đúng một lần.

Một cách hợp lệ là sơn cả hai thuyền bằng màu \(2\). Màu \(1\) không được dùng nên thỏa mãn điều kiện; các khoảng cách của thuyền màu \(2\) tạo thành cấp số cộng \((1,2)\). Cặp thuyền cùng màu duy nhất có khoảng cách \(|A_1-A_2|=|1-2|=1\), nên độ đẹp là \(1\). Không thể đạt độ đẹp từ \(2\) trở lên, nên in \(1\).

Ví dụ này thỏa mãn các nhóm \(1\), \(2\), \(3\), \(4\), \(5\).

Ví dụ 2

Input

3
1 10 100

Output

-1

Giải thích

Để không có màu nào xuất hiện đúng một lần, cả ba thuyền phải được sơn cùng màu. Tuy nhiên, dãy khoảng cách \((1,10,100)\) không phải cấp số cộng. Vì thế không có cách sơn hợp lệ và phải in -1.

Ví dụ này thỏa mãn các nhóm \(2\), \(3\), \(4\), \(5\).

Ví dụ 3

Input

5
5 6 8 9 11

Output

Giải thích

Có thể sơn thuyền \(1,3,5\) bằng màu \(1\), và thuyền \(2,4\) bằng màu \(4\). Bốn cặp thuyền cùng màu là \((1,3)\), \((1,5)\), \((2,4)\), \((3,5)\), có khoảng cách lần lượt \(3,6,3,3\). Độ đẹp là \(3\). Không thể đạt độ đẹp từ \(4\) trở lên, nên in \(3\).

Ví dụ này thỏa mãn các nhóm \(2\), \(3\), \(4\), \(5\).

Nguồn

JOI 2025/2026 - Vòng loại 2, bài Ship.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.