Bài 37.9. Giải Mã Thông Điệp Cổ Xưa - [Độ khó: Khó]

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 64M

Author:

Problem type

Bài 37.9. Giải Mã Thông Điệp Cổ Xưa - [Độ khó: Khó]

Bạn tìm thấy một bản ghi cổ xưa được mã hóa bằng một phương pháp kỳ lạ. Mỗi chữ cái trong thông điệp gốc được thay thế bằng một chữ cái khác theo một quy tắc dịch chuyển phức tạp, không phải là Caesar đơn giản. Cụ thể, mỗi chữ cái X trong thông điệp gốc sẽ được thay thế bằng chữ cái thứ k sau nó trong bảng chữ cái (ví dụ: 'A' -> 'C' nếu k=2). Nếu dịch chuyển vượt quá 'Z' hoặc 'z', nó sẽ quay lại từ 'A' hoặc 'a'. Số bước dịch chuyển k không cố định, mà được lấy từ một chuỗi số shift_key cho trước. Ví dụ, nếu shift_key là "123", thì ký tự đầu tiên dịch 1 bước, ký tự thứ hai dịch 2 bước, ký tự thứ ba dịch 3 bước, ký tự thứ tư lại dịch 1 bước, và cứ thế. Các ký tự không phải chữ cái (số, ký tự đặc biệt, khoảng trắng) không bị dịch chuyển.

INPUT FORMAT

Dòng đầu tiên là chuỗi message (đã mã hóa). Độ dài của message không quá 200 ký tự. Dòng thứ hai là chuỗi shift_key (chỉ chứa các chữ số '0'-'9'). Độ dài của shift_key không quá 10 ký tự.

OUTPUT FORMAT

In ra chuỗi thông điệp gốc sau khi giải mã.

Ví dụ:

Input:

CpswJ
123

Output:

Hello

Giải thích:

message = "CpswJ", shift_key = "123"
Để giải mã, ta dịch ngược lại. Chuyển shift_key thành các bước dịch ngược: 1 -> -1, 2 -> -2, 3 -> -3.
Ký tự 'C': dịch ngược 1 bước (-1). 'C' -> 'B'. Không đúng.
- À, đề bài là dịch chuyển k bước. Khi giải mã, ta phải trừ đi k bước.
- 'C' (ASCII 67), shift '1' (value 1). 'C' - 1 = 'B'. Không đúng.
- Có lẽ là dịch chuyển tiến chứ không phải dịch chuyển lùi. "CpswJ" là sau khi dịch chuyển. Ta cần tìm trước khi dịch chuyển.
- message = "CpswJ", shift_key = "123".
- C (ký tự đầu tiên): dịch shift_key[0] = 1 bước.
  - 'C' - 1 = 'B'. Sai rồi. Chắc chắn là dịch "C" -> "B" thì nó ra "Hello"
  - 'H' (8) -> 'C' (3) nếu dịch 1 bước? Không, dịch 1 bước là H->I.
  - Bài toán "giải mã" tức là từ CpswJ ta muốn về Hello.
  - C -> H: Dịch chuyển H lên C là -5. Tức là C sang H là +5.
  - p -> e: Dịch chuyển e lên p là +11.
  - s -> l: Dịch chuyển l lên s là +7.
  - Vậy quy tắc dịch chuyển là k bước. C là kết quả của việc dịch H đi k_0 bước. p là kết quả của việc dịch e đi k_1 bước.
  - Nếu shift_key là 1, 2, 3:
    - 'H' dịch 1 bước (H -> I) -> 'I'
    - 'e' dịch 2 bước (e -> g) -> 'g'
    - 'l' dịch 3 bước (l -> o) -> 'o'
    - 'l' dịch 1 bước (l -> m) -> 'm'
    - 'o' dịch 2 bước (o -> q) -> 'q'
  - Vậy "Hello" -> "Igomq" với key "123".
  - Đề bài này cần phải rõ ràng hơn: "Giải mã tin nhắn với quy tắc dịch chuyển phức tạp" -> tức là tôi nhận CpswJ và 123, tôi muốn output Hello. Điều này có nghĩa là mỗi kí tự c trong CpswJ là kết quả của c_original + shift_value. Vậy để giải mã, ta cần c_original = c - shift_value.
message = "CpswJ", shift_key = "123".
shift_key được dùng lặp lại: 1, 2, 3, 1, 2, 3, ...
Ký tự 1: 'C'. shift_value = shift_key[0] = '1'. Chuyển 'C' lùi 1 vị trí. 'C' -> 'B'. (Chưa đúng với "Hello" - H).
Ký tự 2: 'p'. shift_value = shift_key[1] = '2'. Chuyển 'p' lùi 2 vị trí. 'p' -> 'n'. (Chưa đúng với "Hello" - e).

Tạm dừng: Ví dụ này có vẻ không khớp với định nghĩa "dịch chuyển k bước" và "giải mã". Nếu "dịch chuyển k bước" nghĩa là 'A' -> 'C' với k=2, thì 'H' -> 'J' với k=2. Nếu input là "CpswJ" và output là "Hello", thì 'C' phải là kết quả của một 'H' dịch chuyển 'k' bước, tức là 'H' + k = 'C'. Vậy k = 'C' - 'H' = -5. Nhưng shift_key là 1, 2, 3.

Giải thích lại ví dụ cho đúng logic: "mỗi chữ cái X trong thông điệp gốc sẽ được thay thế bằng chữ cái thứ k sau nó". Tức là encoded_char = original_char + k. Để giải mã, original_char = encoded_char - k.

shift_key là "123". Số bước dịch là s_i = shift_key[i % len(shift_key)] - '0'.
Ký tự 1: 'C'. s_0 = 1. 'C' - 1 = 'B'. ('B' là ký tự thứ 2, 'A' là thứ 1).
Ký tự 2: 'p'. s_1 = 2. 'p' - 2 = 'n'.
Ký tự 3: 's'. s_2 = 3. 's' - 3 = 'p'.
Ký tự 4: 'w'. s_3 = s_0 = 1. 'w' - 1 = 'v'.
Ký tự 5: 'J'. s_4 = s_1 = 2. 'J' - 2 = 'H'.

Output theo logic này sẽ là "Bn p vH". Vậy ví dụ "CpswJ" -> "Hello" là không chính xác với quy tắc dịch và giải mã thông thường của Vigenere/Caesar.

Cần sửa lại ví dụ hoặc định nghĩa dịch chuyển để khớp. Giả sử quy tắc dịch là: nếu shift_key[i] là '1', thì 'A' -> 'Z', 'B' -> 'A', ... (dịch lùi 1). Nếu shift_key[i] là '2', thì 'A' -> 'Y', 'B' -> 'Z', ... (dịch lùi 2). Tức là, original_char = encoded_char + shift_value. (Nếu shift_value là số nguyên từ 0-25). VD: 'H' (7) -> 'C' (2). 'C' - 'H' = -5. Mod 26: -5 + 26 = 21. Tức là dịch 21 bước. Nếu shift_key là "123", và nó ám chỉ dịch chuyển tiến 1, 2, 3 bước. Thì để CpswJ ra Hello, ta cần dịch chuyển ngược lại. 'C' -> 'H': ngược 5. 'p' -> 'e': ngược 11. 's' -> 'l': ngược 7. 'w' -> 'l': ngược 11. 'J' -> 'o': ngược 5. Các giá trị 5, 11, 7, 11, 5... không liên quan đến 1, 2, 3.

Kết luận: Ví dụ của tôi bị sai. Tôi sẽ sửa nó để khớp với định nghĩa "mỗi chữ cái X trong thông điệp gốc sẽ được thay thế bằng chữ cái thứ k sau nó" và "giải mã" là làm ngược lại.

Sửa ví dụ để khớp logic: Giả sử thông điệp gốc là "HELLO", shift_key là "123".

'H' dịch 1 bước ('1'): H -> I.
'E' dịch 2 bước ('2'): E -> G.
'L' dịch 3 bước ('3'): L -> O.
'L' dịch 1 bước ('1'): L -> M.
'O' dịch 2 bước ('2'): O -> Q. Kết quả mã hóa: "IGOMQ". Vậy, nếu input là "IGOMQ" và shift_key là "123", output phải là "HELLO".

Sửa lại phần Giải thích và Ví dụ: