Chọn ĐTQG Gia Lai 2025

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Doraemon truyền năng lượng

Doraemon đang du hành vũ trụ thì phát hiện có $n$ trạm không gian, giả sử các trạm được đánh số từ $1$ đến $n$ . Trạm thứ $i$ có khả năng tiếp nhận năng lượng tối đa là $a i$ (đơn vị năng lượng).

Doraemon có khả năng truyền năng lượng trong phạm vi hoạt động $K$ $(K \geq 0)$ . Doraemon sẽ chỉ truyền được năng lượng giữa các trạm có thể chịu được mức năng lượng $K$ $(a i \geq K)$ .

Ban đầu, Doraemon nạp năng lượng cho trạm $1$ . Một trạm sau khi nhận được năng lượng có thể truyền tiếp cho các trạm bên phải trong phạm vi $K$ (tức là các trạm có chỉ số trong đoạn $[i + 1, i + K]$ , nếu các trạm đó có thể nhận được năng lượng ở mức $K$ ).

Nhiệm vụ của bạn là giúp Doraemon tìm ra giá trị nhỏ nhất của $K$ sao cho năng lượng có thể truyền từ trạm $1$ đến trạm $n$ .

Input

Dòng đầu tiên chứa số nguyên dương $n$ $(1 \leq n \leq 107)$ .

Dòng thứ hai gồm $n$ số nguyên $a 1, a 2, \dots, a n$ $(0 \leq a i \leq n)$ .

Dữ liệu vào đảm bảo luôn tồn tại ít nhất một giá trị $K$ thỏa mãn yêu cầu.

Output

Một số nguyên dương duy nhất là giá trị nhỏ nhất của $K$ sao cho năng lượng có thể truyền từ trạm $1$ đến trạm $n$ .

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$n \leq 100$
2	$20%$	$n \leq 1000$
3	$20%$	$n \leq 105$
4	$20%$	$n \leq 106$
5	$20%$	Không có ràng buộc gì thêm

Sample Input 1

9
9 8 8 0 0 8 0 0 9

Sample Output 1

Notes

Với $K = 3$ , chỉ những trạm có khả năng $a i \geq 3$ mới được tham gia truyền năng lượng: ${1, 2, 3, 6, 9}$ .

Năng lượng bắt đầu truyền ở trạm $1$ : Trạm $1 \to$ trạm $3 \to$ trạm $6 \to$ trạm $9$ .

Cuối cùng, năng lượng đến được trạm $9 \Rightarrow K = 3$ là giá trị nhỏ nhất thỏa mãn.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Xây dựng tuyến đường giao thông

Quốc gia $Z$ có $N$ thành phố được nối với nhau bởi $M$ con đường hai chiều và $K$ sân bay. Khi đi qua một con đường nối hai thành phố $U$ và $V$ $(1 \leq U, V \leq N)$ bằng ô tô thì sẽ mất thời gian là $C$ phút. Mỗi thành phố có tối đa một sân bay và bất cứ chuyến bay nào đều có thời gian di chuyển mất $T$ phút.

Lãnh đạo quốc gia $Z$ đưa ra $Q$ yêu cầu để đẩy mạnh phát triển cơ sở hạ tầng. Yêu cầu sau chỉ được thực hiện khi yêu cầu trước đó đã hoàn thành. Mỗi yêu cầu của lãnh đạo có thể thực hiện một trong ba loại công việc sau:

Loại 1: Xây dựng một con đường hai chiều mới giữa hai thành phố $U$ và $V$ $(1 \leq U, V \leq N)$ sao cho mất $C$ phút khi di chuyển bằng ô tô.

Loại 2: Xây dựng một sân bay mới ở một thành phố $X$ $(1 \leq X \leq N)$ .

Loại 3: Tính $(\sum i=1 N \sum j=1 N F(i,j))$ với $F(i,j)$ là tổng thời gian tối thiểu để đi từ thành phố $i$ đến thành phố $j$ qua các con đường và chuyến bay (nếu không có cách đi hoặc $i = j$ thì $F(i,j) = 0$ ).

Yêu cầu : Bạn hãy giúp lãnh đạo mô hình hóa các yêu cầu loại $1$ và $2$ , cho biết kết quả của các yêu cầu loại $3$ tương ứng.

Input

Dòng đầu tiên chứa năm số nguyên $N, M, Q, K, T$ $(1 \leq N, Q \leq 400, 0 \leq K \leq N, 1 \leq M \leq 105,$ $1 \leq T \leq 109)$ .

