Chọn ĐTQG Đồng Nai 2025

Chọn ĐTQG Đồng Nai 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. Trạm quan trắc

Một viện nghiên cứu khí tượng thủy văn đặt N trạm quan trắc được đánh số từ 1 đến N dọc theo một con sông lớn để theo dõi mực nước và thu thập dữ liệu tài nguyên. Vị trí các trạm quan trắc được biểu diễn trên một trục số. Trạm thứ i nằm ở vị trí x_i, chứa g_i đơn vị dữ liệu và có r_i đơn vị đá dùng để làm kè chống lũ. Không có hai trạm nào nằm cùng vị trí.

Để bảo vệ các trạm quan trắc trong mùa mưa lũ, viện nghiên cứu muốn xây tối đa K đoạn kè rời nhau dọc bờ sông. Mỗi đoạn kè có thể có độ dài khác nhau. Chi phí để xây một đoạn kè từ vị trí x_a đến vị trí x_b là x_b - x_a (x_a < x_b) đơn vị đá và số đá này chỉ được lấy từ các trạm có vị trí thuộc đoạn [x_a, x_b]. Nói cách khác, nếu muốn xây một đoạn kè từ vị trí x_a đến x_b thì tổng số đơn vị đá của tất cả các trạm nằm trong đoạn kè này phải không nhỏ hơn x_b - x_a. Mỗi đoạn kè sẽ bảo vệ dữ liệu của các trạm bên trong chúng và mỗi trạm chỉ thuộc nhiều nhất một đoạn kè.

Yêu cầu : Hãy tìm phương án chọn tối đa K đoạn kè sao cho tổng giá trị dữ liệu được bảo vệ là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương N và K (1 ≤ N ≤ 2000, 1 ≤ K ≤ 10).

• N dòng tiếp theo, dòng thứ i gồm ba số nguyên x_i, g_i, r_i biểu thị vị trí, lượng dữ liệu và số đơn vị đá của trạm thứ i (|x_i| ≤ 10⁹, 1 ≤ g_i ≤ 10⁹, 1 ≤ r_i ≤ 10⁶).

Output

Một số nguyên duy nhất là tổng giá trị dữ liệu lớn nhất có thể được bảo vệ.

Scoring

Sample Input 1

6 2
20 100 4
0 100 3
1 10 1
9 10 1
11 80 1
12 80 4

Sample Output 1

370

Sample Input 2

6 4
20 100 4
0 100 3
1 10 1
9 10 1
11 80 1
12 80 4

Sample Output 2

380

Notes

Trong ví dụ thứ nhất, được xây tối đa K=2 đoạn kè, ta xây như sau:

• Xây đoạn kè thứ nhất [0,1] chứa trạm 2,3: tổng dữ liệu được bảo vệ là 110.

• Xây đoạn kè thứ hai [11,20] chứa trạm 1,5,6: tổng dữ liệu được bảo vệ là 260.

Tổng dữ liệu được bảo vệ của 2 đoạn kè là 370, đây là giá trị lớn nhất có thể.

Trong ví dụ thứ hai, được xây tối đa K=4 đoạn kè, ta chỉ cần xây 3 đoạn kè là đủ bảo vệ dữ liệu của toàn bộ N trạm:

• Xây đoạn kè thứ nhất [0,1] chứa trạm 2,3: tổng dữ liệu được bảo vệ là 110.

• Xây đoạn kè thứ hai [9,10] chứa trạm 4: tổng dữ liệu được bảo vệ là 10.

• Xây đoạn kè thứ ba [11,20] chứa trạm 1,5,6: tổng dữ liệu được bảo vệ là 260.

Tổng dữ liệu được bảo vệ của 3 đoạn kè là 380, đây là giá trị lớn nhất có thể.

---

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. Nhiệt độ

