NOI Singapore 2026 - Vòng chung kết - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	NOI Singapore 2026 - Monkeys	100 (p)	1.0s	1G
2	NOI Singapore 2026 - Famished Cats	100 (p)	1.0s	1G
3	NOI Singapore 2026 - 3 Raptors	100 (p)	2.0s	1G
4	NOI Singapore 2026 - Gemstones	100 (p)	2.5s	1G
5	NOI Singapore 2026 - Lemon	100 (p)	5.0s	2G

1. NOI Singapore 2026 - Monkeys

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

Monkeyland là một trục số vô hạn có $n$ con khỉ, đánh số từ $1$ đến $n$. Ban đầu con thứ $i$ ở vị trí $p_i$; nhiều con có thể cùng vị trí.

Chuyển động của các con khỉ được xác định bởi chuỗi $d$ dài $n$:

nếu $d_i=$ L, con thứ $i$ dịch sang trái một đơn vị;
nếu $d_i=$ R, con thứ $i$ dịch sang phải một đơn vị.

Mỗi ngày Pan niệm phép đúng một lần. Hai con khỉ trở thành bạn nếu chúng từng ở cùng vị trí vào bất kỳ ngày nào, kể cả lúc ban đầu. Nếu Pan niệm phép trong $k$ ngày, hãy đếm số cặp khỉ trở thành bạn.

Dữ liệu vào

Dòng đầu chứa $n,k$.
Dòng thứ hai chứa $p_1,p_2,\ldots,p_n$.
Dòng thứ ba chứa chuỗi $d$ gồm $n$ ký tự.

Dữ liệu ra

In một số nguyên: số cặp khỉ trở thành bạn.

Giới hạn

\[ 1\le n\le200\,000,\quad 1\le k\le10^9,\quad 1\le p_i\le10^9 \]

Mỗi $d_i$ là L hoặc R.

Chấm điểm

Phần	Điểm	Giới hạn thêm
1	6	$n=2$
2	13	$d_1=d_2=\cdots=d_n$
3	10	$n,k\le200$
4	22	$n,k\le3000$
5	18	$n\le3000$
6	31	Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input

2 1
1 3
RL

Output

Note

Sau ngày đầu, cả hai con đều ở vị trí $2$ nên trở thành bạn.

Ví dụ 2

Input

5 67
1 2 3 4 5
RRRRR

Output

Note

Mọi con cùng đi sang phải và ban đầu ở các vị trí khác nhau, nên không cặp nào gặp nhau.

Ví dụ 3

Input

6 7
1 1 8 16 18 22
RRLRLL

Output

Ví dụ 4

Input

10 30
9 46 27 8 12 100 56 96 6 7
LRLRRLRRLR

Output

Ví dụ 5

Input

4 2
3 4 4 6
LLRL

Output

Note

Ban đầu khỉ $2$ và $3$ cùng ở vị trí $4$. Sau ngày đầu, khỉ $3$ và $4$ cùng ở vị trí $5$. Do đó có hai cặp bạn.

Hình 1: Trạng thái ban đầu của ví dụ 5, ở ngày $0$.

Hình 2: Trạng thái của ví dụ 5 sau ngày $1$.

Hình 3: Trạng thái của ví dụ 5 sau ngày $2$.

2. NOI Singapore 2026 - Famished Cats

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

Vương quốc mèo nằm dọc một con đường rất dài từ tây sang đông. Ngân hàng thức ăn ở đầu phía tây. Có $n$ ngôi nhà mèo về phía đông, đánh số từ $1$ đến $n$; $n$ là số chẵn. Nhà $1$ cách ngân hàng $d_1$ km. Với $i\ge2$, nhà $i$ cách nhà $i-1$ một đoạn $d_i$ km.

Hình 1: Ngân hàng thức ăn và các nhà mèo theo thứ tự từ tây sang đông; $d_i$ là khoảng cách đến vị trí liền trước.

Ket lái xe tải giao thức ăn từ ngân hàng với $x$ đơn vị nhiên liệu. Một đơn vị nhiên liệu cho phép đi $1$ km. Nhà $i$ có $f_i$ đơn vị nhiên liệu mà xe có thể lấy. Xe chứa nhiên liệu không giới hạn, chỉ dừng khi hết nhiên liệu và không cần quay về.

Ket có thể dùng đũa phép để hoán đổi lượng nhiên liệu ở nhà $i$ và nhà $n-i+1$. Chỉ được hoán đổi khi nhiên liệu ở cả hai nhà chưa được sử dụng.

