Khôi Phục Chuỗi Nhị Phân Qua Khoảng Cách Hamming

Buổi 63 — Interactive & Constructive
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved