Gửi tin với máy truyền tin bị hỏng

Alice và Bob là một cặp đôi yêu xa bởi Alice phải làm việc trong một khu rừng bí ẩn, cách biệt hoàn toàn với thành phố nơi Bob sinh sống. Hằng ngày, Alice đều muốn gửi tới Bob những bức thông điệp ngập tràn yêu thương. Tuy nhiên, máy truyền tin của Alice đã bị hỏng do ở lâu ngày trong rừng, nhiều vi mạch đã bị chập vì độ ẩm cao. May thay, máy truyền tin không phải bị hỏng hoàn toàn mà chỉ làm sai lệch dữ liệu trong quá trình truyền tín hiệu. Cơ chế hoạt động của chiếc máy truyền tin như sau:

• Khi Alice muốn gửi một từ (là một chuỗi các chữ cái tiếng Anh), cô phải tự mã hóa từ đó thành một chuỗi nhị phân gồm n chữ số 0 hoặc 1 rồi nạp vào máy truyền tin để phát sóng, biết rằng máy truyền tin này có đúng $n$ vị trí phát sóng.
• Máy truyền tin nhận chuỗi nhị phân, nếu không bị hỏng hóc thì về nguyên tắc sẽ gửi chính xác chuỗi nhị phân đó đến Bob. Tuy nhiên, do bị chập mạch nên một số bit trong chuỗi nhị phân sẽ không thể truyền đi bình thường mà mặc định luôn phát tín hiệu là bit 0, bất kể giá trị gốc của bit đó là 0 hay 1. Tất nhiên, bằng một cách nào đó, Alice luôn biết trước các vị trí bit bị lỗi này trước khi truyền tin.
• Sau khi gửi xong một chuỗi, các vị trí bit bị lỗi của máy truyền tin có thể thay đổi khi truyền chuỗi tiếp theo.

Bob ở thành phố nên máy thu của Bob hoạt động hoàn hảo và không bị lỗi như máy của Alice. Vấn đề đặt ra là khi nhận tín hiệu, Bob cần một đoạn mã để giải mã chính xác thông điệp của Alice, ngay cả khi các bit nhận được đã bị biến đổi. Do đó, Alice và Bob cần bạn hỗ trợ thiết kế phương pháp mã hóa cho Alice và đoạn mã giải mã cho Bob để họ có thể liên lạc thuận tiện. Yêu cầu: đoạn mã giải mã phải được viết bằng Python, có độ dài không quá 1000 ký tự, không sử dụng bất kỳ thư viện nào và phải giải mã chính xác tất cả các chuỗi mà Alice muốn gửi. Hãy giúp họ nhé!

Đầu vào:

• Dòng đầu tiên chứa hai số nguyên $m \; (1 \leq m \leq 1000)$ và $n \; (1 \leq n \leq 200)$, lần lượt biểu diễn số lượng chuỗi ký tự mà Alice muốn gửi và số lượng vị trí phát sóng (tức độ dài chuỗi nhị phân mà Alice mã hóa).
• $2 \times m$ dòng tiếp theo chứa thông tin các lần Alice gửi chuỗi chữ cái, cụ thể:
  • Dòng thứ $2 \times i$ chứa chuỗi chữ cái thứ $i$ mà Alice muốn gửi. Chuỗi này có thể gồm các chữ cái in hoa hoặc in thường, mỗi chuỗi có độ dài từ 1 đến 10 ký tự.
  • Dòng thứ $2 \times i + 1$ chứa các số nguyên biểu diễn số lượng và vị trí các bit bị lỗi trong máy phát khi gửi chuỗi thứ $i$. Số nguyên đầu tiên k_i là số lượng bit bị lỗi, theo sau là k_i số nguyên biểu diễn các vị trí bị lỗi $x_{i,j}$. Biết rằng $0 \leq k_i \leq n, \; 0 \leq k_i \leq 70$ và $1 \leq x_{i,j} < x_{i, j+1} \leq n,\; 1 \leq j \leq k_i$.

Ràng buộc

• 20% số testcase thỏa mãn tất cả $k_i = 1$ và $n = 120$.
• 20% số testcase thỏa mãn tất cả $k_i \leq 2,\; n \geq 175$.
• 30% số testcase thỏa mãn tất cả $2 < k_i \leq 40,\; n = 200$.
• 30% số testcase còn lại luôn thỏa mãn $3 \times (k_i + 58) \leq 2 \times n$.

Đầu ra:

• m dòng đầu tiên là các chuỗi nhị phân mà Alice mã hóa từ các chuỗi ký tự muốn gửi. Lưu ý rằng các chuỗi nhị phân này có thể bị biến đổi như mô tả khi Bob nhận được.
• Các dòng tiếp theo là đoạn mã giải mã dành cho Bob. Đoạn mã này phải chứa hàm tên là GiaiMa(x) được định nghĩa bằng Python theo định dạng sau, trong đó x là chuỗi nhị phân mà Bob nhận được và giá trị trả về là chuỗi ký tự sau khi giải mã:

def GiaiMa(x):
	...
  return ...

Quy ước: ký tự tab có thể được biểu diễn bằng 2 dấu cách.

Đoạn mã được chạy một lần, sau đó hàm GiaiMa được gọi lần lượt cho cả m chuỗi mà Bob nhận được; tổng thời gian cho việc này không quá 1 giây. Giới hạn 1000 ký tự tính mọi ký tự sau m dòng đầu (kể cả dấu cách và xuống dòng). Đoạn mã không được chứa chữ import ở bất kỳ đâu và không được dùng eval, exec, compile, exit, quit.

Giải thích: Quan sát testcase ví dụ, ta thấy trong toàn bộ quá trình truyền tin, chỉ có bit ở vị trí thứ 1 và thứ 26 bị lỗi, do đó Alice chỉ cần không dùng 2 bit này để truyền dữ liệu. Vì số lượng chữ cái in hoa và in thường tối đa là 52, Alice chỉ cần sử dụng 6 bit để mã hóa mỗi ký tự:

• a: 000001
• ...
• z: 011010
• A: 011011
• ...
• Z: 110100

Đoạn mã giải mã sẽ dựa trên phương pháp mã hóa trên để khôi phục lại chuỗi ban đầu.

Lưu ý rằng đoạn mã trong ví dụ chỉ giải quyết trường hợp đặc biệt của ví dụ này, không giải quyết được tất cả các trường hợp của bài toán.

Ví dụ 1:

Đầu vào:

3 120
I
0
Love
1 1
You
1 26

Đầu ra:

010001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
010011000111101011000010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
011001100111101010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

def binToChar(binary):
    sum = 0
    for b in binary:
        sum = sum * 2 + ord(b) - ord('0')
    if sum == 0:
        return ''
    if sum <= 26:
        return chr(ord('a')+sum-1)
    if sum <= 52:
        return chr(ord('A')+sum-27)
def GiaiMa(x):
    i = 1
    s = ""
    while i <= len(x) - 6:
        s = s + str(binToChar(x[i:i+6]))
        i += 6
    return s