HSG lớp 9 Hà Nội 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI ĐỀ CHÍNH THỨC
(Đề thi có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ Năm học 2025 - 2026
Môn thi: Tin học - Ngày thi: 10 tháng 01 năm 2026
Thời gian làm bài: 150 phút

---

Tổng quan bài thi

STT	Tên bài	Tên file chương trình	Tên file dữ liệu vào	Tên file kết quả ra	Điểm
1	Chợ xuân	CHOXUAN.*	CHOXUAN.INP	CHOXUAN.OUT	5
2	Cân bằng	CANBANG.*	CANBANG.INP	CANBANG.OUT	5
3	Khoảng cách	KHOANGCACH.*	KHOANGCACH.INP	KHOANGCACH.OUT	4
4	Xóa đoạn	XOADOAN.*	XOADOAN.INP	XOADOAN.OUT	3
5	Bắn súng	BANSUNG.*	BANSUNG.INP	BANSUNG.OUT	3

Chú ý: Dấu * được thay thế bởi PAS, CPP, PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, C/C++ hoặc Python.

Bài I. CHỢ XUÂN (5,0 điểm)

Nhà trường tổ chức Hội chợ xuân kéo dài trong 7 ngày, giá thuê một gian hàng là K đồng/ngày. Lớp An có N đồng, muốn thuê một gian hàng trong 7 ngày để bán thiệp. Hỏi số tiền còn lại sau khi thuê gian hàng của lớp An là bao nhiêu?

Dữ liệu vào từ file văn bản CHOXUAN.INP:

• Dòng đầu tiên chứa một số nguyên dương N (N ≤ 10⁹) là số tiền lớp An có.
• Dòng thứ hai chứa một số nguyên dương K (K ≤ 10⁹) là giá thuê gian hàng trong một ngày.

Kết quả ghi ra file văn bản CHOXUAN.OUT: Một số nguyên là số tiền còn lại của lớp An, nếu không đủ tiền thuê trong 7 ngày thì ghi ra −1.

Ví dụ:

CHOXUAN.INP	CHOXUAN.OUT	Giải thích
1000000 50000	650000	Lớp An có 1000000 đồng, tổng tiền thuê là 50000 × 7 = 350000 đồng. Vậy lớp An còn lại 1000000 − 350000 = 650000 đồng.
350000 50000	0	Lớp An có 350000 đồng, tổng tiền thuê là 50000 × 7 = 350000 đồng. Vậy lớp An còn lại 350000 − 350000 = 0 đồng.
200000 50000	-1	Lớp An có 200000 đồng, tổng tiền thuê là 50000 × 7 = 350000 đồng. Vậy lớp An không đủ tiền để thuê.

Bài II. CÂN BẰNG (5,0 điểm)

Cho dãy số nguyên A gồm N phần tử phân biệt A₁, A₂, …, A_N và số nguyên dương K. Phần tử Aᵢ được gọi là “cân bằng K” nếu trong dãy xuất hiện phần tử có giá trị bằng Aᵢ + K và Aᵢ − K. Ví dụ dãy số 5, 2, 4, 6 và K = 1 thì có 1 phần tử cân bằng là 5 vì dãy số có phần tử là 5 − 1 = 4 và 5 + 1 = 6.

Yêu cầu: Đếm số lượng phần tử “cân bằng K” của dãy số A.

Dữ liệu vào từ file văn bản CANBANG.INP:

• Dòng đầu tiên chứa hai số nguyên dương N và K (N ≤ 10⁵; K ≤ 10⁹).
• Dòng thứ hai chứa N số nguyên A₁, A₂, …, A_N (|Aᵢ| ≤ 10⁹; 1 ≤ i ≤ N).

Kết quả ghi ra file văn bản CANBANG.OUT: Gồm một số nguyên là kết quả của bài toán.

Ví dụ:

CANBANG.INP	CANBANG.OUT	Giải thích
6 1 4 1 7 8 5 6	3	Có 3 phần tử 5, 6 và 7 là “cân bằng K”.
6 2 4 -1 7 8 5 6	1	Có 1 phần tử 6 là “cân bằng K”.

Ràng buộc:

• Có 70% số test ứng với 70% số điểm có K = 1; N ≤ 10³ và 0 ≤ Aᵢ ≤ 10³.
• 20% số test tiếp theo ứng với 20% số điểm có K = 1; 0 ≤ Aᵢ ≤ 10⁶.
• 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.

Bài III. KHOẢNG CÁCH (4,0 điểm)

Điền 26 kí tự Tiếng Anh in thường theo thứ tự từ điển thành một vòng tròn cách đều nhau 1 đơn vị như hình bên. Khoảng cách giữa hai kí tự là số bước di chuyển ngắn nhất từ kí tự này đến kí tự kia. Ví dụ khoảng cách giữa hai kí tự ‘a’ và ‘c’ là 2; khoảng cách giữa ‘a’ và ‘z’ là 1.

Khoảng cách của một xâu là khoảng cách lớn nhất giữa hai kí tự bất kì của xâu đó. Ví dụ tính khoảng cách của xâu “adc”:

• Khoảng cách của ‘a’ và ‘d’ là 3.
• Khoảng cách của ‘a’ và ‘c’ là 2.
• Khoảng cách của ‘d’ và ‘c’ là 1.

Vậy khoảng cách của xâu “adc” là max(3, 2, 1) = 3.

Cho xâu S gồm N kí tự được đánh chỉ số từ 1 đến N và Q truy vấn, mỗi truy vấn yêu cầu tính khoảng cách của xâu con từ vị trí L đến vị trí R trong xâu S (1 ≤ L ≤ R ≤ N).

Dữ liệu vào từ file văn bản KHOANGCACH.INP:

• Dòng đầu tiên chứa xâu S chỉ gồm các kí tự Tiếng Anh in thường gồm N kí tự (1 ≤ N ≤ 10⁵).
• Dòng thứ hai chứa số nguyên dương Q (Q ≤ 10⁵).
• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên L, R (1 ≤ L ≤ R ≤ N) mô tả đoạn con của xâu S cần tính khoảng cách.

Kết quả ghi ra file văn bản KHOANGCACH.OUT: Gồm Q dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng.

Ví dụ:

KHOANGCACH.INP	KHOANGCACH.OUT	Giải thích
abcyzz 3 1 3 2 5 5 6	2 4 0	Truy vấn 1: khoảng cách của xâu “abc” là 2. Truy vấn 2: khoảng cách của xâu “bcyz” là 4. Truy vấn 3: khoảng cách của xâu “zz” là 0.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm có Q = 1; N ≤ 10³.
• 20% số test tiếp theo ứng với 20% số điểm có Q = 1.
• 20% số test tiếp theo ứng với 20% số điểm có N ≤ 10³.
• 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.

Bài IV. XÓA ĐOẠN (3,0 điểm)

Cho dãy số nguyên A gồm N phần tử A₁, A₂, …, A_N và số nguyên S. Bạn có thể xóa đi một đoạn con liên tiếp bất kỳ trong dãy (tức là chọn hai chỉ số L, R với 1 ≤ L ≤ R ≤ N và xóa các phần tử A_L, A_(L+1), …, A_R). Quy ước: Nếu xóa hết dãy thì tổng còn lại bằng 0.

Yêu cầu: Tìm độ dài nhỏ nhất của đoạn con cần xóa sao cho tổng các phần tử còn lại của dãy không vượt quá S. Nếu không cần xóa đoạn nào thì kết quả là 0, nếu không có cách xóa thỏa mãn thì kết quả là −1.

Dữ liệu vào từ file văn bản XOADOAN.INP:

• Dòng đầu tiên chứa số nguyên dương N (N ≤ 10⁵).
• Dòng thứ hai chứa N số nguyên A₁, A₂, …, A_N (|Aᵢ| ≤ 10⁹; 1 ≤ i ≤ N).
• Dòng thứ ba chứa số nguyên S (|S| ≤ 10¹⁴).

Kết quả ghi ra file văn bản XOADOAN.OUT: Gồm một số nguyên là kết quả của bài toán.

Ví dụ:

XOADOAN.INP	XOADOAN.OUT	Giải thích
5 4 -5 4 4 -2 0	2	Tổng dãy ban đầu là 5, cần tổng dãy nhỏ hơn hoặc bằng 0. Có thể xóa đoạn [3, 4] có tổng là 8 ⇒ tổng còn lại là 5 − 8 = −3 ≤ 0. Kết quả là 2.
3 4 2 1 0	3	Tổng dãy ban đầu là 7, cần tổng dãy nhỏ hơn hoặc bằng 0. Có thể xóa đoạn [1, 3] có tổng là 7 ⇒ tổng còn lại là 7 − 7 = 0 ≤ 0. Kết quả là 3.
3 1 2 3 -2	-1	Tổng dãy ban đầu là 6, cần tổng dãy nhỏ hơn hoặc bằng −2. Không có cách xóa thỏa mãn.
3 1 2 0 5	0	Tổng dãy ban đầu là 3, cần tổng dãy nhỏ hơn hoặc bằng 5. Không cần xóa đoạn nào.

Ràng buộc:

• Có 40% số test ứng với 40% số điểm có N ≤ 100; Aᵢ ≥ 0.
• 20% số test tiếp theo ứng với 20% số điểm có N ≤ 5000; Aᵢ ≥ 0.
• 20% số test tiếp theo ứng với 20% số điểm có Aᵢ ≥ 0.
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Bài V. BẮN SÚNG (3,0 điểm)

Trong một buổi tập bắn súng, có N tấm bia được xếp thành một hàng dọc, đánh số từ 1 tới N. Độ bền của các tấm bia được mô tả bởi dãy số A, tấm bia thứ i có độ bền ban đầu là Aᵢ. Một tấm bia được coi là bị phá hủy nếu độ bền của nó giảm xuống nhỏ hơn hoặc bằng 0 (khi này coi độ bền của tấm bia là 0).

Xạ thủ được quyền chọn một loại đạn có sức công phá X (với X là số nguyên dương tùy ý) để sử dụng cho toàn bộ buổi tập. Mỗi lần bắn, xạ thủ bắn một viên đạn thẳng dọc theo hàng các tấm bia, viên đạn sẽ trúng tấm bia đầu tiên chưa bị phá hủy (tấm bia thứ i có chỉ số nhỏ nhất và độ bền Aᵢ > 0). Do đạn có tính xuyên phá nên sẽ gây ảnh hưởng lên tấm bia thứ i và các tấm bia thứ j phía sau nó (j ≥ i). Độ bền của tấm bia thứ j (i ≤ j ≤ N) bị giảm một lượng theo công thức: max(0, X − (j − i)²).

Ví dụ: với X = 5, có 6 tấm bia với độ bền lần lượt là [0, 2, 5, 0, 1, 2], viên đạn đầu tiên trúng vào tấm bia thứ 2, sẽ gây ảnh hưởng cho các tấm bia thứ 2, 3, 5, 6 (vì tấm bia 1 và 4 có độ bền bằng 0), độ bền của các tấm bia bị giảm được tính như sau:

• Tấm bia thứ 2: max(0, 5 − (2 − 2)²) = max(0, 5 − 0²) = 5.
• Tấm bia thứ 3: max(0, 5 − (3 − 2)²) = max(0, 5 − 1²) = 4.
• Tấm bia thứ 5: max(0, 5 − (5 − 2)²) = max(0, 5 − 3²) = 0.
• Tấm bia thứ 6: max(0, 5 − (6 − 2)²) = max(0, 5 − 4²) = 0.

Vậy sau lượt bắn này, độ bền của các tấm bia là [0, 0, 1, 0, 1, 2].

Yêu cầu: Hãy tìm giá trị sức công phá X nhỏ nhất sao cho xạ thủ có thể phá hủy toàn bộ các tấm bia khi bắn không quá K lần.

Dữ liệu vào từ file văn bản BANSUNG.INP:

• Dòng đầu chứa hai số nguyên dương N, K (N ≤ 2 × 10⁵; K ≤ 10⁹) tương ứng là số tấm bia và số lần bắn tối đa.
• Dòng tiếp theo chứa N số nguyên dương mô tả dãy A (Aᵢ ≤ 10⁹; 1 ≤ i ≤ N).

Kết quả ghi ra file văn bản BANSUNG.OUT: Gồm một số nguyên dương X nhỏ nhất tìm được.

Ví dụ:

BANSUNG.INP	BANSUNG.OUT
6 3 6 7 1 3 2 1	5
3 1 3 7 3	8

Giải thích:

Ở ví dụ đầu tiên, chọn X = 5.

Ở lần bắn đầu tiên, tấm bia i đầu tiên có Aᵢ > 0 là tấm bia 1. Quá trình ảnh hưởng như sau:

• Sức công phá gây lên tấm bia 1 là: max(0, 5 − (1 − 1)²) = 5.
• Sức công phá gây lên tấm bia 2 là: max(0, 5 − (2 − 1)²) = 4.
• Tương tự, sức công phá gây lên các tấm bia thứ 3, 4, 5, 6 lần lượt là 1, 0, 0, 0.
• Vậy độ bền còn lại là A = [1, 3, 0, 3, 2, 1].

Ở lần bắn thứ hai, tấm bia i đầu tiên có Aᵢ > 0 vẫn là tấm bia 1. Quá trình ảnh hưởng như sau:

• Sức công phá lên các tấm bia thứ 1, 2, 4, 5, 6 lần lượt là 5, 4, 0, 0, 0.
• Độ bền các tấm bia là A = [0, 0, 0, 3, 2, 1].

Ở lần bắn thứ ba, tấm bia i đầu tiên có Aᵢ > 0 là tấm bia 4. Sức công phá lên các tấm bia thứ 4, 5, 6 lần lượt là 5, 4, 1. Khi này tất cả các tấm bia đều bị phá hủy.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm có N, K ≤ 30; Aᵢ ≤ 30.
• 20% số test tiếp theo ứng với 20% số điểm có K = 1.
• 30% số test tiếp theo ứng với 30% số điểm có N ≤ 1000.
• 20% số test còn lại với 20% số điểm không có ràng buộc gì thêm.

---

Giám thị không giải thích gì thêm.