HSG THCS Gia Lai 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH GIA LAI ĐỀ THI CHÍNH THỨC

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

---

Tổng quan đề thi

Bài	Tên bài	Tên tệp chương trình	Tên tệp dữ liệu vào	Tên tệp dữ liệu ra
Bài 1	Số phong phú	SPP.*	SPP.INP	SPP.OUT
Bài 2	Xóa tập tin	XOATT.*	XOATT.INP	XOATT.OUT
Bài 3	Đường đi	DUONGDI.*	DUONGDI.INP	DUONGDI.OUT
Bài 4	Số siêu nguyên tố	SIEUNT.*	SIEUNT.INP	SIEUNT.OUT

Chú ý:

• Phần mở rộng tên tệp chương trình theo ngôn ngữ lập trình của thí sinh (.pas; .cpp; .py).
• Khi chấm thi có xét đến thời gian xử lý bài toán của chương trình nên thí sinh không sử dụng các câu lệnh làm chậm hoặc làm dừng chương trình trong bài làm.
• Tệp dữ liệu vào và tệp dữ liệu ra ở trong thư mục hiện hành, thí sinh không khai báo đường dẫn đến tệp dữ liệu vào và dữ liệu ra.
• Thời gian chạy cho mỗi test của chương trình không quá 01 giây.
• Bộ nhớ cần dùng cho mỗi test của chương trình không quá 1024MB.

Bài 1. SỐ PHONG PHÚ (5,0 điểm)

Trong số học, số phong phú là số mà tổng các ước dương của số đó (không kể chính nó) lớn hơn số đó.

Ví dụ:

• Số 18 có tổng các ước (không kể 18): 1 + 2 + 3 + 6 + 9 = 21 > 18.
• Số 10 có tổng các ước (không kể 10): 1 + 2 + 5 = 8 < 10.

Khi đó ta nói số 18 là số phong phú còn số 10 không là số phong phú.

Dữ liệu vào: Từ tệp SPP.INP gồm một số tự nhiên N (0 < N < 10⁸).

Dữ liệu ra: Ghi ra tệp SPP.OUT số phong phú nhỏ nhất lớn hơn hoặc bằng N.

Ví dụ:

SPP.INP	SPP.OUT
18	18
10	12

Ràng buộc:

• Subtask 1 (50% số test): N ≤ 10⁵.
• Subtask 2 (50% số test): N < 10⁸.

Bài 2. XÓA TẬP TIN (5,0 điểm)

Một hệ thống máy tính đang lưu trữ N tập tin, tập tin thứ i được đặt tên là S_i. Nhận thấy rằng có nhiều tập tin không cần thiết, người ta cần xóa đi một số tập tin của hệ thống máy tính. Cụ thể, người ta đã thực hiện Q thao tác xóa tập tin. Mỗi thao tác được biểu diễn bởi một kí tự c, cho biết thao tác này xóa đi các tập tin có tên chứa ít nhất một kí tự c. Sau mỗi thao tác xóa, hãy cho biết còn lại bao nhiêu tập tin trong hệ thống máy tính.

Dữ liệu vào: Từ tệp XOATT.INP theo định dạng:

• Dòng đầu tiên gồm hai số nguyên N và Q (1 ≤ N, Q ≤ 10⁵).
• N dòng tiếp theo, dòng thứ i gồm xâu ký tự S_i độ dài không vượt quá 8, chỉ gồm các kí tự chữ cái in thường là tên của tập tin thứ i.
• Q dòng tiếp theo, mỗi dòng gồm một kí tự chữ cái in thường c là mô tả một thao tác xóa.

Dữ liệu ra: Ghi ra tệp XOATT.OUT gồm Q dòng, dòng thứ i gồm số tập tin còn lại trong hệ thống máy tính sau khi thực hiện thao tác xóa thứ i.

Ví dụ:

XOATT.INP	XOATT.OUT
5 3 chuc cac ban thi tot a b c	3 3 2

Ràng buộc:

• Subtask 1 (40% số test): N, Q ≤ 100.
• Subtask 2 (60% số test): Không có ràng buộc gì thêm.

Bài 3. ĐƯỜNG ĐI (5,0 điểm)

Cho lưới ô vuông hình chữ nhật m × n, mỗi ô chỉ chứa một giá trị 0 hoặc 1. Có bao nhiêu cách khác nhau để đi từ ô (1, 1) đến ô (m, n). Biết rằng mỗi lần đi chỉ được đi xuống dưới (từ ô (i, j) đến ô (i + 1, j)) hoặc sang phải (từ ô (i, j) đến ô (i, j + 1)) và không được đi vào ô có giá trị 1 (kể cả ô xuất phát (1, 1)).

	1	2	3	4
1	0	0	0	1
2	0	1	0	0
3	0	0	0	0

Dữ liệu vào: Từ tệp DUONGDI.INP theo định dạng:

• Dòng đầu tiên là 2 số nguyên dương m và n (m, n ≤ 50).
• m dòng tiếp theo, mỗi dòng gồm n số (0 hoặc 1) viết liền nhau của một hàng trong bảng.

Dữ liệu ra: Ghi ra tệp DUONGDI.OUT số đường đi khác nhau tìm được.

Ví dụ:

DUONGDI.INP	DUONGDI.OUT
3 4 0001 0100 0000	3

Ràng buộc:

• Subtask 1: Có 60% số test n, m ≤ 30.
• Subtask 2: Có 40% số test n, m ≤ 50.

Bài 4. SỐ SIÊU NGUYÊN TỐ (5,0 điểm)

Một số tự nhiên lớn hơn 10 được gọi là số siêu nguyên tố nếu cứ xóa bỏ chữ số hàng đơn vị của số đó ta luôn được số mới là số nguyên tố. Ví dụ số 293 là số siêu nguyên tố vì 293, 29, 2 là các số nguyên tố. Số 17 không phải số siêu nguyên tố vì 1 không phải là số nguyên tố.

Yêu cầu: Cho hai số nguyên dương a và b (a ≤ b). Đếm số lượng số siêu nguyên tố trong phạm vi từ a tới b.

Dữ liệu vào: Từ tệp SIEUNT.INP gồm hai số nguyên dương a và b (a ≤ b ≤ 10¹²) cách nhau một khoảng trống.

Dữ liệu ra: Ghi ra tệp SIEUNT.OUT số lượng số siêu nguyên tố tìm được.

Ví dụ:

	SIEUNT.INP	SIEUNT.OUT
Ví dụ 1	23 36	3
Ví dụ 2	100 311	4

Giải thích:

• Trong ví dụ 1, các số siêu nguyên tố là 23, 29, 31.
• Trong ví dụ 2, các số siêu nguyên tố là 233, 239, 293, 311.

Ràng buộc:

• Có 15% test tương ứng 15% số điểm có a ≤ b ≤ 100.
• Có 15% test tương ứng 15% số điểm có a ≤ b ≤ 10000.
• Có 30% test tương ứng 30% số điểm có a ≤ b ≤ 10⁶.
• Có 40% test còn lại tương ứng 40% số điểm không có ràng buộc gì thêm.

---

--- HẾT ---

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

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

Bài 1. SỐ PHONG PHÚ (5,0 điểm)

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

Hướng dẫn giải

Xét từng số x từ N tăng dần, duyệt ước đến √x và cộng cả cặp ước (d, x/d). Trừ chính x; số đầu tiên có tổng ước thực sự lớn hơn x là đáp án.

Độ phức tạp: O(g√M), với g là khoảng cách từ N đến số phong phú kế tiếp.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
bool abundant(int64 x) {
    if (x < 12)
        return false;
    int64 s = 1;
    for (int64 d = 2; d * d <= x; d++)
        if (x % d == 0) {
            s += d;
            if (d * d != x)
                s += x / d;
            if (s > x)
                return true;
        }
    return s > x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 n;
    cin >> n;
    while (!abundant(n))
        ++n;
    cout << n;
}

