Khôi phục kênh nhiễu vũ trụ
Đề bài
Mô tả
Trong một chuyến bay khẩn cấp rời hành tinh ở Khu vực 2026, đặc vụ tiền đồn Alice phải truyền một xâu lệnh nhị phân bit tới mô-đun chỉ huy của Bob qua một kênh bức xạ vũ trụ không ổn định. Kênh truyền bị nhiễu hạt và có thể lật nhiều nhất bit (đổi 0 thành 1 hoặc 1 thành 0).
Để bảo vệ lệnh, trước khi phát, Alice mã hóa xâu gốc gồm bit thành một từ mã có độ dài (, ). Kênh truyền lật bit () và chuyển tới Bob từ mã đã bị nhiễu .
Khi nhận được , Bob phải hoàn thành các mục tiêu sau:
- Xác định chính xác số bit bị lật .
- Nếu hoặc , khôi phục chính xác xâu nhị phân gốc độ dài .
Chương trình của bạn sẽ được chạy hai lần trong mỗi test để đóng vai Bộ mã hóa (Alice) và Bộ giải mã (Bob), qua đầu vào chuẩn (stdin) và đầu ra chuẩn (stdout). Hai lần chạy là hai tiến trình độc lập: thông tin duy nhất Bob nhận được từ Alice là từ mã (sau khi bị lật bit). Các bit bị lật là vị trí phân biệt của do bộ dữ liệu quyết định (có thể là bất kỳ vị trí nào), Bob không biết đó là những vị trí nào.
Dữ liệu vào
Với lần chạy 1 (Alice, bộ mã hóa):
- Dòng 1 chứa xâu
first. - Dòng 2 chứa số nguyên , độ dài của xâu nhị phân gốc.
- Dòng 3 chứa xâu nhị phân độ dài (
01).
Với lần chạy 2 (Bob, bộ giải mã):
- Dòng 1 chứa xâu
second. - Dòng 2 chứa số nguyên .
- Dòng 3 chứa xâu nhị phân độ dài nhận được sau khi bị lật bit ().
Dữ liệu ra
Với lần chạy 1 (Alice):
- In đúng một dòng chứa từ mã nhị phân độ dài ().
Với lần chạy 2 (Bob):
- Dòng 1: in số nguyên , số bit bị lật mà Bob phát hiện được.
- Dòng 2 (chỉ khi hoặc ): in xâu nhị phân gốc độ dài đã khôi phục.
Một test được tính điểm khi và chỉ khi Bob xác định đúng và, khi , khôi phục đúng .
Ràng buộc
- (độ dài từ mã của Alice không được vượt quá ).
- Kênh truyền lật bit của .
- Mọi ký tự trong mọi xâu nhị phân đều là
0hoặc1.
Ví dụ
Mỗi dòng của bảng là một lần chạy chương trình. Từ mã phụ thuộc vào cách mã hóa của lời giải; bảng dưới đây là kết quả của một cách mã hóa đúng.
| Input | Output | Giải thích |
|---|---|---|
| first 4 1011 |
00110011 | Lần chạy 1 (Alice): mã hóa 4 bit thành 8 bit. Trong đề gốc, Alice in 10110101; đó là kết quả của một cách mã hóa khác, cũng hợp lệ nếu Bob dùng cùng cách. |
| second 4 00110001 |
1 1011 |
Lần chạy 2 (Bob) khi kênh lật 1 bit (bit thứ 7 tính từ trái): Bob phát hiện 1 bit bị lật và khôi phục 1011. |
| second 4 00110101 |
2 | Lần chạy 2 (Bob) khi kênh lật 2 bit (bit thứ 6 và thứ 7): Bob chỉ cần in 2. |
| first 3 110 |
0011110 | Lần chạy 1 (Alice) của một test khác. |
| second 3 1011110 |
1 110 |
Lần chạy 2 (Bob) của test thứ hai: kênh lật bit đầu tiên. |
Bình luận