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
- Dùng hai mảng:
hang[i]= tổng hàng i,cot[j]= tổng cột j. - Khi đọc phần tử
aở vị trí (i, j) thì cộng ngay vàohang[i]vàcot[j], không cần lưu cả ma trận. - Lấy
S = hang[0]làm chuẩn. Nếu có bất kỳ hàng hoặc cột nào khác S thì không đều. - Độ phức tạp: O(n²).
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:
n - k(k-1)/2chia hết cho k, vàa ≥ 1.
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
| k | 99 − k(k−1)/2 | Chia hết k? | a | Dãy |
|---|---|---|---|---|
| 2 | 98 | có | 49 | 49 50 |
| 3 | 96 | có | 32 | 32 33 34 |
| 4 | 93 | không | – | – |
| 6 | 84 | có | 14 | 14 … 19 |
| 9 | 63 | có | 7 | 7 … 15 |
| 11 | 44 | có | 4 | 4 … 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.
Bài 3. Giải mã tin nhắn (6,0 điểm)
Đề tóm tắt
- Xâu S (1 ≤ |S| ≤ 255) chứa nhiều tin nhắn ngăn cách bởi
#. - Mã hóa: mỗi chữ cái được thay bằng chữ đứng sau nó k vị trí (xoay vòng); ký tự khác chữ cái giữ nguyên.
- Tin cần tìm là tin dài nhất; nếu bằng nhau lấy tin xuất hiện đầu tiên.
- Xuất: số lượng tin nhắn và tin đã giải mã.
Ý tưởng
- 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. - Chọn tin dài nhất: ghi lại vị trí đầu
bdvà độ dàimaxLen. 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. - 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ọnk = k % 26trướ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. ✔
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
- Đơn i chiếm các đêm
a, a+1, …, b-1(ngày b trả phòng buổi sáng), tức khoảng nửa mở[a, b). - Hai đơn không chồng nhau khi
a_sau ≥ b_trước(được phép bằng nhau, vì trả sáng, nhận chiều). - Đây là bài lập lịch có trọng số (weighted interval scheduling). Vì ngày chỉ từ 1 đến 100 nên dùng quy hoạch động theo ngày rất gọn.
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).
f[t] = f[t-1](không nhận đơn nào kết thúc ở ngày t), hoặcf[t] = f[a] + cvới mỗi đơn cób = t(nhận đơn đó, phần trước chỉ được dùng các đơn kết thúc ≤ a).- Lấy giá trị lớn nhất. Đáp số là
f[100].
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).
| t | f[t] | Giải thích |
|---|---|---|
| 1 | 0 | không có đơn kết thúc |
| 2 | 8 | f[1] + 8 |
| 3 | 14 | f[2] + 6 |
| 4–6 | 14 | giữ nguyên |
| 7 | 20 | f[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).
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.