Một công ty xây dựng các phòng chăm sóc vật nuôi được mô tả bởi một hình chữ nhật kích thước m × n chia thành lưới ô vuông đơn vị. Mỗi ô là một phòng có nhiệt độ là một số nguyên trong đoạn 0 ⋯ 10⁹. Theo quy định các con vật phải được chăm sóc ở ít nhất T phòng trước khi đưa đi tiêu thụ. Khi di chuyển các con vật từ phòng này qua phòng khác nó phải chịu sốc nhiệt là độ lệch nhiệt độ giữa hai phòng. Khả năng chịu sốc nhiệt của con vật là một số D nhỏ nhất sao cho con vật có thể di chuyển tới ít nhất T phòng (tính cả phòng ban đầu). Biết rằng con vật ở một phòng có thể di chuyển sang các phòng có chung cạnh nếu độ chênh lệch nhiệt độ không vượt quá D.

Yêu cầu : Hãy giúp công ty tính tổng khả năng chịu sốc nhiệt của con vật ở các phòng cần được kiểm tra.

Input

• Dòng 1 chứa ba số nguyên dương m, n, T (m, n ≤ 500; T ≤ m × n).

• m dòng tiếp theo, dòng thứ i chứa n số nguyên, số thứ j là nhiệt độ của phòng (i,j).

• m dòng tiếp theo, dòng thứ i chứa n số nguyên thuộc {0,1}, trong đó số thứ j là 1 cho biết phòng (i,j) là phòng có con vật cần được kiểm tra.

Output

Một số nguyên duy nhất là tổng khả năng chịu sốc nhiệt của con vật ở các phòng cần được kiểm tra.

Scoring

Sample Input 1

4 4 8
15 20 18 100
13 19 23 26
18 17 40 60
19 35 26 30
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1

Sample Output 1

21

Sample Input 2

4 4 8
15 20 18 100
13 19 23 26
18 17 40 60
19 35 26 30
1 1 0 0
0 0 0 0
0 0 0 0
0 0 0 1

Sample Output 2

25

Notes

Trong ví dụ thứ nhất, khả năng chịu nhiệt của con vật ở phòng (1,1) là 5 và ở phòng (4,4) là 16. Vậy tổng khả năng chịu sốc nhiệt của 2 con ở 2 phòng là: 5+16=21.

Trong ví dụ thứ hai, khả năng chịu nhiệt của con vật ở phòng (1,1) là 5, ở phòng (1,2) là 4 và phòng (4,4) là 16. Vậy tổng khả năng chịu sốc nhiệt của 3 con ở 3 phòng là: 5+4+16=25.

---

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. Trò chơi bắt chuột

An đang tham gia một trò chơi do Cung văn hóa thiếu nhi tổ chức nhân dịp Trung thu sắp tới. Sân chơi được thiết kế dưới dạng sơ đồ cây có n đỉnh. Có một robot chuột và hai thiết bị bay điều khiển từ xa được đặt tại 3 đỉnh khác nhau trong cây. Nhiệm vụ của An là điều khiển thiết bị bay để bắt robot chuột. Robot chuột sẽ bị bắt khi có một thiết bị bay ở chung đỉnh với nó và không còn đường để robot chuột chạy thoát. Hai thiết bị bay điều khiển từ xa, ký hiệu là F₁ và F₂, dùng chung một điều khiển từ xa. Trên điều khiển có một công tắc, khi gạt công tắc sang trái thì sẽ điều khiển thiết bị F₁, gạt công tắc sang phải thì điều khiển thiết bị F₂.

Trong một bước di chuyển:

• An được phép điều khiển một thiết bị bay lên không trung và đáp xuống một đỉnh bất kỳ trong cây (kể cả đỉnh vừa mới rời khỏi). Thiết bị bay còn lại sẽ ở nguyên tại vị trí của nó.

• Trong lúc đó, robot chuột có thể đi đến một đỉnh khác trong cây bằng cách di chuyển theo các cạnh của cây, nhưng trong quá trình di chuyển không được phép đi qua đỉnh đang có thiết bị bay (vì sẽ bị bắt). Tốc độ của robot chuột rất nhanh, do đó nó luôn chạy thoát đến được đỉnh nó muốn trước khi thiết bị bay đáp xuống đất.

Robot chuột rất thông minh, nó luôn tìm được đường đi tối ưu để né tránh việc bị bắt. Hỏi An cần ít nhất bao nhiêu bước di chuyển để bắt được robot chuột.

