HSG lớp 9 Ninh Bình 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH NINH BÌNH ĐỀ CHÍNH THỨC
(Đề thi gồm 03 trang)

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

---

Tổng quan đề thi

TT	Tên bài	Tên chương trình	Dữ liệu vào	Dữ liệu ra	Điểm
1	HÌNH CHỮ NHẬT	HCNMAX.*	HCNMAX.INP	HCNMAX.OUT	4,0
2	SỐ ĐẶC BIỆT	SODB.*	SODB.INP	SODB.OUT	4,0
3	ĐẾM SỐ NGUYÊN TỐ	DEMNT.*	DEMNT.INP	DEMNT.OUT	4,0
4	CHIA DÃY	CHIADAY.*	CHIADAY.INP	CHIADAY.OUT	4,0
5	SỐ GẦN CHÍNH PHƯƠNG	GCP.*	GCP.INP	GCP.OUT	4,0

(Trong đó * là PAS nếu sử dụng Pascal hoặc CPP nếu sử dụng C++ hoặc PY nếu sử dụng Python)

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

Câu 1. HÌNH CHỮ NHẬT (4,0 điểm)

Cho bốn số nguyên dương a, b, c, d. Biết rằng a, b là độ dài 2 cạnh của hình chữ nhật thứ nhất; c, d là độ dài 2 cạnh của hình chữ nhật thứ hai.

Yêu cầu: Hãy tính diện tích của hai hình chữ nhật và đưa ra diện tích lớn nhất.

Dữ liệu vào: trong tệp HCNMAX.INP theo thứ tự gồm bốn số nguyên dương a, b, c, d (a, b, c, d ≤ 10⁹).

Kết quả: đưa ra tệp HCNMAX.OUT là diện tích lớn nhất tìm được.

Ví dụ:

HCNMAX.INP	HCNMAX.OUT
2 4 3 6	18

Câu 2. SỐ ĐẶC BIỆT (4,0 điểm)

Số đặc biệt là số chia hết cho tích các chữ số của nó. Ví dụ, số 5 là số đặc biệt vì 5 chia hết cho 5; số 12 là số đặc biệt vì 12 chia hết cho 2 (1 × 2 = 2); số 102 không phải là số đặc biệt vì tích các chữ số của nó bằng 0 (1 × 0 × 2 = 0).

Yêu cầu: Cho dãy số A gồm n số nguyên dương a₁, a₂, …, a_n và 2 số nguyên dương l, r. Hãy liệt kê các số đặc biệt theo đúng thứ tự xuất hiện trong đoạn a_l, a_(l+1), …, a_r.

Dữ liệu vào: trong tệp SODB.INP

• Dòng đầu theo thứ tự gồm ba số nguyên dương n, l, r (1 ≤ n ≤ 10⁵; 1 ≤ l ≤ r ≤ n);
• Dòng thứ hai gồm n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁹; 1 ≤ i ≤ n).

Kết quả: trong tệp SODB.OUT gồm duy nhất một dòng ghi các số đặc biệt tìm được, các số cách nhau một dấu cách. Nếu không tìm được số đặc biệt nào thì in ra -1.

Ví dụ:

SODB.INP	SODB.OUT
8 2 5 2 12 15 20 5 28 36 39	12 15 5

Câu 3. ĐẾM SỐ NGUYÊN TỐ (4,0 điểm)

Trong một cuộc thi lập trình Robot, đội của An nhận được xâu tín hiệu S có độ dài không quá 3 × 10⁶ kí tự, chỉ gồm các chữ cái thường và chữ số gửi về thông qua đường truyền internet. An cần tách các số từ đoạn tín hiệu này và đếm số lượng số nguyên tố trong các số đã được tách. Biết rằng, mỗi số trong xâu S là một dãy các kí tự chữ số liên tiếp mà có các kí tự liền kề trước hoặc sau (nếu có) là kí tự chữ cái. Các số trong xâu S không vượt quá 10⁶.

Yêu cầu: Hãy viết chương trình đếm số lượng số nguyên tố được tách ra từ xâu S.

Dữ liệu vào: trong tệp văn bản DEMNT.INP gồm một xâu S chỉ chứa các kí tự chữ cái thường và chữ số.

Kết quả: trong tệp văn bản DEMNT.OUT ghi ra số lượng số nguyên tố trong các số được tách ra.

Ví dụ:

DEMNT.INP	DEMNT.OUT	Giải thích
nb05hsg21bc3956tin19	2	Các số được tách từ xâu S gồm 4 số {5; 21; 3956; 19} có 2 số nguyên tố là 5 và 19.
nb1hsg09tin68thcs135	0	Trong xâu S không có số nguyên tố nào.

Ràng buộc:

• Subtask 1: 25% số test tất cả các số trong xâu S đều có một chữ số;
• Subtask 2: 50% số test có độ dài của xâu S không vượt quá 1000 kí tự;
• Subtask 3: 25% số test không có ràng buộc gì thêm.

Câu 4. CHIA DÃY (4,0 điểm)

Cho dãy số A gồm n số nguyên a₁, a₂, …, a_n, có thể chia dãy số này thành các đoạn liên tiếp sao cho tổng các số trong mỗi đoạn là lũy thừa cơ số 2.

Ví dụ: dãy gồm 6 số A = {5, 3, 1, 1, 1, 3} có 2 cách chia thoả mãn:

• Cách 1: Chia 3 đoạn {5,3}; {1,1}; {1,3} có tổng lần lượt là 8 = 2³; 2 = 2¹, 4 = 2².
• Cách 2: Chia 4 đoạn {5,3}; {1}; {1}; {1,3} có tổng lần lượt là 8 = 2³; 1 = 2⁰; 1 = 2⁰, 4 = 2².

Yêu cầu: Em hãy viết chương trình tìm cách chia dãy A trên thành các đoạn con liên tiếp sao cho số lượng đoạn con là ít nhất và tổng các số trong mỗi đoạn là lũy thừa cơ số 2?

Dữ liệu vào: trong tệp văn bản CHIADAY.INP gồm:

• Dòng 1 là số nguyên dương n (1 ≤ n ≤ 10⁵);
• Dòng 2 gồm n số nguyên a₁, a₂, …, a_n (0 ≤ a_i ≤ 2 × 10⁴; 1 ≤ i ≤ n);

Kết quả: đưa ra tệp văn bản CHIADAY.OUT một số nguyên là số đoạn ít nhất chia được. Nếu không chia được thì in ra -1.

Ví dụ:

CHIADAY.INP	CHIADAY.OUT
6 5 3 1 1 1 3	3

Ràng buộc:

• Subtask 1: 25% số test có tổng tất cả các số trong dãy A là một lũy thừa cơ số 2;
• Subtask 2: 25% số test có n ≤ 3;
• Subtask 3: 25% số test có n ≤ 5000;
• Subtask 4: 25% số test không có ràng buộc gì thêm.

Câu 5. SỐ GẦN CHÍNH PHƯƠNG (4,0 điểm)

Một số tự nhiên được gọi là “Số gần chính phương” nếu số đó thỏa mãn đồng thời ba điều kiện sau:

• Có từ 3 chữ số trở lên.
• Chữ số ở hàng cao nhất (hàng đầu tiên bên trái) là một số chính phương.
• Tổng của hai chữ số cuối cùng (hàng chục và hàng đơn vị) là một số chính phương.

Yêu cầu: Cho số nguyên dương M, hãy đếm xem có bao nhiêu số “Số gần chính phương” trong đoạn từ 1 đến M.

Dữ liệu vào: trong tệp GCP.INP gồm một số nguyên dương M.

Kết quả: đưa ra tệp GCP.OUT gồm một số nguyên duy nhất là số lượng số “Số gần chính phương” tìm được.

Ví dụ:

GCP.INP	GCP.OUT
105	3

Giải thích: Có 3 số từ 1 đến 105 là số gần chính phương gồm: 100; 101; 104.

Ràng buộc:

• Subtask 1: 50% số test có 100 ≤ M ≤ 999;
• Subtask 2: 25% số test M có 1000 ≤ M ≤ 10⁶;
• Subtask 3: 25% số test M có dạng 10ᴷ với 6 < K < 18.

---

Hết

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

Câu 1. HÌNH CHỮ NHẬT (4,0 điểm)

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

Hướng dẫn giải

Tính hai diện tích bằng số nguyên 64 bit và in giá trị lớn hơn.

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max(a * b, c * d);
}

Câu 2. SỐ ĐẶC BIỆT (4,0 điểm)

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

Hướng dẫn giải

Với từng số trong đoạn [l, r], tính tích các chữ số. Nếu có chữ số 0 thì không đặc biệt; ngược lại kiểm tra số đó có chia hết cho tích không.

Độ phức tạp: O((r − l + 1) · số chữ số).