Hãy tìm chỉ số xa nhất $D$ của ngôi nhà Ket có thể tới sau một số bất kỳ phép hoán đổi, đồng thời tìm số phép hoán đổi nhỏ nhất $S$ cần để tới được nhà $D$.

Dữ liệu vào

Dòng đầu chứa $n,x$.
Dòng thứ hai chứa $d_1,d_2,\ldots,d_n$.
Dòng thứ ba chứa $f_1,f_2,\ldots,f_n$.

Dữ liệu ra

In hai số nguyên $D$ và $S$.

Giới hạn

\[ 2\le n\le500\,000,\quad n\text{ chẵn},\quad d_1\le x\le10^9 \]

\[ 1\le d_i,f_i\le10^9 \]

Chấm điểm

Phần	Điểm	Giới hạn thêm
1	7	Tồn tại hằng số $k$ sao cho $
2	12	$n\le40$
3	14	$f_i\le f_{i+1}$ với mọi $1\le i<n$
4	19	$D\le n/2$
5	21	$n\le5000$
6	27	Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input

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

Output

5 1

Note

Ket tới nhà $1$, lấy nhiên liệu rồi tới nhà $2$. Hoán đổi nhiên liệu ở nhà $2$ và $5$ giúp xe lần lượt tới nhà $3$, $4$, $5$. Xe còn $4$ đơn vị nhưng cần $6$ để tới nhà $6$, nên $D=5$ và số hoán đổi nhỏ nhất là $S=1$.

Hình 2: Khoảng cách, nhiên liệu ban đầu và hành trình trong ví dụ 1.

Ví dụ 2

Input

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

Output

6 1

Ví dụ 3

Input

6 2
2 24 25 40 5 11
4 12 14 16 20 30

Output

3 2

Ví dụ 4

Input

6 10
3 6 3 7 8 6
4 3 1 7 1 6

Output

5 1

3. NOI Singapore 2026 - 3 Raptors

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

Có $n$ con khủng long xếp thành một hàng từ trái sang phải, đánh số từ $1$ đến $n$. Con thứ $i$ có màu $c_i\in\{1,2,3\}$.

WhiteRaptor được phép bỏ một số con (có thể bằng $0$) ở đầu trái và đầu phải, rồi giữ lại toàn bộ đoạn liên tiếp còn lại.

Trong đoạn được giữ, xét tần suất của cả ba màu. Nếu một màu không xuất hiện thì tần suất của nó bằng $0$. WhiteRaptor yêu cầu hiệu giữa tần suất lớn nhất và nhỏ nhất không vượt quá $k$.

Hãy tìm số khủng long lớn nhất có thể giữ lại. Được phép giữ đoạn rỗng.

Dữ liệu vào

Dòng đầu chứa $n,k$.
Dòng thứ hai chứa $c_1,c_2,\ldots,c_n$.

Dữ liệu ra

In số lượng lớn nhất có thể giữ.

Giới hạn

\[ 1\le n\le200\,000,\quad 0\le k\le200\,000,\quad 1\le c_i\le3 \]

Chấm điểm

Phần	Điểm	Giới hạn thêm
1	5	$n\le500$
2	9	$n\le2000$
3	11	$c_i\le2$
4	15	$k=0$
5	16	Tồn tại $1\le j\le n$ sao cho $c_i\ne3$ với mọi $i\le j$, và $c_i=3$ với mọi $i>j$
6	20	Trong mọi đoạn liên tiếp gồm ít nhất $3$ con, màu $3$ có tần suất nhỏ nhất
7	24	Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input

11 2
2 2 1 2 1 3 2 1 2 1 1

Output

Đoạn từ vị trí $3$ đến $9$ có tần suất các màu $1,2,3$ lần lượt là $3,3,1$, nên hiệu bằng $2$. Không có đoạn hợp lệ dài hơn.

Ví dụ 2

Input

6 2
2 1 3 3 3 3

Output

Có thể giữ đoạn từ vị trí $1$ đến $5$.

Ví dụ 3

Input

7 0
1 2 1 2 1 2 1

Output

Mọi đoạn không rỗng đều không chứa màu $3$, nên tần suất nhỏ nhất là $0$ và không thể có ba tần suất bằng nhau. Ví dụ này thỏa phần $5$ khi chọn $j=n$.

4. NOI Singapore 2026 - Gemstones

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

Có $n$ viên đá quý xếp thành một hàng, đánh số từ $1$ đến $n$. Viên thứ $i$ có màu $c_i$.

Trong một thao tác, bạn chọn hai viên kề nhau và cùng màu rồi xóa cả hai. Các viên ở hai phía trượt lại để lấp khoảng trống, có thể tạo ra những cặp kề nhau mới.

Có $q$ kịch bản độc lập. Trong kịch bản thứ $j$, chỉ xét đoạn đá từ $l_j$ đến $r_j$. Nếu thực hiện tối ưu các thao tác, hãy tìm số viên nhỏ nhất còn lại.

Dữ liệu vào

Dòng đầu chứa $n,q$.
Dòng thứ hai chứa $c_1,c_2,\ldots,c_n$.
$q$ dòng tiếp theo, dòng thứ $j$ chứa $l_j,r_j$.

Dữ liệu ra

In $q$ dòng; dòng thứ $j$ là đáp án của kịch bản thứ $j$.

Giới hạn

\[ 1\le n\le10^6,\quad 1\le q\le500\,000,\quad 1\le c_i\le10^9 \]

\[ 1\le l_j\le r_j\le n \]

Chấm điểm

Phần	Điểm	Giới hạn thêm
1	2	$c_1=c_2=\cdots=c_n$
2	5	Các viên cùng màu tạo thành một đoạn liên tiếp
3	9	$n,q\le2000$
4	4	$l_j=1$ với mọi truy vấn
5	8	Mỗi màu xuất hiện đúng hai lần
6	16	$c_i\le2$
7	18	$n,q\le100\,000$
8	15	$n,q\le300\,000$
9	23	Không có giới hạn thêm

Ví dụ

Ví dụ 1

Input

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

Output

Note

Trong truy vấn đầu, xóa hai trong ba viên màu $3$ và còn lại một viên. Truy vấn thứ hai có thể xóa hết. Truy vấn thứ ba còn tối thiểu một viên. Trong truy vấn cuối không thể thực hiện thao tác nào.

Hình 1: Dãy đá quý ban đầu của ví dụ 1.

Hình 2: Xóa một cặp đá kề nhau cùng màu.

Hình 3: Sau lần xóa đầu, một cặp cùng màu mới trở nên kề nhau và có thể bị xóa tiếp.

Ví dụ 2

Input

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

Output

2
0
0

5. NOI Singapore 2026 - Lemon

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

Đây là bài tương tác hai tiến trình. Chỉ các ngôn ngữ C++ tương thích chữ ký được hỗ trợ. Không đọc từ đầu vào chuẩn và không ghi ra đầu ra chuẩn.

Có $n$ loại trái cây mang nhãn đôi một khác nhau từ $1$ đến $n$. Đúng một quả là chanh; Takina và Chisato chưa biết nhãn của nó. Takina nhận lần lượt cả $n$ quả và phải truyền nhãn quả chanh cho Chisato, người không quan sát quá trình này.

Trước khi nhận trái cây, Takina biết mảng hoán vị $p$: quả thứ $i$ được đưa tới có nhãn $p_i$. Takina viết một chuỗi nhị phân $b$ dài không quá $5000$ (có thể rỗng). Gọi $x=|b|$.

Khi nhận từng quả, Takina được biết nó có phải chanh hay không. Nếu không phải chanh, cô có thể quyết định ăn hoặc không ăn ngay lúc đó; quyết định không thể thay đổi. Nếu là chanh, cô không được ăn. Gọi $y$ là tổng số quả đã ăn.

Cuối cùng Chisato nhận chuỗi $b$ và danh sách tăng dần nhãn của các quả không bị ăn. Từ đó cô phải xác định nhãn quả chanh. Có $t$ ván trong mỗi test.

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

Bạn phải cài đặt ba hàm sau trong tệp lời giải.

C++

std::string init(int subtask, int n, std::vector<int> p);

subtask: chỉ số phần chấm của test.
n: số trái cây.
p: vector dài $n+1$, với $p[0]=0$ và $p[i]$ là nhãn quả thứ $i$ được đưa tới.
Hàm được gọi một lần ở đầu mỗi ván và phải trả về chuỗi nhị phân $b$ dài từ $0$ đến $5000$.

C++

bool receive_fruit(int id, bool is_lemon);

id: nhãn quả vừa được đưa tới.
is_lemon: true khi quả đó là chanh.
Hàm được gọi $n$ lần trong mỗi ván.
Trả về true nếu Takina ăn quả, false nếu không. Trả về true khi is_lemon=true sẽ bị Wrong Answer.

C++

int answer(int subtask, int n, std::string b,
           std::vector<int> uneaten);

