SEATST 2026 - Ngày 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	SEATST 2026 - Triple Circuit	100 (p)	10.0s	512M
2	SEATST 2026 - Car Gathering	100 (p)	4.0s	512M
3	SEATST 2026 - Troublesome Trip	100 (p)	4.5s	1G

1. SEATST 2026 - Triple Circuit

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

Đây là bài chỉ xuất kết quả (output-only).

Khi cài đặt một mạch cho robot, bạn phát hiện một số bất thường. Robot có thể chạy $N=128$ chương trình, đánh số từ $0$ đến $N-1$. Bình thường, tại mỗi thời điểm chỉ có đúng một chương trình chạy. Tuy nhiên, đôi khi có đúng ba chương trình chạy đồng thời. Bạn cần xây dựng một mạch để phát hiện tình huống bất thường này.

Ban đầu có $N$ đầu vào. Đầu vào thứ $i$ bằng $0$ nếu chương trình thứ $i$ không chạy, và bằng $1$ nếu chương trình đó đang chạy. Sau đó, bạn thêm các cổng logic được đánh số liên tiếp bắt đầu từ $N$. Mỗi cổng nhận một hoặc hai đầu vào và tạo ra một giá trị $0$ hoặc $1$. Đầu vào của cổng có chỉ số $i$ có thể là một trong $N$ đầu vào ban đầu hoặc đầu ra của một cổng có chỉ số nhỏ hơn $i$.

Có ba loại cổng:

NOT: nhận đúng một đầu vào; đầu ra bằng $1$ khi đầu vào bằng $0$, và ngược lại.
OR: nhận đúng hai đầu vào; đầu ra bằng $0$ khi cả hai đầu vào đều bằng $0$, và bằng $1$ trong các trường hợp còn lại.
AND: nhận đúng hai đầu vào; đầu ra bằng $1$ khi cả hai đầu vào đều bằng $1$, và bằng $0$ trong các trường hợp còn lại.

Đầu ra của cổng cuối cùng phải bằng $1$ nếu có đúng ba trong $N$ đầu vào ban đầu bằng $1$, và bằng $0$ nếu có đúng một đầu vào ban đầu bằng $1$.

Dữ liệu luôn đảm bảo số đầu vào ban đầu bằng $1$ là đúng một hoặc đúng ba.

Dữ liệu ra

Bạn phải tạo tệp 1.out mô tả một mạch hợp lệ cho $N=128$.

Dòng đầu chứa số nguyên $K$, là số cổng được sử dụng. Mỗi dòng trong $K$ dòng tiếp theo có một trong ba dạng:

NOT in_1
OR in_1 in_2
AND in_1 in_2

Các dòng lần lượt thêm một cổng NOT, OR hoặc AND. Với NOT, in_1 là chỉ số đầu vào của cổng. Với OR và AND, in_1, in_2 là chỉ số hai đầu vào của cổng.

Cổng được mô tả ở dòng thứ $i$ sau dòng đầu tiên có chỉ số

\[ N-1+i. \]

Nói cách khác, $N$ đầu vào ban đầu có chỉ số từ $0$ đến $N-1$, cổng đầu tiên có chỉ số $N$, và mọi chỉ số đầu vào được nhắc đến trên một dòng phải nhỏ hơn chỉ số cổng của dòng đó.

Tổng số cổng không được vượt quá $1024$, tức là tệp kết quả có không quá $1025$ dòng.

Chấm điểm

Bài có một phần trị giá $100$ điểm và không có giới hạn thêm.

Nếu tồn tại một trạng thái đầu vào hợp lệ mà mạch cho kết quả sai, bài làm nhận $0$ điểm. Ngược lại, với $K$ là số cổng, điểm nhận được bằng $100f(K)$, trong đó

\[ f(K)= \begin{cases} 0, & 1024<K,\\ 0.3-0.1\dfrac{K-384}{896}, & 384<K\le 1024,\\ 0.6-0.3\dfrac{K-256}{128}, & 256<K\le 384,\\ 1-0.40\dfrac{K-215}{41}, & 215<K\le 256,\\ 1, & K\le 215. \end{cases} \]

Ví dụ

Xét phiên bản đơn giản với $N=4$; bạn chỉ cần nộp lời giải cho $N=128$. Một mạch hợp lệ là:

3
OR 0 1
OR 2 3
AND 4 5

Mạch gồm:

Cổng $4$ cho đầu ra $1$ nếu ít nhất một trong hai đầu vào $0,1$ bằng $1$.
Cổng $5$ cho đầu ra $1$ nếu ít nhất một trong hai đầu vào $2,3$ bằng $1$.
Cổng $6$ cho đầu ra $1$ nếu đầu ra của cả cổng $4$ và cổng $5$ đều bằng $1$.

Có thể kiểm tra rằng mạch cho kết quả đúng với mọi trạng thái đầu vào hợp lệ của phiên bản này.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 2, bài Triple Circuit.

2. SEATST 2026 - Car Gathering

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

Có $N$ chiếc xe, đánh số từ $0$ đến $N-1$, nằm trên một trục số. Bạn được cho danh sách vị trí

\[ X[0],X[1],\ldots,X[N-1] \]

và danh sách mức tiêu hao nhiên liệu trên mỗi đơn vị quãng đường

\[ C[0],C[1],\ldots,C[N-1]. \]

Cả hai danh sách đều được sắp xếp không giảm. Tuy nhiên, bạn không biết chiếc xe nào ứng với vị trí nào hoặc mức tiêu hao nào. Bạn chỉ biết mỗi xe có đúng một vị trí và đúng một mức tiêu hao.

Tương đương, tồn tại hai hoán vị $P,Q$ độ dài $N$ sao cho xe thứ $i$ ở vị trí $X[P[i]]$ và có mức tiêu hao $C[Q[i]]$.

Trong bài này, một hoán vị $P$ độ dài $N$ là một mảng thỏa mãn $0\le P[i]\le N-1$ với mọi $0\le i<N$, và $P[i]\ne P[j]$ với mọi $0\le i<j<N$. Chẳng hạn, $[2,1,0]$ là một hoán vị độ dài $3$, còn $[1,2,3]$ và $[2,0,2]$ thì không.

Với một cách gán $(P,Q)$, tổng chi phí nhiên liệu để tập hợp tất cả xe tại điểm $y$ là

\[ \operatorname{cost}(P,Q,y) =\sum_{i=0}^{N-1}|X[P[i]]-y|\cdot C[Q[i]]. \]

Với một điểm nguyên $p$, định nghĩa chi phí trong trường hợp xấu nhất tại $p$ là tổng chi phí lớn nhất trên mọi cách gán có thể:

\[ \operatorname{worst}(p)=\max_{P,Q}\operatorname{cost}(P,Q,p). \]

Hãy tìm một điểm nguyên $p$ làm nhỏ nhất $\operatorname{worst}(p)$. Nếu có nhiều điểm cùng đạt giá trị nhỏ nhất, có thể trả về bất kỳ điểm nào.

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

Bạn cần cài đặt hàm sau:

C++

int car_gathering(int N, std::vector<int> X, std::vector<int> C);

$N$ là số xe.
$X$ là mảng độ dài $N$ chứa các vị trí xe, đã được sắp xếp không giảm.
$C$ là mảng độ dài $N$ chứa các mức tiêu hao nhiên liệu, đã được sắp xếp không giảm.
Hàm được gọi đúng một lần trong mỗi test.
Hàm phải trả về một điểm nguyên $p$ làm nhỏ nhất chi phí trong trường hợp xấu nhất.

Bài nộp không được cài đặt hàm main và phải khai báo #include "gather.h".

Giới hạn

$1\le N\le 10\,000\,000$.
$-10^9\le X[i]\le 10^9$ với mọi $0\le i<N$.
$0\le C[i]\le 100$ với mọi $0\le i<N$.
$X[i]\le X[j]$ và $C[i]\le C[j]$ với mọi $0\le i<j<N$.

Chấm điểm

Phần	Điểm	Giới hạn thêm
1	10	$N\le 1000$, $
2	23	$N\le 100\,000$
3	17	$N\le 1\,000\,000$
4	31	$C[i]\le 1$ với mọi $0\le i<N$
5	19	Không có giới hạn thêm

Ví dụ

Xét lời gọi:

C++

car_gathering(3, [-1, 2, 3], [1, 1, 2])

Giả sử $p=1$. Có thể chứng minh cách gán $P=[0,1,2]$, $Q=[2,1,0]$ tạo ra trường hợp xấu nhất:

\[ \operatorname{worst}(1) =|-1-1|\cdot2+|2-1|\cdot1+|3-1|\cdot1 =7. \]

Cũng có thể chứng minh $p=1$ làm nhỏ nhất giá trị $\operatorname{worst}(p)$. Vì vậy hàm phải trả về 1.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

N
X[0] X[1] ... X[N - 1]
C[0] C[1] ... C[N - 1]

và in một số nguyên là giá trị do car_gathering trả về.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 2, bài Car Gathering.

3. SEATST 2026 - Troublesome Trip

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

Một loài sinh vật độc đáo và bí ẩn tên là Nuko sinh sống trên một quần đảo xa xôi. Quần đảo được mô hình hóa bởi $N$ hòn đảo, đánh số từ $0$ đến $N-1$, và $M$ cây cầu. Cầu thứ $i$ nối hai đảo phân biệt $U[i]$, $V[i]$ theo cả hai chiều. Không có hai cầu nào nối cùng một cặp đảo, và có thể đi giữa mọi cặp đảo.

Thời xa xưa, Nuko chỉ sống trên đảo $0$. Sau một thời gian dài, chúng đã lan ra mọi hòn đảo. Mỗi khi một nhóm Nuko đi qua một cây cầu đến đảo mới, chúng tiến hóa thành một phân loài khác với phân loài ở đảo trước đó.

Cụ thể, Nuko trên đảo $j$ thuộc phân loài $s_j$, trong đó $s_j$ là số cầu ít nhất phải đi qua để đến đảo $j$ từ đảo $0$. Chẳng hạn, Nuko trên đảo $0$ thuộc phân loài $0$.

Bạn muốn đi từ đảo $A$ đến đảo $B$ bằng các cây cầu; luôn có $A\ne B$. Khi đặt chân lên một hòn đảo, bạn chắc chắn gặp phân loài Nuko sống ở đó. Vì mỗi phân loài có tập tục riêng và việc thích nghi với nhiều tập tục rất phiền phức, bạn muốn chọn một đường đi sao cho số phân loài Nuko phân biệt gặp phải là nhỏ nhất.

Hãy tìm số phân loài phân biệt ít nhất phải gặp trên hành trình từ $A$ đến $B$.

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

Bạn cần cài đặt hàm sau:

C++

int min_distinct(int N, int M, int A, int B,
                 std::vector<int> U, std::vector<int> V);

$N$ là số đảo và $M$ là số cầu.
$A,B$ lần lượt là đảo bắt đầu và đảo kết thúc.
$U,V$ là hai mảng độ dài $M$ mô tả các cây cầu.
Hàm phải trả về số phân loài Nuko phân biệt ít nhất phải gặp.

Bài nộp không được cài đặt hàm main và phải khai báo #include "trip.h".

Giới hạn

$2\le N\le 5\,000\,000$.
$1\le M\le 5\,000\,000$.
$0\le A,B<N$ và $A\ne B$.
$0\le U[i],V[i]<N$ và $U[i]\ne V[i]$ với mọi $0\le i<M$.
Với mọi $i\ne j$, hai cặp $(U[i],V[i])$ và $(U[j],V[j])$ không biểu diễn cùng một cạnh theo bất kỳ thứ tự nào.
Đồ thị liên thông.

Chấm điểm

Phần	Điểm	Giới hạn thêm
1	4	$A=0$, $N,M\le 100\,000$
2	4	$M=N-1$, $N,M\le 100\,000$
3	6	$N,M\le 300$
4	8	$N,M\le 4000$
5	22	$N\le 4000$, $M\le 1\,000\,000$
6	14	$N,M\le 100\,000$
7	5	$N,M\le 300\,000$
8	5	$N,M\le 500\,000$
9	32	Không có giới hạn thêm

Trong phần 9, riêng trình chấm được đảm bảo sử dụng $1500$ ms trong giới hạn thời gian $4500$ ms.

Ví dụ

Ví dụ 1

C++

min_distinct(5, 5, 2, 4,
             [0, 1, 2, 3, 4],
             [1, 2, 3, 4, 0])

Đường đi tối ưu là $2-3-4$. Các phân loài gặp phải là $1$ và $2$, nên hàm trả về 2.

Ví dụ 2

C++

min_distinct(8, 9, 4, 7,
             [0, 0, 0, 1, 1, 2, 2, 6, 7],
             [1, 2, 3, 4, 5, 5, 6, 3, 3])

Đường đi tối ưu là $4-1-5-2-6-3-7$. Các phân loài gặp phải là $1$ và $2$, nên hàm trả về 2.

Ví dụ 3

C++

min_distinct(15, 17, 3, 7,
             [0, 1, 2, 3, 4, 13, 12, 12, 11, 10, 10, 9, 8, 7, 6, 8, 0],
             [1, 2, 3, 4, 13, 12, 1, 11, 10, 9, 5, 8, 7, 6, 5, 14, 14])

Số phân loài phân biệt ít nhất phải gặp khi đi từ đảo $3$ đến đảo $7$ là $3$, nên hàm trả về 3.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

N M A B
U[0] V[0]
U[1] V[1]
...
U[M - 1] V[M - 1]

và in một số nguyên là giá trị do min_distinct trả về.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 2, bài Troublesome Trip.

Phần	Điểm	Giới hạn thêm
1	4	\(A=0\), \(N,M\le 100\,000\)
2	4	\(M=N-1\), \(N,M\le 100\,000\)
3	6	\(N,M\le 300\)
4	8	\(N,M\le 4000\)
5	22	\(N\le 4000\), \(M\le 1\,000\,000\)
6	14	\(N,M\le 100\,000\)
7	5	\(N,M\le 300\,000\)
8	5	\(N,M\le 500\,000\)
9	32	Không có giới hạn thêm

Phần	Điểm	Giới hạn thêm
1	10	\(N\le 1000\), $
2	23	\(N\le 100\,000\)
3	17	\(N\le 1\,000\,000\)
4	31	\(C[i]\le 1\) với mọi \(0\le i<N\)
5	19	Không có giới hạn thêm