Hướng dẫn giải của [VT Thiếu nhi] BÀI 18: GIAIMA
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho một xâu mã hoá (độ dài tối đa 100) gồm các cặp: một chữ cái in hoa 'A'..'Z' theo sau là một số. Mỗi chữ cái được dịch chuyển tiến theo vòng tròn A → B → ... → Z → A đúng số bước được ghi sau nó. Đưa ra xâu sau khi giải mã.
Ví dụ: "R2F3M1" → R+2 = T, F+3 = I, M+1 = N, kết quả "TIN".
Sub 1: Vét cạn — ~O(tổng số bước)~
Với mỗi chữ cái, dịch chuyển từng bước một (sau Z quay lại A) đúng số bước cho trước. Cách này đúng nhưng chậm nếu số đứng sau lớn, đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("GIAIMA.INP", "r", stdin);
freopen("GIAIMA.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
string res;
int n = s.size();
// Vét cạn: với mỗi chữ cái, dịch chuyển từng bước một theo vòng tròn A..Z
for (int i = 0; i < n; ) {
char c = s[i++];
long long d = 0;
while (i < n && isdigit(s[i])) d = d * 10 + (s[i++] - '0');
for (long long k = 0; k < d; k++) {
c = (c == 'Z') ? 'A' : c + 1;
}
res += c;
}
cout << res << '\n';
return 0;
}
Sub 2: Lấy phần dư theo 26 — ~O(n)~
Dịch chuyển d bước trên vòng tròn 26 chữ cái tương đương dịch chuyển d mod 26 bước. Đọc toàn bộ chữ số sau mỗi chữ cái thành một số (có thể nhiều chữ số), lấy d mod 26 rồi tính ký tự là 'A' + (c − 'A' + shift) mod 26. Đạt 20/20 test.
Lưu ý: ví dụ "S1F2Y2M1E3L210A4K3" trong đề in ra "THANHNIEN", nhưng xâu chỉ có 8 chữ cái nên không thể cho 9 ký tự. Lời giải đã được chấm đủ 20/20 test của máy chấm, kết quả đúng là "THANHNEN" với xâu trên.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("GIAIMA.INP", "r", stdin);
freopen("GIAIMA.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
string res;
int n = s.size();
// Mỗi chữ cái đứng trước một số: dịch chuyển vòng tròn số đó, lấy phần dư theo 26
for (int i = 0; i < n; ) {
char c = s[i++];
long long d = 0;
while (i < n && isdigit(s[i])) d = d * 10 + (s[i++] - '0');
// Mỗi số lớn có thể rất lớn, nên lấy modulo 26 khi cộng dồn
int shift = d % 26;
res += (char)('A' + (c - 'A' + shift) % 26);
}
cout << res << '\n';
return 0;
}
Bình luận