KOI TST 2026 - Vòng 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	KOI TST 2026 - All Kinds of Sauce	100 (p)	3.0s	2G
2	KOI TST 2026 - Sorting	100 (p)	5.0s	2G
3	KOI TST 2026 - Flying Squirrel 2	100 (p)	5.0s	2G
4	KOI TST 2026 - Observation Tower	100 (p)	6.0s	2G

1. KOI TST 2026 - All Kinds of Sauce

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

Đề bài

Có $N$ nguyên liệu, đánh số từ $0$ đến $N-1$. Đầu bếp có thể làm một tập $X$ các loại sốt. Mỗi loại sốt $S\in X$ dùng đúng $2$ hoặc $3$ nguyên liệu, tức là $S\subseteq\{0,1,\ldots,N-1\}$ và $|S|\in\{2,3\}$. Hai loại sốt khác nhau không có cùng tập nguyên liệu.

Bạn cần xác định $|X|$. Tập $X$ không được cung cấp trực tiếp; thay vào đó, bạn có thể thực hiện các phép thử mù. Trong một phép thử, bạn chọn một tập nguyên liệu $Y$ thỏa mãn

\[ |Y|\le \left\lceil\frac N2\right\rceil+1. \]

Grader trả về

\[ f(Y)=|\{S\in X\mid S\subseteq Y\}|. \]

Mục tiêu là tìm chính xác $|X|$ với ít phép thử nhất.

Yêu cầu cài đặt

C++

int solve(int N);
int query(vector<int> Y);

solve(N) được gọi đúng một lần và phải trả về $|X|$.
Trong solve, bạn có thể gọi query(Y). Các phần tử của Y phải phân biệt, nằm trong $[0,N-1]$, và kích thước không vượt quá $\lceil N/2\rceil+1$.
query trả về $f(Y)$ và được gọi nhiều nhất $3\,000$ lần trong một test.
Chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

$6\le N\le 1\,000$.
$1\le |X|\le 50\,000$.
Mọi $S\in X$ có $|S|\in\{2,3\}$.
Grader không thích nghi: $X$ được cố định trước khi solve được gọi.

Phân nhóm

Nhóm	Điểm	Ràng buộc bổ sung
1	11	$N\le 500$; các tập trong $X$ đôi một rời nhau; mọi $S\in X$ có $
2	32	$N\le 500$; các tập trong $X$ đôi một rời nhau.
3	25	Mọi $S\in X$ có $
4	32	Không có ràng buộc bổ sung.

Nếu chương trình trả lời sai ở bất kỳ test nào của một nhóm, điểm của nhóm đó là $0$. Nếu mọi test đều đúng, gọi $Q$ là số lần gọi query lớn nhất trong nhóm:

Nhóm 1 và 2 nhận toàn bộ điểm nếu $Q\le 3\,000$.
Với nhóm 3 và 4, nếu $Q\le 41$ thì nhận toàn bộ điểm. Nếu $41<Q\le 3\,000$, điểm nhóm được nhân với

\[ 0.5+\frac{41}{2Q}. \]

Grader mẫu

Grader mẫu đọc $N$, số $K=|X|$, rồi $K$ dòng mô tả từng loại sốt dưới dạng L a[0] ... a[L-1]. Grader in giá trị solve trả về và số lần gọi query.

Ví dụ

Input

Output

2
3

Trong ví dụ, $X=\{\{0,1\},\{2,3,4\}\}$. Một cách hợp lệ là hỏi lần lượt các tập $\{0,1,2\}$, $\{2,3,4\}$ và $\{0,2,3,5\}$, nhận các kết quả $1,1,0$, rồi trả về $2$.

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 2, giấy phép CC BY-NC-SA 4.0.

2. KOI TST 2026 - Sorting

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

Đề bài

Alice có $N$ đồ vật, đánh số từ $0$ đến $N-1$. Giá trị của vật $i$ là một số nguyên không âm $A[i]$. Alice biết toàn bộ giá trị, còn Bob chỉ biết $N$ và biết rằng các giá trị không âm.

Bob cần trả về một hoán vị $P$ sao cho

\[ A[P[i]]\le A[P[i+1]]\qquad(0\le i<N-1). \]

