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_i đượ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_i + K và A_i − 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_i| ≤ 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_i ≤ 10³.
20% số test tiếp theo ứng với 20% số điểm có K = 1; 0 ≤ A_i ≤ 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.

26 chữ cái từ a đến z xếp theo thứ tự trên một vòng tròn, z nằm cạnh a

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_i| ≤ 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_i ≥ 0.
20% số test tiếp theo ứng với 20% số điểm có N ≤ 5000; A_i ≥ 0.
20% số test tiếp theo ứng với 20% số điểm có A_i ≥ 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_i. 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_i > 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_i ≤ 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_i > 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_i > 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_i > 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_i ≤ 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.

Hướng dẫn giải và đáp án

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

Xem hướng dẫn & lời giải

Hướng dẫn giải

Chi phí thuê đủ bảy ngày là 7K. Nếu N < 7K thì in −1; ngược lại in N − 7K. Dùng số nguyên 64 bit vì tích có thể tới 7·10⁹.

Độ phức tạp: O(1).

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n, k;
    cin >> n >> k;
    cout << (n < 7 * k ? -1 : n - 7 * k);
}

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

Xem hướng dẫn & lời giải

Hướng dẫn giải

Đưa mọi giá trị vào bảng băm. Với mỗi A_i, kiểm tra A_i − K và A_i + K có cùng xuất hiện không. Các phần tử phân biệt nên mỗi giá trị chỉ được đếm một lần.

Độ phức tạp: O(N) kỳ vọng.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    unordered_set<long long> s;
    s.reserve(n * 2);
    vector<long long> a(n);
    for (auto &x : a)
        cin >> x, s.insert(x);
    int ans = 0;
    for (long long x : a)
        ans += s.count(x - k) && s.count(x + k);
    cout << ans;
}

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

Xem hướng dẫn & lời giải

Hướng dẫn giải

Lập mảng cộng dồn số lần xuất hiện của 26 chữ cái để lấy tập chữ cái của mỗi đoạn trong O(26), biểu diễn tập bằng mặt nạ 26 bit. Xét khoảng cách d từ 13 giảm về 1: quay vòng mặt nạ d vị trí; nếu mặt nạ ban đầu và mặt nạ đã quay có bit chung thì có hai chữ cách nhau đúng d trên vòng tròn. Giá trị d đầu tiên tìm được là đáp án.

Độ phức tạp: O(26N + 39Q).

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<array<int, 26>> pre(n + 1);
    for (int i = 0; i < n; ++i) {
        pre[i + 1] = pre[i];
        ++pre[i + 1][s[i] - 'a'];
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        uint32_t mask = 0;
        for (int c = 0; c < 26; ++c)
            if (pre[r][c] > pre[l][c])
                mask |= 1u << c;
        int ans = 0;
        for (int d = 13; d >= 1; --d) {
            uint32_t rot = ((mask << d) | (mask >> (26 - d))) & ((1u << 26) - 1);
            if (mask & rot) {
                ans = d;
                break;
            }
        }
        cout << ans << '\n';
    }
}

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

Xem hướng dẫn & lời giải

Hướng dẫn giải

Gọi tổng cả dãy là T. Nếu T ≤ S thì không cần xóa. Ngược lại, đoạn bị xóa phải có tổng ít nhất T − S; bài toán trở thành tìm đoạn ngắn nhất có tổng không nhỏ hơn một ngưỡng dương, trong dãy có thể có số âm.

Dùng tổng tiền tố và hàng đợi hai đầu (deque) giữ các tổng tiền tố tăng dần: lấy ra ở đầu deque khi hiệu đã đủ ngưỡng (cập nhật đáp án), bỏ ở cuối deque các tổng tiền tố không nhỏ hơn tổng mới, vì chỉ số mới luôn có lợi hơn cho các đoạn về sau.

Độ phức tạp: O(N).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> p(n + 1);
    for (int i = 1; i <= n; ++i) {
        ll x;
        cin >> x;
        p[i] = p[i - 1] + x;
    }
    ll S;
    cin >> S;
    if (p[n] <= S) {
        cout << 0;
        return 0;
    }
    ll need = p[n] - S;
    deque<int> dq;
    int ans = n + 1;
    for (int i = 0; i <= n; ++i) {
        while (!dq.empty() && p[i] - p[dq.front()] >= need) {
            ans = min(ans, i - dq.front());
            dq.pop_front();
        }
        while (!dq.empty() && p[i] <= p[dq.back()])
            dq.pop_back();
        dq.push_back(i);
    }
    cout << (ans == n + 1 ? -1 : ans);
}

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

Xem hướng dẫn & lời giải

Hướng dẫn giải

Với sức công phá cố định X, xử lý bia từ trái sang phải. Khi đến bia i, sát thương từ các phát trước đã xác định; nếu bia còn độ bền r > 0 thì bắt buộc phải bắn đúng ⌈r/X⌉ phát vào nó. Mô phỏng này cho số phát ít nhất.

Một phát tại i gây cho vị trí j sát thương X − (j − i)² = −j² + 2ij + (X − i²) khi j − i ≤ ⌊√(X − 1)⌋. Mỗi nhóm phát là cộng một đa thức bậc hai trên một đoạn, nên dùng ba mảng hiệu cho hệ số của j², j và hằng số để cập nhật/đọc sát thương trong O(1) mỗi bia.

Số phát cần dùng không tăng theo X, nên tìm kiếm nhị phân X nhỏ nhất (trước đó nhân đôi cận trên đến khi khả thi). Các tổng sát thương dùng __int128.

Độ phức tạp: O(N log X).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll K;
    cin >> n >> K;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    auto enough = [&](ll X) {
        ll D = sqrt((long double)(X - 1));
        while ((D + 1) <= (X - 1) / (D + 1))
            ++D;
        while (D > 0 && D > (X - 1) / D)
            --D;
        vector<i128> d2(n + 3), d1(n + 3), d0(n + 3);
        i128 c2 = 0, c1 = 0, c0 = 0;
        ll shots = 0;
        for (ll i = 1; i <= n; ++i) {
            c2 += d2[i];
            c1 += d1[i];
            c0 += d0[i];
            i128 damage = c2 * i * i + c1 * i + c0;
            i128 rem = (i128)a[i] - damage;
            if (rem <= 0)
                continue;
            ll t = (ll)((rem + X - 1) / X);
            shots += t;
            if (shots > K)
                return false;
            ll L = i + 1, R = min<ll>(n, i + D);
            if (L <= R) {
                i128 A = -t, B = 2 * (i128)i * t, C = (i128)t * (X - i * i);
                d2[L] += A;
                d2[R + 1] -= A;
                d1[L] += B;
                d1[R + 1] -= B;
                d0[L] += C;
                d0[R + 1] -= C;
            }
        }
        return shots <= K;
    };
    ll lo = 0, hi = 1;
    while (!enough(hi))
        hi *= 2;
    while (lo + 1 < hi) {
        ll mid = lo + (hi - lo) / 2;
        if (enough(mid))
            hi = mid;
        else
            lo = mid;
    }
    cout << hi;
}

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