Lời giải đề thi Tin học – HSG THCS tỉnh Kiên Giang 2024-2025

Ngôn ngữ: C++. Ngày thi 14/3/2025 – 150 phút – 4 bài (3 + 6 + 6 + 5 = 20 điểm).

Bài 1. Rút tiền (3,0 điểm)

Đề tóm tắt

Rút tối đa 5.000.000đ, là bội của 50.000đ, dùng các mệnh giá 500.000 – 200.000 – 100.000 – 50.000 sao cho số tờ ít nhất. In tổng số tờ và số tờ từng loại.

Phân tích

Chương trình

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n <= 0 || n > 5000000 || n % 50000 != 0) {
        cout << "So tien khong hop le";
        return 0;
    }

    int menhGia[4] = {500000, 200000, 100000, 50000};
    int soTo[4], tong = 0;

    for (int i = 0; i < 4; i++) {
        soTo[i] = n / menhGia[i];   // số tờ tối đa của mệnh giá này
        n %= menhGia[i];            // số tiền còn lại
        tong += soTo[i];
    }

    cout << tong << endl;
    for (int i = 0; i < 4; i++) cout << soTo[i] << endl;
    return 0;
}

Kiểm tra n = 1 350 000

Mệnh giáSố tờCòn lại
500.0002350.000
200.0001150.000
100.000150.000
50.00010

Tổng 2 + 1 + 1 + 1 = 5 tờ. In ra 5, 2, 1, 1, 1 ✔.

Bài 2. Số nguyên tố (6,0 điểm)

Đề tóm tắt

Cho 0 < A < B. In số lượng, danh sách và tổng các số nguyên tố trong đoạn [A, B].

Phân tích

Chương trình

#include <iostream>
#include <vector>
using namespace std;

bool laNguyenTo(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

int main() {
    long long A, B;
    cin >> A >> B;

    vector<long long> ds;
    long long tong = 0;
    for (long long i = A; i <= B; i++)
        if (laNguyenTo(i)) {
            ds.push_back(i);
            tong += i;
        }

    cout << ds.size() << endl;
    for (size_t i = 0; i < ds.size(); i++) cout << ds[i] << " ";
    cout << endl << tong;
    return 0;
}

Kiểm tra A = 6, B = 22

Các số nguyên tố trong [6, 22]: 7, 11, 13, 17, 19. Số lượng 5, tổng 7 + 11 + 13 + 17 + 19 = 67 ✔.

Lưu ý về đề. Ví dụ trong đề in dãy 7 11 13 15 17 19, nhưng 15 = 3·5 không phải số nguyên tố. Số lượng 5 và tổng 67 chỉ khớp khi không có 15, nên đây là lỗi đánh máy của đề. Chương trình trên in 7 11 13 17 19.
Nếu đoạn [A, B] rất lớn (hàng triệu số) thì nên dùng sàng Eratosthenes thay cho thử chia. Đề không nêu giới hạn nên cách thử chia là đủ.

Bài 3. Mã hóa văn bản (6,0 điểm)

Đề tóm tắt

Mã hóa Caesar: mỗi chữ cái có số thứ tự T (A = 0, …, Z = 25) được đổi thành chữ có số thứ tự (T + K) mod 26. Ký tự khác chữ cái giữ nguyên (ví dụ mẫu giữ nguyên @, dấu cách, 2025).

Đề viết "TTT = TT/26" nhưng ý đúng là số dư của phép chia, tức TTT = TT % 26 (đề cũng ghi "Tìm số dư").

Phân tích

Chương trình

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int main() {
    string s;
    long long K;
    getline(cin, s);
    cin >> K;
    K %= 26;                       // đủ dùng vì (T + K) mod 26 lặp theo chu kỳ 26

    for (size_t i = 0; i < s.size(); i++) {
        char c = s[i];
        if (isupper(c))
            s[i] = 'A' + (c - 'A' + K) % 26;
        else if (islower(c))
            s[i] = 'a' + (c - 'a' + K) % 26;
        // ký tự khác: giữ nguyên
    }
    cout << s;
    return 0;
}

Kiểm tra: @ TIN HOC 2025 @, K = 7

Ký tựTT + 7mod 26Mới
T19260A
I81515P
N132020U
H71414O
O142121V
C299J

Kết quả: @ APU OVJ 2025 @ ✔.

Bài 4. Số may mắn (5,0 điểm)

Đề tóm tắt

Số N (< 10000) là "may mắn" nếu các chữ số chia được thành hai nhóm có tổng bằng nhau. In "La so may man" và biểu thức, hoặc "Khong la so may man".

Phân tích

Chương trình

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;
    string s = to_string(N);
    int d = s.size();

    int tong = 0;
    for (int j = 0; j < d; j++) tong += s[j] - '0';

    for (int mask = 1; mask < (1 << d) - 1; mask++) {
        if (!(mask & 1)) continue;          // chữ số đầu luôn ở nhóm 1

        int t1 = 0;
        for (int j = 0; j < d; j++)
            if (mask & (1 << j)) t1 += s[j] - '0';

        if (t1 * 2 == tong) {
            cout << "La so may man" << endl;
            string g1 = "", g2 = "";
            for (int j = 0; j < d; j++) {
                string &g = (mask & (1 << j)) ? g1 : g2;
                if (!g.empty()) g += " + ";
                g += s[j];
            }
            cout << g1 << " = " << g2;
            return 0;
        }
    }
    cout << "Khong la so may man";
    return 0;
}

Kiểm tra ví dụ

NTổng chữ sốMask tìm đượcKết quả
5510015 = 5 ✔
12360111 + 2 = 3 ✔
19822000111 + 9 = 8 + 2 ✔
Lưu ý về ví dụ 2024. Đề ghi 2024 là "Khong la so may man", nhưng theo định nghĩa của đề thì 2024 có chia được: 2 + 2 = 0 + 4 (cũng có 2 + 0 + 2 = 4). Chương trình trên theo đúng định nghĩa nên sẽ in La so may man và 2 + 2 = 0 + 4. Ví dụ này nhiều khả năng sai trong đề (hoặc đề có điều kiện ngầm về chữ số 0 mà không nói rõ). Em nên hỏi lại giáo viên để thống nhất; nếu muốn khớp ví dụ, có thể thêm điều kiện loại bỏ chữ số 0 trước khi chia nhóm.

Mẹo làm bài: tự chạy tay từng ví dụ như trên trước khi nộp; khi ví dụ của đề mâu thuẫn với phát biểu, hãy làm theo phát biểu và ghi chú lại nhận xét của mình.