Bob có thể hỏi Alice không quá $10\,000$ lần. Trong mỗi câu hỏi:

Bob nối các đồ vật bằng đúng $N-1$ sợi dây, mỗi dây nối hai đồ vật phân biệt, sao cho mọi cặp đồ vật đều liên thông qua các sợi dây. Nói cách khác, các dây tạo thành một cây.
Alice chọn một tập đồ vật độc lập trên cây: không có hai vật được chọn nối trực tiếp với nhau. Tổng giá trị các vật được chọn phải lớn nhất có thể.
Nếu có nhiều tập tối ưu, Alice tùy ý trả về một trong số đó. Sau đó các dây được tháo bỏ.

Hãy giúp Bob sắp xếp các đồ vật với ít câu hỏi nhất.

Yêu cầu cài đặt

C++

vector<int> sorting(int N);
vector<int> ask_question(vector<array<int, 2>> threads);

sorting(N) được gọi đúng một lần và phải trả về một hoán vị $P$ sắp theo giá trị không giảm. Nếu có nhiều đáp án, có thể trả về bất kỳ đáp án hợp lệ nào.
ask_question(threads) thực hiện một câu hỏi. threads phải chứa đúng $N-1$ cạnh và tạo thành một cây liên thông trên các đỉnh $0,\ldots,N-1$.
Hàm trả về mảng nhị phân $C$ độ dài $N$, với $C[i]=1$ khi Alice chọn vật $i$.
Cùng một mảng threads có thể nhận các đáp án tối ưu khác nhau ở những lần gọi khác nhau.
ask_question được gọi nhiều nhất $10\,000$ lần trong một test.
Chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

$5\le N\le 1\,000$.
$A[i]$ là số nguyên không âm và không có cận trên được công bố.
Grader có tính thích nghi: mảng $A$ không nhất thiết được cố định trước. Sau mỗi câu trả lời, luôn tồn tại ít nhất một mảng $A$ phù hợp với toàn bộ câu trả lời trước đó.
Có thể giả sử phần grader xử lý các câu hỏi trong không quá $2$ giây và dùng không quá $16$ MiB cho mỗi test, không tính tài nguyên của bài nộp.

Phân nhóm

Nhóm	Điểm	Ràng buộc bổ sung
1	7	$N=5$.
2	8	$N\le 100$.
3	10	Có nhiều nhất một chỉ số $i$ thỏa mãn $A[i]>0$.
4	30	$A[i]=0$ với mọi $0\le i<N/2$.
5	45	Không có ràng buộc bổ sung.

Ở nhóm 1 và 2, đáp án đúng nhận toàn bộ điểm nhóm. Ở nhóm 3, 4 và 5, bài sai hoặc kết thúc bất thường nhận $0$ điểm. Nếu đáp án đúng, gọi $Q_{\max}$ là số câu hỏi lớn nhất trong một lần chạy thuộc nhóm và xác định $X$ như sau:

\[ X= \begin{cases} 0, & Q_{\max}>10\,000,\\ 90-35\log_{10}\left(\dfrac{Q_{\max}}{80}\right), & 80<Q_{\max}\le 10\,000,\\ 170-Q_{\max}, & 70<Q_{\max}\le 80,\\ 100, & Q_{\max}\le 70. \end{cases} \]

Điểm nhận được bằng $X\%$ số điểm của nhóm.

Grader mẫu

Grader mẫu đọc $N$ và mảng $A$. Grader in hoán vị do sorting trả về trên dòng đầu và số lần gọi ask_question trên dòng thứ hai. Grader mẫu chỉ được đảm bảo hoạt động khi $0\le A[i]\le 10^9$ và có thể khác grader chính thức.

Ví dụ

Input

6
5 3 3 0 8 1

Output

3 5 1 2 0 4
2

Vì hai vật $1$ và $2$ có cùng giá trị, hoán vị 3 5 2 1 0 4 cũng hợp lệ.

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 2, giấy phép CC BY-NC-SA 4.0.

3. KOI TST 2026 - Flying Squirrel 2

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

Đề bài

Trên mặt phẳng có một sóc bay và $N$ cột thẳng đứng vô hạn, đánh số từ $0$ đến $N-1$. Chân cột $i$ ở $(i,0)$. Nếu $B[i]=0$, cột có màu đỏ; nếu $B[i]=1$, cột có màu xanh.

