Editorial for Mật Thư Của Lười


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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

There are no comments at the moment.