Dòng thứ hai gồm $K$ số nguyên đôi một phân biệt $A 1, A 2, \dots, A K$ cho biết các thành phố có sân bay $(1 \leq A i \leq N, 1 \leq i \leq K)$ .

$M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $U, V, C$ cho biết có con đường nối hai thành phố $U$ và $V$ với thời gian di chuyển bằng ô tô là $C$ phút $(1 \leq U, V \leq N, U \neq V, 1 \leq C \leq 109)$ .

$Q$ dòng cuối cùng, mỗi dòng được viết theo một trong ba định dạng tương ứng với ba loại yêu cầu sau:Loại 1: $1 X Y C$ , tức xây dựng một con đường mới nối hai thành phố $X$ và $Y$ với thời gian di chuyển bằng ô tô là $C$ phút $(1 \leq X, Y \leq N, X \neq Y, 1 \leq C \leq 109)$ .Loại 2: $2 X$ , tức xây dựng một sân bay mới tại thành phố $X$ $(1 \leq X \leq N)$ . Dữ liệu đảm bảo thành phố $X$ chưa có sân bay trước yêu cầu này.Loại 3: $3$ , tức yêu cầu tìm tổng thời gian tối thiểu.

Output

Với mỗi yêu cầu loại $3$ , ghi một số nguyên trên một dòng là kết quả tương ứng.

Scoring

Subtask	Điểm	Ràng buộc
1	$10%$	$N, Q \leq 100; M \leq 200; K = 0$ và không có yêu cầu loại $2$
2	$20%$	$N, Q \leq 100$
3	$30%$	$K = 0$ và không có yêu cầu loại $2$
4	$40%$	Không có ràng buộc gì thêm

Sample Input 1

3 1 3 2 100
2 3
1 3 50
3
1 2 3 30
3

Sample Output 1

600
320

Notes

Với yêu cầu loại $3$ thứ nhất:

$\sum i=1 N \sum j=1 N F(i,j) = F(1,1) + F(1,2) + F(1,3) + F(2,1) + F(2,2) + F(2,3) + F(3,1) + F(3,2) + F(3,3)$

$= 0 + (50 + 100) + 50 + (100 + 50) + 0 + 100 + 50 + 100 + 0$

$= 600$ .

Với yêu cầu loại $3$ thứ hai:

$\sum i=1 N \sum j=1 N F(i,j) = F(1,1) + F(1,2) + F(1,3) + F(2,1) + F(2,2) + F(2,3) + F(3,1) + F(3,2) + F(3,3)$

$= 0 + (50 + 30) + 50 + (30 + 50) + 0 + 30 + 50 + 30 + 0$

$= 320$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Vòng ngọc cổ

Trong quá trình khảo cổ, nhà nghiên cứu Henry đã phát hiện một chuỗi gồm $N$ hạt ngọc được xâu lại thành một vòng tròn khép kín. Henry đã đánh số các viên ngọc liên tiếp từ $1$ đến $N$ , viên ngọc thứ $i$ $(1 \leq i < N)$ nằm liền kề với viên ngọc thứ $i + 1$ , viên ngọc thứ $N$ nằm liền kề với viên ngọc thứ $1$ . Viên ngọc thứ $i$ mang giá trị là một số nguyên dương $A i$ .

Để phục vụ cho quá trình nghiên cứu, Henry bắt buộc phải tách chuỗi ngọc này thành $K$ đoạn liên tiếp nhau để phân tích. Chi phí để tách một đoạn liên tiếp các chuỗi ngọc được tính bằng bình phương tổng giá trị các viên ngọc nằm trong đoạn đó.

Cụ thể, nếu một đoạn ngọc có $m$ viên ngọc với giá trị các viên ngọc lần lượt là $A 1, A 2, A 3, \dots, A m$ , chi phí để tách đoạn này là: $(A 1 + A 2 + \dots + A m) 2$ .

Tổng chi phí của quá trình tách thành $K$ đoạn chính là tổng chi phí của $K$ đoạn ngọc được tạo thành. Nhiệm vụ của Henry là tìm cách cắt chuỗi ngọc sao cho tổng chi phí để cắt là nhỏ nhất.

Input

Dòng đầu tiên chứa hai số nguyên dương $N, K$ $(2 \leq K \leq N \leq 1000)$ — $N$ là số lượng viên ngọc của chuỗi ngọc, $K$ là số đoạn ngọc cần tách.

Dòng thứ hai chứa $N$ số nguyên dương $A 1, A 2, A 3, \dots, A N$ $(1 \leq A i \leq 105)$ — giá trị của các viên ngọc.

Output

Một số nguyên duy nhất là tổng chi phí nhỏ nhất để chia chuỗi ngọc thành $K$ đoạn.

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$K = 2, 2 \leq N \leq 103$
2	$20%$	$2 \leq K \leq N \leq 20$
3	$20%$	$2 \leq K \leq N \leq 100$
4	$20%$	$2 \leq K \leq N \leq 250$
5	$20%$	$2 \leq K \leq N \leq 500$

Sample Input 1

6 2
2 6 5 2 1 4

Sample Output 1

Notes

Chia chuỗi ngọc với thứ tự các chỉ số như sau:

Chuỗi ngọc 1: $(2, 3)$ .

Chuỗi ngọc 2: $(4, 5, 6, 1)$ .

Tổng chi phí: $(6 + 5) 2 + (2 + 1 + 4 + 2) 2 = 202$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Phần tử giữa

Phần tử giữa là phần tử nằm giữa của một tập hợp các số sau khi đã sắp xếp theo thứ tự không giảm. Nói cách khác, phần tử giữa chia dãy số thành hai phần sao cho:

Một nửa số phần tử nhỏ hơn hoặc bằng phần tử giữa.

Một nửa số phần tử lớn hơn hoặc bằng phần tử giữa.

Để tìm phần tử giữa của một dãy hữu hạn các số, ta sắp xếp theo thứ tự không giảm tất cả các số rồi lấy phần tử nằm giữa dãy số đó.

Cho bảng số nguyên không âm kích thước $m \times n$ ( $m$ dòng, $n$ cột) và hai số lẻ $r, c$ . Hãy tìm bảng con kích thước $r \times c$ để phần tử giữa của các số trong bảng là nhỏ nhất.

Input

Dòng đầu chứa bốn số nguyên $m, n, r, c$ $(1 \leq m, n \leq 1000; 1 \leq r \leq m; 1 \leq c \leq n)$ .

$m$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên không âm mô tả bảng số (các số không vượt quá $109$ ).

Output

Một số là phần tử giữa nhỏ nhất tìm được.

Scoring

Subtask	Điểm	Ràng buộc
1	$40%$	$m, n \leq 100$
2	$30%$	$m, n \leq 300$
3	$30%$	$m, n \leq 1000$

Sample Input 1

5 5 5 3
9 10 11 12 8
1 2 3 4 5
13 14 1 10 1
5 20 7 8 25
13 15 6 8 9

Sample Output 1

Notes

Bảng con kích thước $5 \times 3$ cần tìm là:

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. Chuyển hàng

Mỗi ngày, công ty ABC cần vận chuyển $N$ thùng hàng được đánh số từ $1$ đến $N$ . Được biết, thùng hàng $i$ nặng $W i$ ki-lô-gam, và $\sum i=1 N W i$ không vượt quá $106$ ki-lô-gam. Hiện tại, ở công ty chỉ có hai chiếc xe chở hàng, vì tính chất của công việc, toàn bộ $N$ thùng này cần được vận chuyển trong một lần. Cả hai xe đều đảm bảo tải trọng để chở $N$ thùng hàng.

Để đảm bảo quy tắc về vận chuyển, công ty đã đưa ra $M$ quy định với quy định thứ $j$ yêu cầu thùng hàng $P j$ và $Q j$ không được vận chuyển trên cùng một xe.

Yêu cầu : Hãy tính số cách khác nhau để chia các thùng hàng ra cho hai xe mà vẫn tuân thủ các quy định. Hai cách vận chuyển được gọi là khác nhau nếu tổng khối lượng vận chuyển của xe một và tổng khối lượng vận chuyển của xe hai khác nhau trong hai cách.

Input

Dòng đầu tiên chứa một số nguyên dương $T$ — số trường hợp cần tính $(1 \leq T \leq 10)$ .

$T$ nhóm dòng tiếp theo, mỗi nhóm dòng tương ứng một trường hợp có cấu trúc như sau:Dòng đầu chứa hai số nguyên $N, M$ $(2 \leq N \leq 5 \times 104; 0 \leq M \leq 105)$ .Dòng thứ hai chứa $N$ số nguyên, số thứ $i$ là giá trị của $W i$ $(W i \geq 1; \sum i=1 N W i \leq 106)$ . $M$ dòng tiếp theo, dòng thứ $j$ gồm hai số nguyên $P j, Q j$ $(1 \leq P j, Q j \leq N; P j \neq Q j)$ .

Output

$T$ dòng, dòng thứ $i$ chứa một số nguyên là kết quả của trường hợp thứ $i$ .

Scoring