b: chuỗi do init trả về.
uneaten: vector tăng dần dài $n-y+1$, trong đó uneaten[0]=0, các phần tử sau là nhãn những quả không bị ăn.
Hàm được gọi một lần cuối mỗi ván và phải trả về nhãn quả chanh.

Trình chấm chạy lời giải hai lượt:

Lượt đầu gọi init, rồi gọi receive_fruit theo thứ tự $p$ trong từng ván. Lời giải được giữ trạng thái giữa các lần gọi.
Lượt hai có thể đổi thứ tự các ván và chỉ gọi answer. Ngoài các tham số của answer, chương trình không được truy cập thông tin từ lượt đầu.

Các hàm được gọi nhiều lần, vì vậy phải xử lý đúng trạng thái còn lại từ ván trước.

Giới hạn

\[ 1\le t\le10\,000,\qquad n=500 \]

$p$ là hoán vị của $1,2,\ldots,n$ và mỗi ván có đúng một quả chanh.

Điểm của mỗi test dùng giá trị $x$ lớn nhất và $y$ lớn nhất trong tất cả $t$ ván của test đó.

Chấm điểm

Phần	Điểm tối đa	Công thức
1	10	Nếu $y>2$ thì $0$ điểm; ngược lại $10\min(288/x,1)$
2	30	Nếu $y>9$ thì $0$ điểm; ngược lại $30\min(30/x,1)$
3	60	$60\min(20/(x+y),1)$

Ví dụ tương tác

Xét một ván minh họa với $n=4$ (không thỏa giới hạn thật), $p=[0,3,1,4,2]$ và quả chanh có nhãn $4$:

Bước	Lời gọi	Giá trị trả về
1	`init(subtask, 4, [0,3,1,4,2])`	`"101"`
2	`receive_fruit(3, false)`	`true`
3	`receive_fruit(1, false)`	`false`
4	`receive_fruit(4, true)`	`false`
5	`receive_fruit(2, false)`	`true`
6	`answer(subtask, 4, "101", [0,1,4])`	`4`

Takina ăn các quả nhãn $3$ và $2$, nên uneaten=[0,1,4]. Chiến lược xác định đúng nhãn $4$ với $x=3,y=2$.

Tệp đính kèm cung cấp lemon.h, lời giải mẫu khung, trình chấm mẫu và hai dữ liệu mẫu để kiểm thử cục bộ. Trình chấm mẫu chỉ chạy một lượt và không đổi thứ tự ván, khác với trình chấm chính thức.

Phần	Điểm	Giới hạn thêm
1	6	\(n=2\)
2	13	\(d_1=d_2=\cdots=d_n\)
3	10	\(n,k\le200\)
4	22	\(n,k\le3000\)
5	18	\(n\le3000\)
6	31	Không có giới hạn thêm

Phần	Điểm	Giới hạn thêm
1	7	Tồn tại hằng số \(k\) sao cho $
2	12	\(n\le40\)
3	14	\(f_i\le f_{i+1}\) với mọi \(1\le i<n\)
4	19	\(D\le n/2\)
5	21	\(n\le5000\)
6	27	Không có giới hạn thêm

Phần	Điểm	Giới hạn thêm
1	5	\(n\le500\)
2	9	\(n\le2000\)
3	11	\(c_i\le2\)
4	15	\(k=0\)
5	16	Tồn tại \(1\le j\le n\) sao cho \(c_i\ne3\) với mọi \(i\le j\), và \(c_i=3\) với mọi \(i>j\)
6	20	Trong mọi đoạn liên tiếp gồm ít nhất \(3\) con, màu \(3\) có tần suất nhỏ nhất
7	24	Không có giới hạn thêm

Phần	Điểm	Giới hạn thêm
1	2	\(c_1=c_2=\cdots=c_n\)
2	5	Các viên cùng màu tạo thành một đoạn liên tiếp
3	9	\(n,q\le2000\)
4	4	\(l_j=1\) với mọi truy vấn
5	8	Mỗi màu xuất hiện đúng hai lần
6	16	\(c_i\le2\)
7	18	\(n,q\le100\,000\)
8	15	\(n,q\le300\,000\)
9	23	Không có giới hạn thêm

Phần	Điểm tối đa	Công thức
1	10	Nếu \(y>2\) thì \(0\) điểm; ngược lại \(10\min(288/x,1)\)
2	30	Nếu \(y>9\) thì \(0\) điểm; ngược lại \(30\min(30/x,1)\)
3	60	\(60\min(20/(x+y),1)\)