Editorial for Mật Thư Của Lười
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: Nghaiz
Lời giải: Mật Thư Của Lười
Chủ đề: xử lý chuỗi (string), ord / chr, phép chia lấy dư
Tóm tắt đề
Bức thư đã được mã hóa bằng cách dịch mỗi chữ cái tới \(K\) vị trí (vòng tròn). Ta cần dịch lùi \(K\) vị trí để lấy lại thư gốc. Chữ hoa, chữ thường giữ nguyên kiểu; ký tự khác giữ nguyên.
Ý tưởng
Bước 1: rút gọn \(K\). Dịch \(26\) vị trí thì chữ cái quay về chính nó, nên dịch \(K\) vị trí giống hệt dịch K % 26 vị trí. Với \(K = 10^9\), ta chỉ cần dịch \(10^9 \bmod 26 = 12\) vị trí.
Bước 2: đổi chữ cái thành số và ngược lại. Hàm ord(ch) cho mã ASCII của ký tự, chr(x) làm điều ngược lại. Với chữ thường, ord(ch) - ord('a') là vị trí của chữ cái trong bảng (từ \(0\) đến \(25\)). Dịch lùi \(K\) vị trí theo vòng tròn:
vi_tri_moi = (ord(ch) - ord('a') - K) % 26
ch_moi = chr(ord('a') + vi_tri_moi)
Trong Python, phép % với số dương luôn cho kết quả không âm (ví dụ (-3) % 26 == 23), nên không cần tự xử lý trường hợp "lùi quá chữ a".
Bước 3: làm tương tự với chữ hoa (dùng 'A' làm gốc), ký tự khác giữ nguyên. Gom kết quả bằng "".join(...) rồi in ra.
Độ phức tạp
\(O(n)\) với \(n\) là độ dài bức thư.
Code mẫu
def giai_ma(ch, k):
if "a" <= ch <= "z":
goc = ord("a")
elif "A" <= ch <= "Z":
goc = ord("A")
else:
return ch
return chr(goc + (ord(ch) - goc - k) % 26)
k = int(input())
thu = input()
k %= 26
print("".join(giai_ma(ch, k) for ch in thu))
Comments