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

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

Bài 1. Ma trận đều (3,0 điểm)

Đề tóm tắt

Ma trận n×n là đều nếu tổng các phần tử của mỗi hàng và mỗi cột đều bằng nhau. Nhập n và ma trận, in kết quả kèm lý do.

Phân tích

Chương trình

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long hang[1005] = {0}, cot[1005] = {0};

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            long long x;
            cin >> x;
            hang[i] += x;   // cộng vào tổng hàng i
            cot[j]  += x;   // cộng vào tổng cột j
        }

    long long S = hang[0];
    bool deu = true;
    for (int i = 0; i < n; i++)
        if (hang[i] != S || cot[i] != S) { deu = false; break; }

    if (deu) {
        cout << "Dung ma tran deu" << endl;
        cout << "vi tong cac so hang theo tung hang hoac tung cot deu bang " << S;
    } else {
        cout << "Khong phai ma tran deu" << endl;
        cout << "vi tong cac so hang theo tung hang hoac tung cot khong bang nhau";
    }
    return 0;
}

Kiểm tra ví dụ 1

Hàng: 1+6+7 = 14, 2+7+5 = 14, 11+1+2 = 14. Cột: 1+2+11 = 14, 6+7+1 = 14, 7+5+2 = 14. Tất cả bằng 14, nên in "Dung ma tran deu … 14".
Ví dụ 2: hàng đầu 4+5+8 = 17, hàng hai 2+7+9 = 18, khác nhau nên "Khong phai ma tran deu".

Bài 2. Phân tích số (6,0 điểm)

Đề tóm tắt

Cho 0 < n ≤ 32000. Liệt kê mọi cách viết n thành tổng của từ hai số tự nhiên liên tiếp trở lên, rồi in tổng số cách. Không có thì in "khong co cach chia nao".

Ý tưởng

Giả sử tổng gồm k số liên tiếp (k ≥ 2), bắt đầu từ a (a ≥ 1):

n = a + (a+1) + … + (a+k-1) = k·a + k(k-1)/2

Suy ra a = (n - k(k-1)/2) / k. Với mỗi k, chỉ cần kiểm tra:

Vì a ≥ 1 nên k(k+1)/2 ≤ n, tức k chỉ chạy đến khoảng √(2n) ≈ 253 với n = 32000. Rất nhanh.

Duyệt k tăng dần thì kết quả in ra đúng thứ tự trong ví dụ (dãy ngắn trước, dài sau).

Chương trình

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int dem = 0;

    for (int k = 2; k * (k + 1) / 2 <= n; k++) {
        int t = n - k * (k - 1) / 2;      // = k * a
        if (t % k == 0) {                 // a là số nguyên
            int a = t / k;                // a >= 1 do điều kiện vòng for
            for (int i = 0; i < k; i++)
                cout << a + i << " ";
            cout << endl;
            dem++;
        }
    }

    if (dem == 0) cout << "khong co cach chia nao";
    else cout << "Co " << dem << " cach chia so " << n;
    return 0;
}

Kiểm tra n = 99

k99 − k(k−1)/2Chia hết k?aDãy
298có4949 50
396có3232 33 34
493không––
684có1414 … 19
963có77 … 15
1144có44 … 14

Tổng cộng 5 cách, khớp với ví dụ. Với n = 20 chỉ có k = 5 cho a = 2 (2 3 4 5 6), 1 cách.

Với n là lũy thừa của 2 (1, 2, 4, 8, 16, …) không có cách nào, chương trình sẽ in "khong co cach chia nao".

Bài 3. Giải mã tin nhắn (6,0 điểm)

Đề tóm tắt

Ý tưởng

  1. Tách tin nhắn: duyệt S, cộng dồn độ dài đoạn hiện tại; gặp # thì kết thúc một tin. Số tin = số dấu # + 1.
  2. Chọn tin dài nhất: ghi lại vị trí đầu bd và độ dài maxLen. Chỉ cập nhật khi độ dài lớn hơn hẳn (dấu >, không phải >=) để giữ tin đầu tiên khi bằng nhau.
  3. Giải mã: dịch ngược k vị trí: (c - 'A' - k) mod 26. Do kết quả % có thể âm nên cộng thêm 26 rồi lấy dư lần nữa. Nên rút gọn k = k % 26 trước vì k có thể rất lớn.

