Chọn đội tuyển HSG quốc gia Đồng Nai 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI ĐỀ THI CHÍNH THỨC

KỲ THI LẬP ĐỘI TUYỂN HỌC SINH GIỎI DỰ THI CẤP QUỐC GIA THPT Năm học 2025 - 2026
Môn: Tin học
Thời gian làm bài: 180 phút mỗi ngày (không kể thời gian giao đề)
Ngày thi thứ nhất: 02/10/2025 - Ngày thi thứ hai: 03/10/2025

Ngày thi thứ nhất (02/10/2025)

Câu	Tên bài	Tệp CT	Tệp dữ liệu	Tệp kết quả	Điểm
1	Trạm quan trắc	`QUANTRAC.*`	`QUANTRAC.INP`	`QUANTRAC.OUT`	7 điểm
2	Nhiệt độ	`NHIETDO.*`	`NHIETDO.INP`	`NHIETDO.OUT`	7 điểm
3	Bắt chuột	`BATCHUOT.*`	`BATCHUOT.INP`	`BATCHUOT.OUT`	6 điểm

(* có thể là py hoặc cpp tùy theo ngôn ngữ lập trình sử dụng là Python hoặc C++)

Câu 1. QUANTRAC Trạm quan trắc (7 điểm)

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ᵢ, chứa gᵢ đơn vị dữ liệu và có rᵢ đơ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ₐ đến vị trí x_b là x_b − xₐ (xₐ < 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ₐ, x_b]. Nói cách khác, nếu muốn xây một đoạn kè từ vị trí xₐ đế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ₐ. 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.

Dữ liệu: đọc từ tệp QUANTRAC.INP

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ᵢ, gᵢ, rᵢ biểu thị vị trí, lượng dữ liệu và số đơn vị đá của trạm thứ i (|xᵢ| ≤ 10⁹; 1 ≤ gᵢ ≤ 10⁹; 1 ≤ rᵢ ≤ 10⁶).

Kết quả: ghi ra tệp QUANTRAC.OUT

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ệ.

Ví dụ:

QUANTRAC.INP	QUANTRAC.OUT	Giải thích
`6 2` `20 100 4` `0 100 3` `1 10 1` `9 10 1` `11 80 1` `12 80 4`	`370`	Đượ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ể.
`6 4` `20 100 4` `0 100 3` `1 10 1` `9 10 1` `11 80 1` `12 80 4`	`380`	Đượ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ể.

Ràng buộc:

30% số test ứng với 30% số điểm của bài có K = 1.
70% số test ứng với 70% số điểm của bài không có ràng buộc gì thêm.

Câu 2. NHIETDO Nhiệt độ (7 điểm)

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.

Dữ liệu: đọc từ tệp NHIETDO.INP

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 ∈ {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.

Kết quả: ghi ra tệp NHIETDO.OUT 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.

Ví dụ:

NHIETDO.INP	NHIETDO.OUT	Giải thích
`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`	`21`	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
`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`	`25`	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

Ràng buộc:

Có 25% số test ứng với 25% số điểm của bài có 1 ≤ m, n ≤ 10.
Có 25% số test ứng với 25% số điểm của bài có 10 < m, n ≤ 100.
Có 50% số test ứng với 50% số điểm của bài không có ràng buộc nào thêm.

Câu 3. BATCHUOT Trò chơi bắt chuột (6 điểm)

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.

Dữ liệu: đọc từ tệp BATCHUOT.INP

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.

Kết quả: ghi ra tệp BATCHUOT.OUT 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.

Ví dụ:

BATCHUOT.INP	BATCHUOT.OUT	Giải thích
`4` `2` `1` `3` `1 2` `2 3` `3 4`	`2`	Cây là đường thẳng 1 — 2 — 3 — 4. 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.
`9` `1` `4` `5` `1 2` `2 3` `3 4` `4 5` `3 6` `6 7` `7 8` `8 9`	`4`	Cây ở hình dưới.

Ràng buộc:

Có 20% số test ứng với 20% số điểm của bài có 3 ≤ n ≤ 50.
Có 30% số test ứng với 30% số điểm của bài có 50 < n ≤ 1000.
Có 50% số test ứng với 50% số điểm của bài không có ràng buộc nào thêm.

Ngày thi thứ hai (03/10/2025)

Câu	Tên bài	Tệp CT	Tệp dữ liệu	Tệp kết quả	Điểm
1	Trò chơi	`TROCHOI.*`	`TROCHOI.INP`	`TROCHOI.OUT`	7 điểm
2	Kiểm tra dịch bệnh	`LONGCA.*`	`LONGCA.INP`	`LONGCA.OUT`	7 điểm
3	Hình vuông	`HV.*`	`HV.INP`	`HV.OUT`	6 điểm

(* có thể là py hoặc cpp tùy theo ngôn ngữ lập trình sử dụng là Python hoặc C++)

Câu 1. TROCHOI Trò chơi (7 điểm)

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ᵢ 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:
- Bé đang không giữ giỏ không có kẹo nào.
- Hoặc 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.

Dữ liệu: đọc từ tệp TROCHOI.INP

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ᵢ là số kẹo trong giỏ ngày i (1 ≤ xᵢ ≤ 1000).

Kết quả: Ghi ra tệp TROCHOI.OUT một số nguyên duy nhất là số kẹo lớn nhất bé An có thể đạt được.

Ví dụ:

TROCHOI.INP	TROCHOI.OUT	Giải thích
`5 2 5` `8` `4` `6` `18` `5`	`16`	• 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.

Ràng buộc:

Có 30% số test ứng với 30% số điểm của bài có 2 ≤ N ≤ 10.
Có 70% số test ứng với 70% số điểm của bài không có ràng buộc nào thêm.

Câu 2. LONGCA Kiểm tra dịch bệnh (7 điểm)

Gia đình Nam có n lồng cá nuôi ở ngoài vịnh đượ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.

Dữ liệu: đọc từ tệp LONGCA.INP

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.

Kết quả: ghi ra tệp LONGCA.OUT một số nguyên duy nhất là số lượng ít nhất robot Nam cần sử dụng.

Ví dụ:

LONGCA.INP	LONGCA.OUT
`4` `1 1` `2 2 3` `0` `0`	`2`
`7` `2 3 4` `1 0` `1 0` `0` `0` `0` `1 1`	`4`

Ràng buộc:

Có 20% số test ứng với 20% số điểm của bài có n ≤ 20.
Có 30% số test ứng với 30% số điểm của bài có n ≤ 400.
Có 50% số test ứng với 50% số điểm của bài không có ràng buộc gì thêm.

Câu 3. HV Hình vuông (6 điểm)

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ᵢ, yᵢ). 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.

Dữ liệu: đọc từ tệp HV.INP

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ᵢ, yᵢ (−10⁹ ≤ xᵢ, yᵢ ≤ 10⁹).

Kết quả: Ghi ra tệp HV.OUT

Ứ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.

Ví dụ:

HV.INP	HV.OUT
`1 1` `5` `2 2` `3 3` `2 4` `4 5` `5 5`	`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`	`2` `4`

Ràng buộc:

Có 50% số test ứng với 50% số điểm của bài có 1 ≤ n ≤ 1000.
Có 50% số test ứng với 50% số điểm của bài có 1000 < n ≤ 10⁵.

Thí sinh KHÔNG được sử dụng tài liệu.
Giám thị KHÔNG giải thích gì thêm.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English