Mã hóa Ceasar
Đề bài
Trước công nguyên, nhà quân sự người La Mã Julius Ceasar đã nghĩ ra phương pháp mã hóa một bản tin như sau: thay thế mỗi chữ trong bản tin bằng chữ đứng sau nó $k$ vị trí trong bảng chữ cái. Giả sử chọn $k = 3$, ta có bảng chuyển đổi như sau:
| Chữ ban đầu | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Chữ thay thế | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | a | b | c |
Giả sử bản tin là: 'attack' thì sau khi mã hóa sẽ có bản mã 'dwwdfn' và Ceasar gửi bản mã cho cấp dưới.
Nhận được bản mã và khóa, cấp dưới của Ceasar chưa biết giải mã làm sao. Bạn hãy giúp họ đi nào.
Dữ liệu vào:
- Dòng đầu tiên là bản tin đã được mã hóa, chỉ gồm các chữ cái la tinh thường, chiều dài không quá 100 ký tự.
- Dòng thứ 2 là số nguyên thể hiện khóa $k$ ($1 \le k \le 25$).
Dữ liệu ra: bản tin ban đầu.
wyvnyhttpun
7programmingLời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Các bạn nào muốn thử nộp bài để hệ thống chấm có đúng hay không thì link bài đây nha:
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên LuyenCodeLộ trình lời giải, bấm vào từng phần để nhảy tới:
Chuẩn bịGiới hạn 20 ms thì được lặp bao nhiêu lần?
Trước khi đi vào vấn đề chính của bài thì mình muốn các bạn phải đảm bảo biết qua điều này để về sau các bạn xem mới hiểu.
Với các hệ thống web chấm bài giới hạn thời gian chạy tối đa 1 giây thì các bạn sẽ rất dễ bị rơi vào lỗi Time Limit Exceeded (TLE: chạy quá giới hạn thời gian cho phép). Như mình đã nói rất nhiều lần: nếu không muốn bị TLE thì tối đa số phép toán trên toàn bài của các bạn chỉ nên ở ngưỡng $(3 \text{ đến } 5) \cdot 10^7$ – ngưỡng an toàn với phần lớn hệ thống chấm bài; với một số hệ thống server mạnh hơn thì có thể nâng lên $10^8$ nhưng cũng hên xui nhé.
Thực ra ta không phải đếm chi tiết từng phép toán mà dựa theo số lần vòng lặp chạy, bởi bên trong vòng lặp nó xử lý lặp đi lặp lại nhiều phép toán. Lưu ý ngưỡng trên là với C/C++ thôi nhé, các ngôn ngữ chạy chậm hơn như Python, C#, Java thì ngưỡng phải thấp hơn. Còn nếu đề cho 2 giây thì các bạn cứ tỷ lệ thuận nhân 2 lên, 3 giây thì nhân 3, 100 ms tức là $\frac{1}{10}$ giây thì chia 10, cứ thế thôi.
Bài này phải nói là nên ở mức dễ sẽ đúng hơn là mức trung bình, vì chuỗi chỉ dài tối đa 100 là quá nhỏ, dù cho cách làm tệ nhất vẫn không sợ bị chạy quá thời gian (tất nhiên nếu tệ quá mức thì vẫn bị nhé 🤪). Tuy nhiên chưa chắc bạn nào cũng giải quyết theo cách gọn gàng – mình đã xem qua code của bạn hỏi bài thì thấy bạn xử lý khá rườm rà phức tạp, nên ở đây mình sẽ hướng dẫn một cách rất gọn, các bạn chú ý nha.
Nền tảngKý tự thực chất là số nguyên (mã ASCII)
Để làm được bài này thì các bạn phải hiểu quy luật mã ASCII của các ký tự. Bản chất kiểu dữ liệu ký tự trong C/C++ chính là kiểu số nguyên, bởi các ký tự được quản lý thông qua mã ASCII của nó – có thể hiểu là "mã số" của ký tự. 26 chữ cái từ 'a' đến 'z' tương ứng với các số nguyên từ 97 đến 122: 97 là mã của 'a', 98 là mã của 'b', 99 là mã của 'c', ... đến 122 là mã của 'z'.
| Ký tự | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Mã ASCII | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 |
Ví dụ đoạn code sau:
#include <iostream>
using namespace std;
int main(){
char x = 'a';
cout << x << " " << (int)x;
return 0;
}x = 'a'
print(x, ord(x))Sẽ thấy kết quả in ra là: a 97.
Nếu trước dòng cout ta thêm câu lệnh x++; thì kết quả sẽ là b 98, vì $x$ đang là 97 được cộng thêm 1 thành 98, in ra giá trị $x$ lúc này chính là ký tự 'b'. Tương tự nếu x += 3; thì 97 + 3 = 100 là ký tự 'd'. Rồi từ 100 mà x -= 2 còn 98 thì in ra chính là 'b'. Các bạn chạy thử đoạn code sau:
#include <iostream>
using namespace std;
int main(){
char x = 'a';
x += 3;
cout << x << " " << (int)x << endl;
x -= 2;
cout << x << " " << (int)x;
return 0;
}x = 'a'
x = chr(ord(x) + 3)
print(x, ord(x))
x = chr(ord(x) - 2)
print(x, ord(x))Sẽ thấy kết quả in ra là:
d 100
b 98Đến đây thì các bạn đã hiểu quy luật thao tác với mã ASCII của các ký tự rồi hen. Nó chính là mấu chốt để ta giải quyết nhanh gọn bài này.
Ý tưởngLùi $k$ bước, tụt khỏi 'a' thì cộng 26
Nhìn lại cách mã hóa
Quy luật mã hóa là từ vị trí ký tự hiện tại cộng lên $k$ để lấy ra ký tự thay thế. Mã ASCII của các chữ cái chạy từ 97 ('a') đến 122 ('z'); cứ cộng lên $k$ nếu vượt quá 122 thì bắt đầu lại từ 97. Ví dụ ký tự đang xét là 'x' (mã 120) và $k = 4$ thì ký tự thay thế sẽ là 'b' (mã 98): $120 + 4 = 124$ đã vượt 122 nên trừ cho 122 được $124 - 122 = 2$; rồi do bắt đầu lại từ 'a' (mã 97) nên $2 + 97 - 1 = 98$. Ta phải $-1$ vì chính ký tự 'a' cũng được tính. Còn nếu cộng $k$ mà vẫn $\le 122$ thì quá khoẻ, cứ in ra ký tự có mã đó thôi.
Giải mã: làm ngược lại
Bài này muốn ta đi giải mã thì làm ngược lại thôi: ký tự hiện tại trừ đi $k$, nếu nhỏ hơn 97 (mã của 'a') thì bắt đầu lại từ 122 (mã của 'z') và lùi tiếp cho đủ. Ví dụ ngược lại với trường hợp trên: ký tự đang xét là 'b' (mã 98), $k = 4$ thì $98 - 4 = 94 < 97$, nghĩa là cần lùi thêm $97 - 94 = 3$ ký tự bắt đầu từ 'z': $122 - 3 = 119$, rồi nhớ $+1$ do tính luôn chính ký tự 'z' → kết quả là 120, mã của 'x'.
Vậy khi xét mã ASCII của ký tự $s[i] - k$ mà ra kết quả $< 97$ thì đáp án là ký tự có mã:
s[i] -= k; nếu kết quả nhỏ hơn 97 thì cộng thêm 26, rồi in ký tự có mã đó ra – đó chính là ký tự gốc. Còn nếu trừ $k$ mà vẫn $\ge 97$ thì cứ in ra luôn, khỏi phải nặng đầu tính quy luật gì cả.Bài này đơn giản ở chỗ $k$ tối đa chỉ 25 (nhỏ hơn 26 chữ cái), nên khi mã hóa hay giải mã thì cao lắm chỉ quay vòng 1 lần thôi: dù là 'a' (97) với $k = 25$ thì $97 - 25 = 72 < 97$, cộng 26 được 98 là 'b' – vẫn chỉ cần cộng 26 đúng 1 lần.
Minh hoạGiải mã từng ký tự
Em nhập bản mã (chữ thường) và khóa $k$ rồi bấm Tiếp để xem từng ký tự lùi $k$ bước trên bảng chữ cái, khi nào bị tụt khỏi 'a' thì quay vòng về cuối:
CodeGiải mã – O(N)
Source code các bạn tham khảo để nhìn thấy rõ với tất cả những gì mình đã phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
int k;
cin >> s >> k;
for(int i = 0; i < (int)s.length(); ++i){
s[i] -= k;
if(s[i] < 97){
s[i] += 26;
}
cout << s[i];
}
}s = input()
k = int(input())
for i in range(len(s)):
c = ord(s[i]) - k
if c < ord('a'):
c += 26
print(chr(c), end="")Đánh giá độ phức tạp của cách làm này:
Chuỗi dài tối đa 100 thì vòng lặp chỉ chạy 100 lần, yên tâm là nhỏ hơn rất nhiều so với ngưỡng $(6 \text{ đến } 10) \cdot 10^5$ của 20 ms mình nói đầu bài. Vậy cách làm này sẽ không bị TLE.
Mở rộngNếu $k$ rất lớn? Nếu đề bắt mã hóa?
Khi $k$ lên tới 100 triệu
Đến đây hết rồi nhưng đã lỡ làm bài này mình cũng nói luôn: giả sử có bài tương tự nhưng $k$ có thể vượt quá 25, ví dụ tối đa 100 triệu, nghĩa là có thể phải quay vòng bảng chữ cái rất nhiều lần chứ không phải tối đa 1 lần như bài hiện tại. Sẽ rất dở nếu bạn nào cứ lùi từng bước đủ $k$ lần, 100 triệu lần thì quá 1 giây luôn rồi chứ đừng nói 20 ms.
Nhưng tinh ý một chút: bảng chữ cái có 26 chữ, cứ lùi đủ 26 bước là quay về đúng chữ cũ. Nên ta chỉ cần lấy phần dư k %= 26, phần $\lfloor k / 26 \rfloor$ vòng trọn vẹn thì bỏ qua vì chẳng làm thay đổi gì, sau đó giữ nguyên bước xử lý như bài hiện tại. Ví dụ đang xét 'a' với $k = 26$ thì k %= 26 còn 0 – vẫn là 'a'; với $k = 27$ thì còn 1 – lùi 1 ký tự được 'z'.
cin >> s >> k;
k %= 26; // bỏ qua các vòng trọn vẹn, chỉ giữ phần dư
// ... phần còn lại giữ nguyên như code giải mã ở trênk %= 25; đúng phải là k %= 26 vì chu kỳ quay vòng bằng đúng số chữ cái (26). Mình đã sửa lại ở trên cho chuẩn.Nếu đề yêu cầu mã hóa thay vì giải mã
Lúc này làm như phân tích đầu tiên: xét mã ASCII của $s[i] + k$, nếu ra kết quả $> 122$ thì đáp án là ký tự có mã:
Nghĩa là xét đến ký tự $s[i]$ ta cứ cộng $k$, nếu kết quả lớn hơn 122 thì trừ đi 26 rồi in ký tự có mã đó ra; còn nếu vẫn $\le 122$ thì in ra luôn.
Code mã hóa (chiều ngược lại)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
int k;
cin >> s >> k;
for(int i = 0; i < (int)s.length(); ++i){
int c = s[i] + k;
if(c > 122){
c -= 26;
}
cout << (char)c;
}
}s = input()
k = int(input())
for c in s:
c = ord(c) + k
if c > ord('z'):
c -= 26
print(chr(c), end="")s[i] += k; rồi if(s[i] > 122) giống bản giải mã. Nhưng kiểu char chỉ chứa tối đa 127, mà 'z' + 25 = 147 sẽ bị tràn thành số âm, điều kiện > 122 sai luôn và in ra ký tự rác (ví dụ xyz với $k = 25$). Bản giải mã không gặp chuyện này vì trừ đi thì nhỏ nhất cũng là $97 - 25 = 72$. Nên ở code trên mình tính trong biến int c cho an toàn.
Nhận xét
Đăng nhận xét