Input

• Dòng đầu tiên chứa số nguyên dương n là số đỉnh của cây (3 ≤ n ≤ 10⁵);

• Dòng thứ hai chứa số nguyên dương R_c là vị trí ban đầu của robot chuột;

• Dòng thứ ba chứa số nguyên dương R₁ là vị trí ban đầu của thiết bị bay F₁;

• Dòng thứ tư chứa số nguyên dương R₂ là vị trí ban đầu của thiết bị bay F₂;

• n-1 dòng tiếp theo mô tả cây, mỗi dòng chứa 2 số nguyên dương U và V cho biết có một cạnh nối giữa đỉnh U và V.

Output

Một số nguyên duy nhất là số bước di chuyển ít nhất mà An cần thực hiện để bắt được robot chuột.

Scoring

Sample Input 1

4
2
1
3
1 2
2 3
3 4

Sample Output 1

2

Sample Input 2

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

Sample Output 2

4

Notes

Trong ví dụ thứ nhất:

• Bước 1: An đưa F₁ tới đỉnh 2. Robot chuột chạy sang đỉnh 1. Robot chuột không thể chạy sang đỉnh 4 vì F₂ đang ở đỉnh 3.

• Bước 2: An đưa F₂ tới đỉnh 1. Robot chuột không còn đường chạy nên bị bắt.

Trong ví dụ thứ hai:

---

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 4. Trò chơi

Bé An mới đi học mẫu giáo. Để bé yêu thích việc đến trường, cô giáo tổ chức một trò chơi thú vị cho bé như sau: Trong N ngày liên tiếp, mỗi ngày bé đến lớp cô sẽ đưa ra một giỏ kẹo. Giỏ kẹo ngày thứ i có x_i viên. Mỗi ngày đến lớp, bé có thể thực hiện một trong ba thao tác sau:

• Lấy toàn bộ số kẹo trong giỏ cho vào túi riêng và giữ lại chiếc giỏ không có kẹo đó để trả lại cho cô vào các ngày sau. Bé chỉ được thực hiện thao tác lấy giỏ kẹo khi thỏa mãn một trong hai điều kiện:

• Bé đang không giữ giỏ không có kẹo nào.

• Hôm qua bé vừa thực hiện hành động lấy giỏ kẹo và số giỏ không có kẹo hiện tại bé đang giữ nhỏ hơn M.

• Nếu bé đang giữ K giỏ (K > 0) không có kẹo và số kẹo hiện có trong túi riêng không nhỏ hơn C, bé có thể trả lại cho cô đúng 1 giỏ không có kẹo và C viên kẹo trong túi.

• Bé không làm gì cả (không nhận thêm giỏ cũng không trả lại).

Các thao tác được thực hiện sao cho kết thúc ngày N, bé không giữ chiếc giỏ nào.

Yêu cầu : Hãy tính số kẹo nhiều nhất bé có thể có trong túi sau khi kết thúc trò chơi.

Input

• Dòng đầu ghi ba số nguyên N, M, C là số ngày của trò chơi, số giỏ không có kẹo tối đa bé có thể giữ, số kẹo phải trả lại khi thực hiện thao tác trả giỏ (2 ≤ N ≤ 10000; 1 ≤ M ≤ 500; 1 ≤ C ≤ 1000).

• N dòng sau, mỗi dòng chứa một số nguyên x_i là số kẹo trong giỏ ngày i (1 ≤ x_i ≤ 1000).

Output

Một số nguyên duy nhất là số kẹo lớn nhất bé An có thể đạt được.

Scoring

Sample Input 1

5 2 5
8
4
6
18
5

Sample Output 1

16

Notes

• Ngày 1: lấy giỏ 1, tổng 8.

• Ngày 2: bỏ 1 giỏ, mất 5, còn 3.

• Ngày 3: không lấy.

• Ngày 4: lấy giỏ (18), tổng 21.

• Ngày 5: bỏ 1 giỏ, mất 5, tổng 16.

Kết thúc ngày 5 bé An không giữ giỏ nào, số kẹo tối đa là 16.

---

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 5. Kiểm tra dịch bệnh

Gia đình Nam có n lồng cá nuôi ở ngoại vi được đánh số liên tục từ 0 đến n-1, có một số cầu nối giữa các lồng cá này để có thể đi từ lồng này sang lồng khác. Do các yêu cầu về kiểm soát dịch bệnh nên các cầu nối này được thiết kế để di chuyển một chiều, và đảm bảo trong quá trình di chuyển không thể quay trở lại lồng đã đi qua.

Cơn bão số 10 vừa qua đã gây ảnh hưởng nghiêm trọng đến các gia đình nuôi cá. Sau khi cơn bão đi qua, Nam muốn kiểm tra chất lượng các lồng cá để lên phương án phòng ngừa dịch bệnh. Nam sử dụng các robot tự động di chuyển qua các lồng cá để ghi nhận tình hình cá trong lồng và đánh giá chất lượng nước trong lồng đó. Nam dùng máy bay không người lái thả robot xuống một lồng cá, robot sẽ di chuyển liên tục qua các lồng cá cho đến khi không di chuyển được nữa thì dừng lại chờ máy bay không người lái đến đón về xử lý kết quả và không quay trở lại lồng cá nữa. Để không bị trùng lặp về dữ liệu đánh giá thì mỗi lồng cá chỉ được thăm dò và đánh giá bởi đúng 1 robot.

Yêu cầu : Hãy cho biết Nam cần dùng ít nhất bao nhiêu robot sao cho tất cả các lồng cá đều có robot đến kiểm tra.

Input

• Dòng đầu tiên chứa số nguyên dương n là số lồng cá (0 < n ≤ 1000).

• Dòng thứ i trong n dòng tiếp theo bắt đầu bởi số nguyên k là số cầu nối đi ra từ lồng cá i-1, sau đó là k số nguyên là số hiệu các lồng cá mà có cầu nối từ lồng cá i-1 tới.

Output

Một số nguyên duy nhất là số lượng ít nhất robot Nam cần sử dụng.

Scoring

Sample Input 1

4
1 1
2 2 3
0
0

Sample Output 1

2

Sample Input 2

7
2 3 4
1 0
1 0
0
0
0
1 1

Sample Output 2

4

Notes

Ví dụ 1:

Ví dụ 2:

---

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 6. Hình vuông

Trên mặt phẳng với hệ tọa độ Đề-các vuông góc Oxy cho n điểm. Các điểm được đánh số từ 1 tới n, điểm thứ i có tọa độ (x_i, y_i). Ta nói một điểm được phủ bởi một hình vuông nếu điểm đó nằm ở miền trong của hình vuông hoặc nằm trên cạnh hình vuông.

Câu hỏi 1 : Tìm hai hình vuông có cạnh song song với trục tọa độ, kích thước k × k để phủ hết tất cả n điểm đã cho.

Câu hỏi 2 : Tìm hai hình vuông có cạnh song song với trục tọa độ, kích thước k × k, không có điểm chung, để phủ hết tất cả n điểm đã cho.

Yêu cầu : Tìm số k nhỏ nhất có thể cho hai câu hỏi trên.

Input

• Dòng đầu tiên chứa số nguyên dương C ≤ 100 là số bộ dữ liệu, và số nguyên q ∈ {1, 2} là loại câu hỏi.

• C nhóm dòng tiếp theo, mỗi nhóm dòng mô tả một bộ dữ liệu:Dòng đầu chứa số nguyên dương n ≤ 10⁵.n dòng tiếp theo, dòng thứ i chứa hai số nguyên x_i, y_i (-10⁹ ≤ x_i, y_i ≤ 10⁹).

Output

Ứng với mỗi bộ dữ liệu vào, ghi ra một số nguyên duy nhất là câu trả lời cho giá trị k của câu hỏi tương ứng.

Scoring

Sample Input 1

1 1
5
2 2
3 3
2 4
4 5
5 5

Sample Output 1

2

Sample Input 2

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

Sample Output 2

2
4

---

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.