Chương trình

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

int main() {
    string s;
    int k;
    getline(cin, s);      // xâu có thể chứa dấu cách nên dùng getline
    cin >> k;
    k %= 26;

    int soTin = 1, bd = 0, maxLen = 0, start = 0;
    s += '#';             // thêm # cuối để xử lý tin cuối cùng cho gọn
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '#') {
            int len = i - start;
            if (len > maxLen) { maxLen = len; bd = start; }
            start = i + 1;
            if (i != (int)s.size() - 1) soTin++;   // # thật sự trong đề
        }
    }

    string kq = s.substr(bd, maxLen);
    for (char &c : kq) {
        if (isalpha(c)) {
            char u = toupper(c);
            c = 'A' + ((u - 'A' - k) % 26 + 26) % 26;
        }
    }

    cout << soTin << endl << kq;
    return 0;
}

Kiểm tra ví dụ 1: ABC#QBTDBM#123HG, k = 1

Ba tin: ABC (3), QBTDBM (6), 123HG (5). Dài nhất là QBTDBM. Giải mã lùi 1 chữ: Q→P, B→A, T→S, D→C, B→A, M→L, ra PASCAL. Số tin = 3. ✔

Lưu ý về ví dụ 2. Đề in qbt123#qbtdbm, k = 1 và đáp án 2 / PAS. Theo đúng quy tắc đề, hai tin qbt123 và qbtdbm cùng dài 6, lấy tin đầu và giữ nguyên chữ số, nên kết quả là PAS123, khác với "PAS" trong đề. Ví dụ này nhiều khả năng bị in sai hoặc chụp thiếu. Code ở trên làm theo đúng phát biểu của đề (số tin = 2, tin đầu tiên được chọn, đổi sang chữ in hoa như ví dụ). Nếu giáo viên xác nhận đáp án "PAS" là đúng thì có thể bỏ ký tự số khỏi kết quả bằng cách chỉ in các ký tự isalpha.

Bài 4. Tiền khách sạn (5,0 điểm)

Đề tóm tắt

Có n đơn đặt phòng (a, b, c): nhận phòng ngày a, trả phòng ngày b, trả c tiền. Chỉ có một phòng; khách trả phòng trước 12 giờ trưa, khách khác nhận phòng từ 12 giờ. Chọn tập đơn không chồng nhau sao cho tổng tiền lớn nhất.

Phân tích

Quy hoạch động

Gọi f[t] là số tiền lớn nhất khi chỉ xét các đơn có ngày trả phòng ≤ t (phòng được dọn xong trước ngày t).

Chương trình

#include <iostream>
using namespace std;

int a[12005], b[12005], c[12005];
long long f[105];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];

    f[0] = 0;
    for (int t = 1; t <= 100; t++) {
        f[t] = f[t - 1];                       // bỏ qua ngày t
        for (int i = 0; i < n; i++)
            if (b[i] == t)                     // đơn kết thúc đúng ngày t
                f[t] = max(f[t], f[a[i]] + c[i]);
    }

    cout << f[100];
    return 0;
}

Độ phức tạp: 100 × n ≤ 1,2 triệu phép tính, rất nhỏ.

Kiểm tra ví dụ 1

Đơn: (1,2,8), (2,3,6), (4,7,6).

tf[t]Giải thích
10không có đơn kết thúc
28f[1] + 8
314f[2] + 6
4–614giữ nguyên
720f[4] + 6 = 14 + 6

Kết quả 20 ✔.

Kiểm tra ví dụ 2

Đơn: (1,4,5), (1,3,8), (3,5,4), (4,6,9). f[3] = 8; f[4] = max(8, f[1] + 5) = 8; f[5] = max(8, f[3] + 4) = 12; f[6] = max(12, f[4] + 9) = 17. Kết quả 17 ✔ (chọn đơn 2 và đơn 4).

Ghi chú: nếu dùng a ≥ b_trước sai thành a > b_trước thì ví dụ 1 chỉ ra 14 chứ không phải 20. Đây chính là chi tiết "trả trước 12 giờ, nhận từ 12 giờ" của đề.

Mẹo làm bài: đề thi thường dùng đúng ví dụ để chấm, hãy luôn tự chạy tay các ví dụ như trên trước khi nộp.