HSG THPT Hưng Yên 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO HƯNG YÊN ĐỀ THI CHÍNH THỨC
(Đề thi có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT Năm học 2025 - 2026
Môn thi: Tin học
Thời gian làm bài 150 phút, không kể thời gian phát đề

---

Tổng quan đề thi

	Tên bài	Tên tệp chương trình	Tên tệp dữ liệu	Tên tệp kết quả	Điểm
Câu 1	Chia dư k	KTOTAL.*	KTOTAL.INP	KTOTAL.OUT	6
Câu 2	Lệch nhỏ nhất	MIND.*	MIND.INP	MIND.OUT	6
Câu 3	Số lớn nhất	CKSUB.*	CKSUB.INP	CKSUB.OUT	5
Câu 4	Xe cấp cứu	RESCUE.*	RESCUE.INP	RESCUE.OUT	3

Phần mở rộng .* là: .cpp đối với C++; .py đối với Python

Hãy lập trình giải các bài toán sau:

Câu 1. Chia dư k (6 điểm)

An là cậu bé rất yêu thích môn Tin học. Một hôm thầy giáo giảng phần các phép toán trên một số kiểu dữ liệu, An rất thích thú với phép toán chia lấy phần nguyên và phép toán chia lấy phần dư. Hôm nay, thầy giáo cho An 3 số tự nhiên n, m, k (k < m ≤ n). Thầy yêu cầu An tính tổng giá trị các số tự nhiên trong phạm vi từ 1 đến n có số dư là k trong phép chia cho m. An dễ dàng tính với các số nhỏ nhưng chưa thể giải được với trường hợp tổng quát. Hãy lập trình giúp An giải bài toán trên.

Dữ liệu: Vào từ file KTOTAL.INP một dòng duy nhất chứa 3 số tự nhiên n, m, k.

Kết quả: Đưa ra file KTOTAL.OUT một số nguyên duy nhất là tổng các số tìm được.

	KTOTAL.INP	KTOTAL.OUT
Ví dụ 1	10 3 2	15
Ví dụ 2	3 1 0	6

Giải thích ví dụ 1: Các số đó là 2, 5, 8.

Giải thích ví dụ 2: Các số đó là 1, 2, 3.

Subtasks:

• Subtask 1 (3.5 điểm): n ≤ 10⁵
• Subtask 2 (1.0 điểm): 10⁵ ≤ m, n ≤ 2 × 10⁹
• Subtask 3 (1.0 điểm): n ≤ 2 × 10⁹
• Subtask 4 (0.5 điểm): n ≤ 5 × 10⁹

Câu 2. Lệch nhỏ nhất (6 điểm)

Cho dãy số nguyên dương A₁, A₂, A₃, …, Aₙ. Tìm hai số có giá trị khác nhau trong dãy có tổng chẵn và chênh lệch giữa hai số đó là nhỏ nhất.

Dữ liệu: Vào từ file MIND.INP gồm 2 dòng:

• Dòng thứ nhất chứa số nguyên n (2 ≤ n ≤ 3 × 10⁵).
• Dòng thứ hai chứa n số nguyên dương A₁, A₂, A₃, …, Aₙ (Aᵢ ≤ 10⁸ ∀i = 1, 2, 3, …, n).

Các số trên một dòng được ghi cách nhau một dấu cách.

Kết quả: Ghi ra file MIND.OUT một số nguyên dương duy nhất là chênh lệch nhỏ nhất giữa hai số tìm được. Ghi ra -1 trong trường hợp không tồn tại.

	MIND.INP	MIND.OUT
Ví dụ 1	4 1 3 7 9	2
Ví dụ 2	4 9 10 1 6	4

Giải thích ví dụ 1: Hai số tìm được là (1,3) hoặc (7,9) đều có chênh lệch là 2.

Giải thích ví dụ 2: Hai số tìm được là (10,6) có chênh lệch là 4.

Subtasks:

• Subtask 1 (3.6 điểm): n ≤ 1000 và tất cả các số đều là số chẵn
• Subtask 2 (1.2 điểm): n ≤ 1000
• Subtask 3 (1.2 điểm): n ≤ 3 × 10⁵

Câu 3. Số lớn nhất (5 điểm)

Bạn Vinh rất thích số tự nhiên k và không thích chữ số c. Tuần này, Vinh và Hưng được giao nhiệm vụ ra đề cho một cuộc thi Tin học trong câu lạc bộ. Do vậy, mọi thông tin trao đổi qua mạng về đề thi cần được bảo mật. Hôm nay, sau khi soạn thảo xong, Vinh gửi cho Hưng một file văn bản được đặt mật khẩu cùng với một xâu S gồm n ký tự chữ số khác ‘0’. Vinh đã nói trước với Hưng rằng mật khẩu là số lớn nhất được biểu diễn bởi một trong các xâu con liên tiếp độ dài k của xâu S sao cho số đó không có chữ số c.

Yêu cầu: Hãy giúp Hưng lập trình xác định mật khẩu được dấu trong xâu S mà Vinh gửi.

Dữ liệu: Vào từ file CKSUB.INP:

• Dòng đầu tiên chứa 3 số nguyên n, k, c (0 ≤ c ≤ 9).
• Dòng thứ 2 chứa xâu S.

Kết quả: ghi ra file CKSUB.OUT một số nguyên duy nhất là mật khẩu tìm được.

Dữ liệu đảm bảo trong xâu S luôn tồn tại mật khẩu.

	CKSUB.INP	CKSUB.OUT
Ví dụ 1	6 1 2 827194	9
Ví dụ 2	6 3 2 827194	719

Giải thích ví dụ 1: k = 1, c = 2, các số có thể được biểu diễn bởi xâu con liên tiếp độ dài 1 của S là 8, 2, 7, 1, 9, 4. Số lớn nhất không chứa chữ số 2 là 9.

Giải thích ví dụ 2: k = 3, c = 2, các số có thể được biểu diễn bởi xâu con liên tiếp độ dài 3 của S là 827, 271, 719, 194. Số lớn nhất không chứa chữ số 2 là 719.

Subtasks:

• Subtask 1 (0.8 điểm): n ≤ 10; k = 1; c = 0
• Subtask 2 (2.0 điểm): k ≤ n ≤ 18
• Subtask 3 (1.4 điểm): k ≤ n ≤ 1000
• Subtask 4 (0.8 điểm): k ≤ n ≤ 3 × 10⁵

Câu 4. Xe cứu thương (3 điểm)

Một thành phố có N điểm dân cư đánh số từ 1 đến N, được kết nối bởi M con đường hai chiều. Con đường thứ i nối từ điểm uᵢ đến điểm vᵢ có độ dài là wᵢ (đơn vị độ dài) và thời gian di chuyển là tᵢ (đơn vị thời gian) (1 ≤ uᵢ, vᵢ ≤ N; 1 ≤ wᵢ, tᵢ ≤ 100 ∀i = 1, 2, 3, …, M). Xe cứu thương (chạy điện) có thể di chuyển từ điểm dân cư này sang tất cả các điểm dân cư khác thông qua các con đường trên.

Khi có yêu cầu, xe cứu thương ở vị trí hiện tại sẽ di chuyển tới đón bệnh nhân và đưa tới bệnh viện phù hợp. Theo thông số kỹ thuật, pin của xe không cho phép di chuyển quá L (đơn vị độ dài).

Trung tâm điều phối nhận được thông tin và giao nhiệm vụ cho Q xe khác nhau. Xe cứu thương thứ j đang ở vị trí Xⱼ được giao nhiệm vụ tới điểm Yⱼ đón bệnh nhân rồi đưa tới bệnh viện ở điểm Zⱼ (Xⱼ, Yⱼ, Zⱼ ≤ N ∀j = 1, 2, 3, …, Q).

Yêu cầu: Với mỗi xe cứu thương, hãy xác định thời gian di chuyển ngắn nhất để xe đó có thể tới đón và đưa bệnh nhân tới bệnh viện mà không cần phải dừng lại để sạc pin.

Dữ liệu: Vào từ file RESCUE.INP

• Dòng đầu tiên chứa 3 số nguyên dương N, M, L (N ≤ 100; M ≤ 1000; L < 1024).
• M dòng tiếp theo, dòng thứ i (i = 1, 2, 3, …, M) chứa 4 số nguyên uᵢ, vᵢ, wᵢ, tᵢ xác định con đường thứ i.
• Dòng tiếp theo chứa số nguyên dương Q.
• Q dòng cuối, dòng thứ j (j = 1, 2, 3, …, Q) chứa 3 số nguyên dương Xⱼ, Yⱼ, Zⱼ xác định vị trí và nhiệm vụ của xe thứ j.

Kết quả: Ghi ra file RESCUE.OUT gồm Q dòng, dòng thứ j là thời gian di chuyển ngắn nhất để xe j di chuyển đón và đưa bệnh nhân tới bệnh viện. Biết thời gian đưa bệnh nhân lên xe không đáng kể. Trường hợp xe bắt buộc cần dừng lại sạc pin thì đưa ra −1.

Ví dụ:

RESCUE.INP	RESCUE.OUT	Minh họa
4 5 21 1 4 10 3 4 2 6 9 1 2 20 10 2 3 5 2 1 3 7 9 3 1 1 2 3 2 1 4 1 2	10 13 -1	Đồ thị 4 điểm với các cạnh: 1–4 (w=10, t=3), 4–2 (w=6, t=9), 1–2 (w=20, t=10), 2–3 (w=5, t=2), 1–3 (w=7, t=9)

Giải thích:

• Xe thứ nhất đang ở điểm dân cư 1 đón luôn bệnh nhân ở điểm đó rồi đi trực tiếp tới 2.
• Xe thứ hai đi theo lộ trình 3 → 2 → 3 → 1. Không thể đi 3 → 2 → 1 do không đủ pin.
• Xe thứ ba không thể thực hiện được do không đủ pin.

Subtasks:

• Subtask 1 (0.9 điểm): Q ≤ 100, L = 1, Xⱼ = Yⱼ, ∀j = 1, 2, 3, …, Q
• Subtask 2 (1.2 điểm): Q ≤ 100, L = 2
• Subtask 3 (0.6 điểm): Q ≤ 5
• Subtask 4 (0.3 điểm): Q ≤ 10⁴

---

(Thí sinh không sử dụng tài liệu; Giám thị không giải thích gì thêm)