#include <bits/stdc++.h>
using namespace std;
long long prod(long long x) {
    long long p = 1;
    while (x) {
        int d = x % 10;
        if (d == 0)
            return 0;
        p *= d;
        x /= 10;
    }
    return p;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, l, r;
    cin >> n >> l >> r;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    bool any = false;
    for (int i = l; i <= r; i++) {
        long long p = prod(a[i]);
        if (p && a[i] % p == 0) {
            if (any)
                cout << ' ';
            cout << a[i];
            any = true;
        }
    }
    if (!any)
        cout << -1;
}

Câu 3. ĐẾM SỐ NGUYÊN TỐ (4,0 điểm)

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

Hướng dẫn giải

Sàng Eratosthenes đến 10⁶. Quét xâu, ghép từng đoạn chữ số liên tiếp thành một số rồi tra bảng nguyên tố.

Độ phức tạp: O(10⁶ log log 10⁶ + |S|).

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    const int M = 1000000;
    vector<bool> p(M + 1, true);
    p[0] = p[1] = false;
    for (int i = 2; i * i <= M; i++)
        if (p[i])
            for (int j = i * i; j <= M; j += i)
                p[j] = false;
    int ans = 0;
    for (size_t i = 0; i < s.size();) {
        if (!isdigit((unsigned char)s[i])) {
            i++;
            continue;
        }
        int x = 0;
        while (i < s.size() && isdigit((unsigned char)s[i]))
            x = x * 10 + s[i++] - '0';
        if (p[x])
            ans++;
    }
    cout << ans;
}

Câu 4. CHIA DÃY (4,0 điểm)

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

Hướng dẫn giải

Gọi P[i] là tổng tiền tố. Đoạn (j + 1..i) hợp lệ khi P[i] − P[j] = 2ᵏ. Đặt dp[i] là số đoạn ít nhất để chia i phần tử đầu. Lưu dp nhỏ nhất ứng với mỗi giá trị tổng tiền tố; với mỗi i thử mọi lũy thừa của 2 không vượt P[i].

Độ phức tạp: O(N log(tổng A)).

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    unordered_map<long long, int> best;
    best.reserve(n * 2 + 10);
    best[0] = 0;
    long long pref = 0;
    const int INF = 1e9;
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pref += x;
        int dp = INF;
        for (long long pw = 1; pw <= pref; pw <<= 1) {
            auto it = best.find(pref - pw);
            if (it != best.end())
                dp = min(dp, it->second + 1);
            if (pw > (1LL << 61))
                break;
        }
        auto it = best.find(pref);
        if (it == best.end())
            best[pref] = dp;
        else
            it->second = min(it->second, dp);
        cur = dp;
    }
    cout << (cur == INF ? -1 : cur);
}

Câu 5. SỐ GẦN CHÍNH PHƯƠNG (4,0 điểm)

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

Hướng dẫn giải

Quy hoạch chữ số, đếm riêng từng độ dài từ 3 đến số chữ số của M. Chữ số đầu chỉ thuộc 9; khi chọn mỗi chữ số tiếp theo, kiểm tra tổng hai chữ số liền nhau thuộc 16. Trạng thái gồm vị trí, cờ “còn bám sát M” và chữ số trước.

Độ phức tạp: O(số chữ số · 10 · 10).

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
ull countLen(const string &lim, int L) {
    static long long memo[20][2][10];
    memset(memo, -1, sizeof memo);
    function<ull(int, bool, int)> dfs = [&](int pos, bool tight, int prev) -> ull {
        if (pos == L)
            return 1;
        long long &res = memo[pos][tight][prev];
        if (res != -1)
            return res;
        res = 0;
        int hi = tight ? lim[pos] - '0' : 9;
        for (int d = 0; d <= hi; d++) {
            if (pos == 0 && d != 1 && d != 4 && d != 9)
                continue;
            if (pos == L - 1) {
                int s = prev + d;
                if (s != 0 && s != 1 && s != 4 && s != 9 && s != 16)
                    continue;
            }
            res += dfs(pos + 1, tight && d == hi, d);
        }
        return res;
    };
    return dfs(0, true, 0);
}
int main() {
    string m;
    cin >> m;
    ull ans = 0;
    for (int L = 3; L <= (int)m.size(); L++) {
        string lim = L == (int)m.size() ? m : string(L, '9');
        ans += countLen(lim, L);
    }
    cout << ans;
}

Cảm ơn Thầy Nguyễn Duy Chiến đã đóng góp lời giải đề này.

Xem tất cả đề do thầy Nguyễn Duy Chiến đóng góp →