Năm ngoái, một liên minh nghiên cứu đã gặp một số rắc rối với một hệ cơ sở dữ liệu phân tán đôi khi làm mất một phần dữ liệu. Bạn không cần đọc hay hiểu bài toán đó để giải bài này!

Liên minh nhận thấy các hệ thống phân tán quá phức tạp, nên họ lưu \(B\) bit thông tin quan trọng trong một mảng duy nhất trên một cỗ máy tuyệt vời. Để tăng thêm một lớp bảo mật, họ khiến việc lấy thông tin thật nhanh trở nên khó khăn: người dùng phải truy vấn một vị trí bit từ \(1\) đến \(B\), rồi mới nhận được bit tại vị trí đó trong mảng đang lưu.

Đáng tiếc, cỗ máy siêu hiện đại này chịu ảnh hưởng của các dao động lượng tử ngẫu nhiên! Cụ thể, sau khi gửi mỗi truy vấn thứ \(1, 11, 21, 31, \ldots\), nhưng trước khi nhận được phản hồi, dao động lượng tử gây ra đúng một trong bốn hiệu ứng sau, mỗi hiệu ứng có xác suất như nhau:

• Với xác suất \(25\%\), mảng bị bù bit: mọi 0 trở thành 1 và ngược lại.
• Với xác suất \(25\%\), mảng bị đảo ngược thứ tự: bit đầu đổi chỗ với bit cuối, bit thứ hai đổi chỗ với bit áp chót, v.v.
• Với xác suất \(25\%\), cả hai thao tác trên (bù bit và đảo ngược thứ tự) cùng xảy ra. (Lưu ý rằng thứ tự thực hiện hai thao tác không quan trọng.)
• Với xác suất \(25\%\), mảng không thay đổi.

Ngoài ra, mỗi lần dao động xảy ra, không có bất kỳ dấu hiệu nào cho biết hiệu ứng nào đã được áp dụng. Liên minh bắt đầu lo lắng và thuê bạn lấy lại dữ liệu quý giá của họ, bất kể hiện giờ nó đang ở dạng nào! Bạn có thể tìm toàn bộ mảng sao cho câu trả lời chính xác tại đúng thời điểm bạn đưa ra câu trả lời không? Việc trả lời không được tính là một truy vấn. Chẳng hạn, nếu trả lời sau truy vấn thứ \(30\), mảng vẫn ở cùng trạng thái như trong khoảng từ sau truy vấn thứ \(21\) đến hết truy vấn thứ \(30\).

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là bài toán tương tác. Hãy chắc chắn rằng bạn đã đọc phần Bài toán tương tác trong FAQ.

Ban đầu, chương trình phải đọc một dòng chứa hai số nguyên \(T\) và \(B\), lần lượt là số lượng bộ test và số bit trong mảng. Lưu ý rằng \(B\) giống nhau ở mọi bộ test.

Sau đó, bạn cần xử lý \(T\) bộ test. Trong mỗi bộ test, bộ chấm khởi tạo một mảng \(B\) bit đã được xác định trước; mảng này có thể khác nhau giữa các bộ test và không nhất thiết được chọn ngẫu nhiên. Tiếp theo, bạn được thực hiện tối đa \(150\) truy vấn theo dạng sau:

• Chương trình in một dòng chứa một số nguyên \(P\) trong đoạn từ \(1\) đến \(B\) (kể cả hai đầu), cho biết vị trí trong mảng mà bạn muốn xem.
• Nếu số thứ tự của truy vấn vừa gửi có chữ số tận cùng là \(1\), bộ chấm chọn ngẫu nhiên đều và độc lập với mọi lần chọn khác một trong bốn khả năng đã mô tả ở trên (bù bit, đảo ngược thứ tự, vừa bù bit vừa đảo ngược thứ tự, hoặc không làm gì), rồi biến đổi mảng đang lưu tương ứng. (Lưu ý rằng điều này xảy ra ngay ở truy vấn đầu tiên.)
• Bộ chấm trả lời bằng một dòng chứa một ký tự 0 hoặc 1, là giá trị hiện được lưu tại vị trí bit \(P\); hoặc trả lời N nếu bạn in một dòng sai định dạng (ví dụ, một vị trí không hợp lệ).

