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
- Dùng thuật toán tham lam: lấy mệnh giá lớn nhất trước, càng nhiều tờ càng tốt, phần còn lại chuyển sang mệnh giá nhỏ hơn.
- Tham lam cho kết quả tối ưu ở đây vì mỗi mệnh giá lớn được ghép từ các mệnh giá nhỏ mà không tiết kiệm được tờ nào (500 = 2·200 + 100 là 3 tờ, nhiều hơn 1 tờ 500; 200 = 2·100; 100 = 2·50).
- Số tờ loại i:
n / menhGia[i]; số tiền còn lại:n % menhGia[i]. - Nên kiểm tra tính hợp lệ (đề nói máy ATM có quy tắc), nếu sai thì báo lỗi.
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.000 | 2 | 350.000 |
| 200.000 | 1 | 150.000 |
| 100.000 | 1 | 50.000 |
| 50.000 | 1 | 0 |
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
- Viết hàm
laNguyenTo(n): n < 2 thì không; còn lại thử chia cho i từ 2 đến √n (i*i <= n). Nếu có ước thì không nguyên tố. Lý do chỉ cần đến √n: nếu n = p·q thì một trong hai thừa số ≤ √n. - Duyệt i từ A đến B, số nào nguyên tố thì lưu vào mảng, đồng thời cộng vào tổng.
- Thứ tự in theo đề: số lượng → danh sách → tổng. Vì phải in số lượng trước nên cần lưu danh sách lại (dùng
vector). - Dùng
long longcho tổng để tránh tràn số.
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 ✔.
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.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).
TTT = TT % 26 (đề cũng ghi "Tìm số dư").Phân tích
- Chuỗi có dấu cách nên đọc bằng
getline(không dùngcin >>vì sẽ bị cắt ở dấu cách). Sau đó đọc K. - Với mỗi ký tự là chữ cái:
T = c - 'A',TTT = (T + K) % 26, ký tự mới là'A' + TTT. - K có thể rất lớn, dùng
long longhoặc rút gọnK %= 26trước để khỏi tràn số. - Nếu có chữ thường, làm tương tự với mốc
'a'để giữ nguyên kiểu 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ự | T | T + 7 | mod 26 | Mới |
|---|---|---|---|---|
| T | 19 | 26 | 0 | A |
| I | 8 | 15 | 15 | P |
| N | 13 | 20 | 20 | U |
| H | 7 | 14 | 14 | O |
| O | 14 | 21 | 21 | V |
| C | 2 | 9 | 9 | J |
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
- N < 10000 nên có tối đa 4 chữ số. Số cách chia hai nhóm rất ít, có thể vét cạn toàn bộ.
- Chuyển N thành xâu để lấy các chữ số theo thứ tự từ trái sang phải.
- Dùng mặt nạ bit
masktừ 1 đến 2d − 2 (d là số chữ số): chữ số thứ j thuộc nhóm 1 nếu bit j của mask bằng 1, ngược lại thuộc nhóm 2. Hai giá trị mask = 0 và mask = 2d − 1 bị loại vì có một nhóm rỗng. - Chỉ xét mask lẻ (chữ số đầu luôn thuộc nhóm 1) để không đếm trùng hai nhóm đổi chỗ, và biểu thức in ra có chữ số đầu ở vế trái, đúng như các ví dụ của đề.
- Tính tổng nhóm 1; nếu
2 × tổng nhóm 1 = tổng tất cả chữ sốthì hai nhóm bằng nhau. Gặp mask đầu tiên thỏa thì in và dừng. - Số 1 chữ số (kể cả 0) không chia được thành hai nhóm khác rỗng, nên không là số may mắn.
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ụ
| N | Tổng chữ số | Mask tìm được | Kết quả |
|---|---|---|---|
| 55 | 10 | 01 | 5 = 5 ✔ |
| 123 | 6 | 011 | 1 + 2 = 3 ✔ |
| 1982 | 20 | 0011 | 1 + 9 = 8 + 2 ✔ |
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.