Bài 2. XÓA TẬP TIN (5,0 điểm)

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

Hướng dẫn giải

Mã hóa mỗi tên tập tin thành mặt nạ 26 bit (bit c bật nếu tên có chữ c). Mỗi chữ cái chỉ cần xử lý ở lần xóa đầu tiên: khi đó quét các tập tin còn lại và xóa tập tin có bit tương ứng. Có tối đa 26 lần quét.

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<unsigned> m(n);
    for (auto &z : m) {
        string s;
        cin >> s;
        for (char c : s)
            z |= 1u << (c - 'a');
    }
    vector<char> alive(n, 1), used(26);
    int rem = n;
    while (q--) {
        char c;
        cin >> c;
        int b = c - 'a';
        if (!used[b]) {
            used[b] = 1;
            for (int i = 0; i < n; i++)
                if (alive[i] && (m[i] >> b & 1)) {
                    alive[i] = 0;
                    --rem;
                }
        }
        cout << rem << '\n';
    }
}

Bài 3. ĐƯỜNG ĐI (5,0 điểm)

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

Hướng dẫn giải

Quy hoạch động trên lưới: dp[j] là số đường đi đến ô đang xét ở cột j. Nếu ô bị chặn thì dp[j] = 0; ngược lại dp[j] = dp[j] (từ trên xuống) + dp[j − 1] (từ trái sang).

Số đường đi lớn nhất là C(98, 49) ≈ 2,5·10²⁸ (lưới 50 × 50 không có ô chặn), vượt 64 bit nhưng vẫn vừa __int128, nên dùng __int128 và tự viết hàm in.

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

#include <bits/stdc++.h>
using namespace std;
using i128 = __int128;
void print(i128 x) {
    if (x == 0) {
        cout << 0;
        return;
    }
    string s;
    while (x > 0)
        s += char('0' + x % 10), x /= 10;
    reverse(s.begin(), s.end());
    cout << s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    vector<i128> dp(n);
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == '1')
                dp[j] = 0;
            else if (i == 0 && j == 0)
                dp[j] = 1;
            else if (j)
                dp[j] += dp[j - 1];
        }
    }
    print(dp[n - 1]);
}

Bài 4. SỐ SIÊU NGUYÊN TỐ (5,0 điểm)

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

Hướng dẫn giải

Sinh trước mọi số siêu nguyên tố: bắt đầu từ 2, 3, 5, 7 và lần lượt nối thêm chữ số 1, 3, 7, 9; chỉ đi tiếp nhánh khi số mới vẫn nguyên tố. Nhờ vậy mọi số nhận được khi xóa dần chữ số cuối đều nguyên tố. Sinh đến 10¹² rồi đếm bằng lower_bound/upper_bound.

Độ phức tạp: Số lượng số siêu nguyên tố rất nhỏ; mỗi lần kiểm tra nguyên tố O(√x).

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
bool prime(ull n) {
    if (n < 2)
        return false;
    if (n % 2 == 0)
        return n == 2;
    for (ull d = 3; d <= n / d; d += 2)
        if (n % d == 0)
            return false;
    return true;
}
vector<ull> v;
void dfs(ull x) {
    if (x > 10)
        v.push_back(x);
    for (int d : {1, 3, 7, 9}) {
        if (x > (1000000000000ULL - d) / 10)
            continue;
        ull y = x * 10 + d;
        if (prime(y))
            dfs(y);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ull a, b;
    cin >> a >> b;
    for (int p : {2, 3, 5, 7})
        dfs(p);
    sort(v.begin(), v.end());
    cout << upper_bound(v.begin(), v.end(), b) - lower_bound(v.begin(), v.end(), a);
}

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

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