Khôi Phục Chuỗi Nhị Phân Qua Khoảng Cách Hamming
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — chuỗi bí mật $S$ được cho trước).
Có một chuỗi nhị phân bí mật $S$ độ dài $N$. Mỗi lần hỏi, bạn gửi một chuỗi nhị phân $Q$ độ dài $N$ và nhận lại khoảng cách Hamming $H(Q, S)$ (số vị trí khác nhau giữa $Q$ và $S$). Chiến lược chuẩn dùng đúng $N$ lần hỏi (nếu $N=1$ dùng 1 lần hỏi) như sau:
- Lần hỏi 1: gửi chuỗi toàn số
0(00...0), nhận được $d_0 = H(00\dots0, S)$. - Với mỗi $i = 1, 2, \dots, N-1$: gửi chuỗi có duy nhất ký tự thứ $i$ là
1, còn lại là0, nhận được $d_i$. Từ $d_0$ và $d_i$, ta suy ra bit thứ $i$ của $S$ (nếu $d_i < d_0$ thì bit $i$ là1, ngược lại là0). - Bit thứ $N$ được suy ra trực tiếp từ $d_0$ và $N-1$ bit đầu mà không cần hỏi thêm.
Hãy mô phỏng các giá trị phản hồi $d_0, d_1, \dots, d_{N-1}$ mà máy chấm trả về và chuỗi $S$ khôi phục được.
Dữ liệu vào
- Dòng đầu ghi số nguyên $N$ ($1 \le N \le 1000$).
- Dòng thứ hai ghi chuỗi nhị phân $S$ độ dài $N$.
Dữ liệu ra
- Dòng đầu ghi $N$ số nguyên $d_0, d_1, \dots, d_{N-1}$ (cách nhau bởi dấu cách).
- Dòng thứ hai ghi chuỗi $S$ khôi phục được.
Ví dụ
| Input | Output |
|---|---|
| 4 1011 |
3 2 4 2 1011 |
Giới hạn
- $1 \le N \le 1000$
Community Discussion