trang chủ / đề bài / icpc26_mb_m

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 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 2 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 S gồm n bit thành một từ mã T có độ dài m (n≤1000, m≤1024). Kênh truyền lật k bit (k∈{0,1,2}) và chuyển tới Bob từ mã đã bị nhiễu T′.

Khi nhận được T′, Bob phải hoàn thành các mục tiêu sau:

  1. Xác định chính xác số bit bị lật k∈{0,1,2}.
  2. Nếu k=0 hoặc k=1, khôi phục chính xác xâu nhị phân gốc S độ dài n.

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ã T (sau khi bị lật k bit). Các bit bị lật là k vị trí phân biệt của T 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 n, độ dài của xâu nhị phân gốc.
  • Dòng 3 chứa xâu nhị phân S độ dài n (Si∈{0, 1}).

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 n.
  • Dòng 3 chứa xâu nhị phân T′ độ dài m nhận được sau khi bị lật k bit (0≤k≤2).

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 T độ dài m (m≤1024).

Với lần chạy 2 (Bob):

  • Dòng 1: in số nguyên k∈{0,1,2}, số bit bị lật mà Bob phát hiện được.
  • Dòng 2 (chỉ khi k=0 hoặc k=1): in xâu nhị phân gốc S độ dài n đã khôi phục.

Một test được tính điểm khi và chỉ khi Bob xác định đúng k và, khi k≤1, khôi phục đúng S.

Ràng buộc

  • 1≤n≤1000
  • 1≤m≤1024 (độ dài từ mã m của Alice không được vượt quá 1024).
  • Kênh truyền lật k∈{0,1,2} bit của T.
  • Mọi ký tự trong mọi xâu nhị phân đều là 0 hoặc 1.

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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0