Ban đầu sóc ở $(0,0)$ và cần đến $(N,H)$. Khi không ở vị trí có cột, sóc bay sang phải và giữ nguyên độ cao, mất thời gian $0$. Tại cột $i$, sóc phải chọn một trong các hành động:

Bay qua cột, không đổi độ cao và mất thời gian $0$.
Nếu cột đỏ, trèo lên làm độ cao tăng $1$, mất $A[i]$ thời gian.
Nếu cột xanh, nhảy làm độ cao tăng $1$, mất $A[i]$ thời gian.

Khi đi qua vị trí ngang $i+0.5$, độ cao phải nằm trong đoạn $[L[i],R[i]]$. Khi đến vị trí ngang $N$, độ cao phải đúng bằng $H$.

Với mỗi $k=0,1,\ldots,H$, gọi $T[k]$ là thời gian nhỏ nhất của một hành trình hợp lệ dùng đúng $k$ lần nhảy trên cột xanh. Nếu không tồn tại hành trình như vậy, đặt $T[k]=-1$.

Hãy tìm $T[0],T[1],\ldots,T[H]$.

Yêu cầu cài đặt

C++

vector<long long> fly(
    int H,
    vector<int> A,
    vector<int> B,
    vector<int> L,
    vector<int> R
);

Các mảng có cùng độ dài $N$. Hàm phải trả về mảng $T$ có độ dài $H+1$, được gọi đúng một lần, và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

$1\le N\le 200\,000$.
$0\le H\le N$.
$0\le A[i]\le 10^9$.
$B[i]\in\{0,1\}$.
$0\le L[i]\le R[i]\le N$.

Phân nhóm

Nhóm	Điểm	Ràng buộc bổ sung
1	3	$N\le 300$.
2	4	$A[i]=B[i]=0$ với mọi $i$.
3	25	$B[i]=0$ với mọi $i$.
4	20	$N\le 65\,000$ và $A[i]\le 5$.
5	29	$N\le 65\,000$.
6	19	Không có ràng buộc bổ sung.

Grader mẫu

Grader mẫu đọc N H, sau đó lần lượt đọc bốn mảng $A,B,L,R$. Grader in $T[0],\ldots,T[H]$ trên một dòng.

Ví dụ 1

Input

Output

-1 20 14 -1

Note

Hình 1: Hành trình trong ví dụ 1 dùng một lần nhảy trên cột xanh và mất $20$ giây.

Ví dụ 2

Input

Output

1000000000 -1

Note

Hình 2: Hành trình trong ví dụ 2 dùng hai lần nhảy trên cột xanh và mất $14$ giây.

Ví dụ 3

Input

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

Output

7 -1 -1 -1

Ví dụ 4

Input

20 7
3 3 4 1 3 2 0 1 4 3 4 0 0 1 0 4 4 5 5 0
1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1
0 0 1 1 2 1 2 2 1 1 0 1 1 3 2 2 1 6 4 4
3 2 3 3 6 2 2 4 3 4 4 5 3 6 6 5 7 8 8 9

Output

-1 16 11 10 9 10 12 15

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 2, giấy phép CC BY-NC-SA 4.0.

4. KOI TST 2026 - Observation Tower

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

Đề bài

Có $N$ tháp quan sát, đánh số từ $0$ đến $N-1$. Tháp $i$ có chiều cao $H[i]$ và điểm quan sát $S[i]$, ban đầu $S[i]=0$.

Với $0\le i<j\le N-1$, tháp $j$ nhìn thấy được từ tháp $i$ nếu

\[ H[k]<H[j]\quad\text{với mọi }i\le k<j. \]

Các tháp có chỉ số không lớn hơn $i$ không nhìn thấy được từ tháp $i$. Khi quan sát từ một tháp, điểm $S[j]$ của mọi tháp nhìn thấy được tăng thêm $1$.

Có $Q$ sự kiện, mỗi sự kiện thuộc một trong ba loại và được biểu diễn bằng một mảng có độ dài tương ứng:

Quan sát [I]: quan sát từ tháp $I$, với $0\le I\le N-2$.
Đo đạc [L, R]: tính $S[L]+S[L+1]+\cdots+S[R]$.
Biến động địa chất [L, R, V]: cộng $V$ vào chiều cao của mọi tháp từ $L$ đến $R$.

Gọi $K$ là tổng số sự kiện đo đạc. Hãy trả về kết quả của $K$ lần đo theo đúng thứ tự xuất hiện.

Yêu cầu cài đặt

C++

vector<long long> tower_events(
    vector<int> H,
    vector<vector<int>> E
);

E[i] mô tả sự kiện thứ $i$ theo quy ước trên. Hàm phải trả về mảng $X$ độ dài $K$, trong đó $X[i]$ là kết quả lần đo thứ $i$. Hàm được gọi đúng một lần và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

$5\le N\le 1\,000\,000$.
$1\le Q\le 250\,000$.
$1\le H[i]\le 10^9$.
Sự kiện quan sát có $0\le I\le N-2$.
Sự kiện đo đạc và biến động có $0\le L\le R\le N-1$.
Sự kiện biến động có $-10^9\le V\le 10^9$.
Sau mỗi biến động, mọi chiều cao vẫn không nhỏ hơn $1$.
Có ít nhất một sự kiện đo đạc.

Phân nhóm

Nhóm	Điểm	Ràng buộc bổ sung
1	17	$N,Q\le 150\,000$; mọi lần đo có $L=0,R=N-1$.
2	6	$N,Q\le 150\,000$; không có biến động địa chất.
3	12	$N,Q\le 150\,000$.
4	19	Mọi lần quan sát có $I=0$; mọi biến động có $L=R$; có nhiều nhất $30\,000$ biến động.
5	21	Mọi lần đo có $L=R$; mọi biến động có $L=R$ và $V\ge 0$.
6	25	Không có ràng buộc bổ sung.

Grader mẫu

Grader mẫu đọc N Q, mảng $H$, rồi $Q$ dòng. Mỗi dòng bắt đầu bằng độ dài $|E[i]|$, tiếp theo là các phần tử của sự kiện. Mỗi kết quả đo được in trên một dòng.

Ví dụ 1

Input

Output

3
6

Ví dụ 2

Input

10 11
7 7 9 5 8 10 2 9 2 2
1 1
3 6 8 6
1 1
2 1 9
1 3
1 8
2 2 4
1 5
3 1 1 7
1 1
2 0 9

Output

5
3
10

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 2, giấy phép CC BY-NC-SA 4.0.

Nhóm	Điểm	Ràng buộc bổ sung
1	11	\(N\le 500\); các tập trong \(X\) đôi một rời nhau; mọi \(S\in X\) có $
2	32	\(N\le 500\); các tập trong \(X\) đôi một rời nhau.
3	25	Mọi \(S\in X\) có $
4	32	Không có ràng buộc bổ sung.

Nhóm	Điểm	Ràng buộc bổ sung
1	7	\(N=5\).
2	8	\(N\le 100\).
3	10	Có nhiều nhất một chỉ số \(i\) thỏa mãn \(A[i]>0\).
4	30	\(A[i]=0\) với mọi \(0\le i<N/2\).
5	45	Không có ràng buộc bổ sung.

Nhóm	Điểm	Ràng buộc bổ sung
1	3	\(N\le 300\).
2	4	\(A[i]=B[i]=0\) với mọi \(i\).
3	25	\(B[i]=0\) với mọi \(i\).
4	20	\(N\le 65\,000\) và \(A[i]\le 5\).
5	29	\(N\le 65\,000\).
6	19	Không có ràng buộc bổ sung.

Nhóm	Điểm	Ràng buộc bổ sung
1	17	\(N,Q\le 150\,000\); mọi lần đo có \(L=0,R=N-1\).
2	6	\(N,Q\le 150\,000\); không có biến động địa chất.
3	12	\(N,Q\le 150\,000\).
4	19	Mọi lần quan sát có \(I=0\); mọi biến động có \(L=R\); có nhiều nhất \(30\,000\) biến động.
5	21	Mọi lần đo có \(L=R\); mọi biến động có \(L=R\) và \(V\ge 0\).
6	25	Không có ràng buộc bổ sung.