Sau khi thực hiện bao nhiêu truy vấn tùy ý trong giới hạn \(150\) truy vấn trên, bạn phải thực hiện thêm một lượt trao đổi như sau:

• Chương trình in một dòng chứa chuỗi gồm \(B\) ký tự, mỗi ký tự là 0 hoặc 1, biểu diễn các bit hiện đang được lưu trong mảng (chúng không nhất thiết trùng với các bit ban đầu!).
• Bộ chấm trả lời bằng một dòng chứa đúng một chữ cái: Y viết hoa nếu câu trả lời đúng, và N viết hoa nếu câu trả lời sai (hoặc nếu bạn in một dòng sai định dạng). Nếu nhận được Y, hãy bắt đầu bộ test tiếp theo, hoặc ngừng gửi dữ liệu nếu không còn bộ test nào.

Sau khi gửi N vào luồng nhập của chương trình, bộ chấm sẽ không gửi thêm bất kỳ dữ liệu nào. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận N, chương trình sẽ hết thời gian và nhận kết quả Time Limit Exceeded. Bạn có trách nhiệm cho chương trình thoát kịp thời để nhận kết quả Wrong Answer thay vì Time Limit Exceeded. Tương tự như thường lệ, nếu vượt giới hạn bộ nhớ hoặc gặp lỗi thực thi, chương trình sẽ nhận kết quả tương ứng.

Ràng buộc

\(1 \le T \le 100\).

Phân nhóm

Test Set 1 (hiển thị kết quả)

\(B = 10\).

Test Set 2 (hiển thị kết quả)

\(B = 20\).

Test Set 3 (ẩn kết quả)

\(B = 100\).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để kiểm thử cục bộ hoặc trên hệ thống của ban tổ chức. Để kiểm thử cục bộ, bạn cần chạy công cụ song song với chương trình của mình; có thể dùng trình chạy tương tác cho việc đó. Trình chạy tương tác đã được thay đổi sau kỳ thi năm 2019; hãy chắc chắn tải phiên bản mới nhất. Để biết thêm thông tin, hãy đọc hướng dẫn trong phần chú thích của tệp đó và tham khảo phần Bài toán tương tác trong FAQ.

Hướng dẫn sử dụng công cụ kiểm thử nằm trong các dòng chú thích bên trong công cụ. Bạn nên tự bổ sung các bộ test của riêng mình. Xin lưu ý rằng dù công cụ này được thiết kế để mô phỏng hệ thống chấm, nó KHÔNG PHẢI hệ thống chấm thật và có thể hoạt động khác. Nếu chương trình vượt qua công cụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm bạn đang dùng cùng trình biên dịch với ban tổ chức.

Ví dụ

t, b = readline_int_list()      // đọc 100 vào t và 10 vào b.
// Bộ chấm bắt đầu với mảng đã định trước cho bộ test này:
// 0001101111. (Test Set 1 thật không nhất thiết dùng mảng này.)
printline 1 to stdout           // ta hỏi vị trí 1.
flush stdout
// Đây là truy vấn thứ 1, nên bộ chấm bí mật chọn ngẫu nhiên một trong
// bốn hiệu ứng. Lần này nó chọn bù bit + đảo ngược thứ tự, vì vậy
// giá trị đang lưu trở thành 0000100111.
r = readline_chr()              // đọc 0.
printline 6 to stdout           // ta hỏi vị trí 6.
flush stdout
// Đây là truy vấn thứ 2, nên không có dao động lượng tử.
r = readline_chr()              // đọc 0.
...
// Các truy vấn từ thứ ba đến thứ mười được lược bỏ trong ví dụ này.
...
printline 1 to stdout           // ta quyết định hỏi lại vị trí 1.
flush stdout
// Đây là truy vấn thứ 11, nên bộ chấm bí mật chọn một hiệu ứng; lần này
// nó đảo ngược thứ tự, vì vậy giá trị đang lưu trở thành 1110010000.
r = readline_chr()              // đọc 1.
printline 1110110000 to stdout  // ta thử trả lời. tại sao chứ?!?!
flush stdout
ok = readline_chr()             // đọc N -- ta đã mắc lỗi!
exit                            // thoát để tránh lỗi TLE không rõ nguyên nhân

Nguồn

Google Code Jam 2020, Vòng loại, bài ESAb ATAd.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.