Một liên danh nghiên cứu đã tìm kiếm cơ sở dữ liệu tốt nhất có thể trong ba năm, nhưng họ vẫn gặp vấn đề. Cơ sở dữ liệu lưu giá trị dưới dạng các bản ghi chứa chuỗi nhị phân \(8\) bit. Không may, phần cài đặt hàm gán giá trị cho bản ghi bị lỗi.

Mỗi bản ghi của cơ sở dữ liệu là một chuỗi nhị phân \(8\) bit. Các bit được đánh chỉ số từ \(0\) đến \(7\) theo thứ tự từ trái sang phải. Khi nhận lệnh gán một bản ghi cụ thể thành giá trị mới \(V\), thay vì gán trực tiếp thành \(V\), cơ sở dữ liệu thực hiện các bước sau:

1. Chọn một số nguyên \(r\) trong đoạn từ \(0\) đến \(7\), kể cả hai đầu, rồi tạo \(W\) bằng cách xoay \(V\) sang phải \(r\) vị trí. Nói cách khác, bit thứ \(((i+r)\bmod8)\) của \(W\) là bit thứ \(i\) của \(V\).
2. Thay giá trị hiện tại \(X\) của bản ghi bằng \(X\operatorname{XOR}W\). Tức là, bit thứ \(i\) của giá trị mới bằng \(1\) khi và chỉ khi bit thứ \(i\) của \(X\) và \(W\) khác nhau.
3. Cuối cùng, trả về cho người dùng số bit bằng \(1\) trong giá trị mới.

May mắn là bất kể giá trị ban đầu và các độ xoay mà cơ sở dữ liệu chọn là gì, ta luôn có thể đặt lại bản ghi thành toàn bit \(0\) sau không quá \(300\) lần dùng thao tác này. Hãy viết chương trình tương tác với cơ sở dữ liệu để thực hiện việc đó.

Dữ liệu vào

Ban đầu, chương trình phải đọc một dòng chứa số nguyên \(\mathbf{T}\), là số lượng bộ test. Sau đó phải xử lý \(\mathbf{T}\) bộ test.

Ở đầu mỗi bộ test, bản ghi trong cơ sở dữ liệu được đặt thành một giá trị khác 00000000. Trong mỗi bộ test, chương trình được thực hiện tối đa \(300\) lượt trao đổi.

Sau khi chương trình gửi một giá trị \(V\), nó đọc một dòng chứa số nguyên duy nhất \(\mathbf{N}_i\), là số bit bằng \(1\) trong giá trị bản ghi đã được cập nhật.

Dữ liệu ra

Lượt trao đổi thứ \(i\) bắt đầu bằng việc chương trình in một dòng chứa đúng một chuỗi nhị phân \(8\) bit để dùng làm giá trị \(V\) trong thao tác đã mô tả.

Lời giải được xem là đúng khi và chỉ khi đặt thành công bản ghi về 00000000 trong mọi bộ test.

Giao thức tương tác

Đây là bài tương tác. Bạn cần đọc kỹ phần Interactive Problems trong FAQ của Google Code Jam.

Sau khi bạn in \(V\), giám khảo thực hiện thao tác xoay và XOR rồi gửi \(\mathbf{N}_i\):

• Nếu \(\mathbf{N}_i=0\), bạn đã thành công và phải bắt đầu bộ test tiếp theo, hoặc kết thúc chương trình nếu đây là bộ test cuối.
• Nếu \(\mathbf{N}_i=-1\), đây là lượt trao đổi thứ \(300\) của bộ test nhưng bản ghi chưa từng trở thành toàn bit \(0\), nên bộ test thất bại. Không bộ test nào khác được xử lý sau đó.
• Nếu \(1\le\mathbf{N}_i\le8\), giá trị mới của bản ghi có \(\mathbf{N}_i\) bit \(1\) và bạn có thể tiếp tục lượt trao đổi kế tiếp để cố đưa nó về toàn bit \(0\).

Nếu ở bất kỳ thời điểm nào giám khảo nhận được một dòng sai định dạng hoặc không hợp lệ từ chương trình, giám khảo sẽ in duy nhất số \(-1\) và không in thêm gì nữa. Khi nhận \(-1\), bạn phải kết thúc chương trình đúng cách, không vượt giới hạn tài nguyên, để nhận phán quyết Wrong Answer. Nếu không, bạn sẽ nhận phán quyết tương ứng với tài nguyên bị vượt hoặc điều kiện kết thúc sai.

Ràng buộc

• \(1\le\mathbf{T}\le100\).
• \(-1\le\mathbf{N}_i\le8\) với mọi \(i\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): Giá trị ban đầu của bản ghi được chọn đều ngẫu nhiên trong tất cả các chuỗi nhị phân \(8\) bit khác 00000000. Mỗi độ xoay cũng được chọn đều ngẫu nhiên và độc lập với mọi lựa chọn cũng như tương tác trước đó.
• Test Set 2 (phán quyết hiển thị): Giám khảo có tính đối kháng. Điều này có nghĩa là, trong số những khả năng khác, giám khảo có thể thay đổi giá trị ban đầu hoặc các độ xoay miễn chúng vẫn nhất quán với toàn bộ tương tác. Giá trị ban đầu được bảo đảm không bao giờ là 00000000.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử chính thức để chạy cục bộ hoặc trên nền tảng của Google Code Jam. Khi kiểm thử cục bộ, cần chạy công cụ song song với chương trình; có thể dùng interactive runner của Google. Hãy đọc hướng dẫn trong phần chú thích của tệp đó và phần Interactive Problems trong FAQ để biết thêm chi tiết.

Hướng dẫn dành cho công cụ kiểm thử nằm trong các chú thích bên trong công cụ. Bạn được khuyến khích bổ sung các bộ test của riêng mình. Mặc dù công cụ đượ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ể hành xử khác. Nếu chương trình vượt qua công cụ nhưng thất bại trên giám khảo thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm bạn dùng cùng trình biên dịch với hệ thống chấm.

Tải công cụ kiểm thử chính thức.

Ví dụ

Nguồn

Google Code Jam 2022, Vòng 1B, bài ASeDatAb.

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