Subtask	Điểm	Ràng buộc
1	$18%$	$N \leq 500; M \leq 1$
2	$16%$	$N \leq 20; M \leq 40$
3	$20%$	$\sum i=1 N W i \leq 3 \times 103$
4	$18%$	$\sum i=1 N W i \leq 2 \times 105$
5	$28%$	Không có ràng buộc gì thêm

Sample Input 1

Sample Output 1

6
0

Notes

Trường hợp 1: Có $6$ cách vận chuyển như sau:

Xe 1	Xe 2
$3$	$2, 3, 2, 5$
$3, 2$	$2, 3, 5$
$3, 2, 5$	$2, 3$
$2, 3, 2$	$3, 5$
$2, 3, 2, 5$	$3$
$3, 5$	$2, 3, 2$

Trường hợp 2: Không có cách vận chuyển phù hợp.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: Lời giải phụ thuộc cách hiểu đề; cần đối chiếu nguồn.

Câu 6. Robot và trò chơi thu kẹo

Nhóm các bạn học sinh giỏi môn Tin học của tỉnh Gia Lai đã tạo một trò chơi. Hệ thống trò chơi được thiết kế gồm một số con robot và $N$ trạm được đánh số liên tiếp từ $1$ tới $N$ . Các trạm được kết nối bởi $N-1$ đường đi hai chiều, đảm bảo giữa hai trạm bất kì đều tồn tại đường đi. Mỗi trạm được đặt một con số vui vẻ $L i$ . Mỗi robot mang một con số may mắn $W$ và một số viên kẹo. Nếu robot mang số may mắn $W$ đi qua trạm thứ $i$ có số vui vẻ $L i$ mà $W > L i$ , robot sẽ phải bỏ vào hộp kẹo của trạm $i$ một lượng kẹo là $W-L i$ viên. Nếu robot đi qua có con số may mắn $W$ không lớn hơn số vui vẻ $L i$ , robot sẽ được đi qua trạm $i$ mà không phải mất kẹo. Biết rằng, số viên kẹo mà mỗi robot mang theo luôn đảm bảo để tham gia trò chơi.

Có $M$ robot chuẩn bị tham gia trò chơi. Robot thứ $i$ di chuyển từ trạm xuất phát $S i$ đến trạm đích $T i$ với số may mắn là $W i$ . Mỗi robot đều đi theo đường đi sao cho khoảng cách di chuyển (số con đường đi qua) phải ít nhất. Tất cả robot đều bị kiểm tra và thu kẹo (nếu có) tại tất cả các trạm nằm trên con đường đi qua, bao gồm trạm xuất phát và trạm đích.

Yêu cầu : Hãy thống kê tổng số kẹo mà mỗi trạm đã thu được sau khi $M$ robot này hoàn thành trò chơi.

Input

Dòng đầu tiên chứa hai số nguyên dương $N$ và $M$ $(1 \leq N, M \leq 3 \times 105)$ — số lượng trạm và số lượng robot.

$N-1$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên dương $u i$ và $v i$ $(1 \leq u i, v i \leq N)$ , thể hiện có một đường đi trực tiếp giữa hai trạm này.

Dòng tiếp theo chứa $N$ số nguyên $L 1, L 2, \dots, L N$ $(0 \leq L i \leq 109)$ — số vui vẻ của mỗi trạm.

$M$ dòng cuối cùng, mỗi dòng chứa ba số nguyên $S i, T i$ và $W i$ $(1 \leq S i, T i \leq N, 1 \leq W i \leq 109)$ — thông tin về robot, trạm xuất phát, trạm đích, số may mắn của robot $i$ .

Output

Một dòng duy nhất chứa $N$ số nguyên (các số cách nhau bởi dấu cách), số thứ $i$ là tổng số kẹo mà trạm $i$ đã thu được.

Scoring

Subtask	Điểm	Ràng buộc
1	$20%$	$N, M \leq 100$
2	$20%$	$u i = i+1 2, v i = i+1$ với $i=1, \dots,N-1$
3	$20%$	Mỗi trạm kết nối không quá $2$ trạm khác
4	$20%$	$L i = 0$ với mọi $1 \leq i \leq N$
5	$20%$	Không có ràng buộc gì thêm

Sample Input 1

Sample Output 1

6 10 3

Notes

Trạm $1$ thu $1$ viên trên đường đi $1 \to 2$ và $5$ viên trên đường đi $2 \to 1 \to 3$ .

Trạm $2$ thu $3$ viên trên đường đi $1 \to 2$ và $7$ viên trên đường đi $2 \to 1 \to 3$ .

Trạm $3$ thu $3$ viên trên đường đi $2 \to 1 \to 3$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Cấu trúc đề và tiến độ