Erika gần đây nhận được một công việc làm thêm mùa hè tại công viên giải trí Phantasialand gần Bonn. Cô được thuê để điều khiển đèn trong các căn phòng mà một chuyến tham quan trong bóng tối đi qua.

Chuyến tham quan đi qua ~N~ căn phòng, được đánh số từ ~0~ đến ~N-1~. Các phòng được đi qua theo thứ tự, bắt đầu từ phòng ~0~ và kết thúc ở phòng ~N-1~. Đèn trong các phòng được điều khiển bằng ~N~ công tắc (cũng được đánh số từ ~0~ đến ~N-1~), mỗi công tắc dành cho một phòng. Công tắc ~s~ (với ~0 \le s < N~) điều khiển đèn trong phòng ~p_s~.

Sếp của Erika yêu cầu cô bật đèn trong phòng đầu tiên và phòng cuối cùng, đồng thời tắt đèn trong tất cả các phòng còn lại. Nghe có vẻ dễ, đúng không? Cô chỉ cần bật hai công tắc ~A~ và ~B~ sao cho ~p_A = 0~ và ~p_B = N-1~ (hoặc ~p_B = 0~ và ~p_A = N-1~). Thật không may, Erika đã không chú ý đầy đủ khi sếp giải thích cách điều khiển, và cô không nhớ mảng ~p~ — tức là công tắc nào điều khiển phòng nào.

Erika cần tìm ra điều này trước khi sếp của cô nhận thấy. Trước khi bắt đầu mỗi lượt chạy, Erika tắt tất cả đèn rồi có thể bật một tập con các công tắc. Khi hành khách đi từ phòng này sang phòng khác, mỗi khi họ đi từ một phòng có đèn sáng sang một phòng không có đèn sáng hoặc ngược lại, Erika sẽ nghe thấy hành khách hét lên vì phấn khích. Tốc độ di chuyển có thể thay đổi, nên Erika không thể trực tiếp suy ra những phòng nào có đèn sáng, nhưng ít nhất cô sẽ nghe được số tiếng hét. Nghĩa là, cô sẽ biết số lần di chuyển từ một phòng có đèn sáng sang một phòng không có đèn sáng, hoặc từ một phòng không có đèn sáng sang một phòng có đèn sáng.

Bạn có thể giúp Erika tìm ra hai công tắc điều khiển đèn của phòng đầu tiên và phòng cuối cùng trước khi sếp của cô nhận thấy không? Bạn có thể sử dụng tối đa ~30~ lượt chạy.

Input

Đây là một bài toán tương tác.

Chương trình của bạn cần bắt đầu bằng việc đọc một dòng chứa số nguyên ~N~: số căn phòng mà chuyến tham quan trong bóng tối đi qua.

Sau mỗi lượt chạy được yêu cầu theo mô tả trong phần Output, chương trình của bạn cần đọc một số nguyên ~\ell~ (~0 \le \ell < N~), là số lần Erika nghe thấy hành khách hét lên.

Output

Sau đó, chương trình của bạn cần tương tác với trình chấm.

• Để bắt đầu một lượt chạy, bạn cần in một dòng bắt đầu bằng dấu hỏi "?", tiếp theo là một xâu có độ dài ~N~ gồm các ký tự 0 (tắt) và 1 (bật), cho biết cách bạn thiết lập ~N~ công tắc. Ký tự ở chỉ số ~s~ xác định trạng thái của công tắc ~s~. Sau khi in truy vấn, hãy đọc phản hồi của trình chấm theo mô tả trong phần Input.

• Khi muốn đưa ra đáp án, hãy in một dòng chứa dấu chấm than "!", tiếp theo là hai số nguyên ~A~ và ~B~ (~0 \le A,B < N~). Để đáp án được chấp nhận, đây phải là chỉ số của hai công tắc điều khiển hai phòng ở hai đầu, theo thứ tự bất kỳ. Sau đó, chương trình của bạn cần kết thúc.

Trình chấm không thích ứng, nghĩa là mảng ẩn ~p~ được xác định trước khi quá trình tương tác bắt đầu.

Hãy bảo đảm đẩy hết dữ liệu trong bộ đệm của đầu ra chuẩn sau khi yêu cầu mỗi lượt chạy, nếu không chương trình của bạn có thể bị chấm là vượt quá giới hạn thời gian. Trong Python, việc này diễn ra tự động miễn là bạn sử dụng input() để đọc các dòng. Trong C++, lệnh cout << endl; vừa in ký tự xuống dòng vừa đẩy dữ liệu trong bộ đệm; nếu sử dụng printf, hãy dùng fflush(stdout).

Scoring

• ~3 \le N \le 30000~.

• Bạn có thể yêu cầu tối đa ~30~ lượt chạy (việc in đáp án cuối cùng không được tính là một lượt chạy). Nếu vượt quá giới hạn này, bạn sẽ nhận được kết quả chấm "Wrong Answer".

Lời giải của bạn sẽ được kiểm tra trên một số nhóm test, mỗi nhóm có một số điểm nhất định. Mỗi nhóm test chứa một tập hợp các test. Để nhận được điểm của một nhóm test, bạn cần giải đúng tất cả các test trong nhóm đó.

Subtask	Điểm	Ràng buộc
1	~9~	~N = 3~
2	~15~	~N \le 30~
3	~17~	~p_0 = 0~, tức là công tắc ~0~ điều khiển phòng ~0~
4	~16~	~N~ chẵn, công tắc điều khiển một trong hai phòng ở hai đầu nằm trong nửa đầu (~0 \le A < \frac{N}{2}~) và công tắc còn lại nằm trong nửa sau (~\frac{N}{2} \le B < N~)
5	~14~	~N \le 1000~
6	~29~	Không có giới hạn gì thêm

Trong mỗi ví dụ, Sample Input liệt kê các dòng do trình chấm gửi, còn Sample Output liệt kê các dòng do chương trình của bạn gửi. Các dòng này được trao đổi xen kẽ theo giao thức tương tác: trước tiên đọc ~N~, sau đó in từng truy vấn và đọc phản hồi tương ứng, cuối cùng in đáp án.

Sample Input 1

5
3
3

Sample Output 1

? 10001
? 10110
! 2 4

Sample Input 2

3
0
2
0

Sample Output 2

? 111
? 110
? 000
! 1 0

Sample Input 3

4
3

Sample Output 3

? 1010
! 0 3

Notes

Công cụ kiểm thử

Để thuận tiện cho việc kiểm thử lời giải, chúng tôi cung cấp một công cụ đơn giản mà bạn có thể tải xuống. Xem mục "attachments" ở cuối trang đề bài gốc trên Kattis. Việc sử dụng công cụ này là tùy chọn. Lưu ý rằng trình chấm chính thức trên Kattis khác với công cụ kiểm thử được cung cấp.

Để sử dụng công cụ, hãy tạo một tệp đầu vào, chẳng hạn như "sample1.in", bắt đầu bằng một số ~N~, tiếp theo là một dòng chứa ~p_0, p_1, \dots, p_{N-1}~ xác định hoán vị ẩn. Ví dụ:

5
2 1 0 3 4

Với chương trình Python, giả sử là solution.py (thường được chạy bằng lệnh pypy3 solution.py), hãy chạy:

python3 testing_tool.py pypy3 solution.py < sample1.in

Với chương trình C++, trước tiên hãy biên dịch (chẳng hạn bằng lệnh g++ -g -O2 -std=gnu++23 -static solution.cpp -o solution.out), sau đó chạy:

python3 testing_tool.py ./solution.out < sample1.in

Giải thích các ví dụ

Trong ví dụ thứ nhất, hoán vị ẩn là ~[p_0,p_1,p_2,p_3,p_4] = [2,1,0,3,4]~. Ví dụ này thỏa mãn ràng buộc của các nhóm test ~2~, ~5~ và ~6~. Đầu tiên, chương trình đọc số nguyên ~N = 5~. Sau đó, chương trình yêu cầu một lượt chạy với hai công tắc được bật: công tắc ~4~ và công tắc ~0~. Chúng điều khiển các phòng ~p_4 = 4~ và ~p_0 = 2~. Erika nghe thấy ~3~ tiếng hét: lần thứ nhất khi di chuyển từ phòng ~1~ không có đèn sáng sang phòng ~2~ có đèn sáng; lần thứ hai khi đi từ phòng ~2~ có đèn sáng sang phòng ~3~ không có đèn sáng; và lần thứ ba khi đi từ phòng ~3~ không có đèn sáng sang phòng ~4~ có đèn sáng. Sau đó, chương trình yêu cầu một lượt chạy khác trong đó các phòng ~p_0~, ~p_2~ và ~p_3~ có đèn sáng, khiến Erika nghe thấy ~3~ tiếng hét. Cuối cùng, chương trình đưa ra đáp án ~A = 2~ và ~B = 4~, và đáp án này đúng vì các công tắc đó điều khiển phòng đầu tiên và phòng cuối cùng (~p_2 = 0~ và ~p_4 = 4~). Lưu ý rằng ~A = 4~ và ~B = 2~ cũng là một đáp án đúng.

Trong ví dụ thứ hai, hoán vị ẩn là ~[p_0,p_1,p_2] = [2,0,1]~. Ví dụ này thỏa mãn ràng buộc của các nhóm test ~1~, ~2~, ~5~ và ~6~. Chương trình yêu cầu một lượt chạy trong đó cả ba công tắc đều được bật. Vì điều này có nghĩa là tất cả các phòng đều có đèn sáng, Erika sẽ không nghe thấy tiếng hét nào. Trong lượt chạy thứ hai, các công tắc ~1~ và ~0~ được bật, khiến các phòng ~p_1 = 0~ và ~p_0 = 2~ có đèn sáng, trong khi phòng ~1~ không có đèn sáng. Erika nghe thấy hai tiếng hét: khi di chuyển từ phòng ~0~ (có đèn sáng) sang phòng ~1~ (không có đèn sáng), và từ phòng ~1~ (không có đèn sáng) sang phòng ~2~ (có đèn sáng). Trong lượt chạy cuối cùng, không có công tắc nào được bật, nghĩa là cả ba phòng đều không có đèn sáng, và một lần nữa Erika không nghe thấy tiếng hét nào. Sau đó, chương trình đưa ra đáp án là các công tắc ~1~ và ~0~, và chúng đúng là các công tắc điều khiển phòng đầu tiên và phòng cuối cùng. Cả "! 0 1" và "! 1 0" đều là các đáp án được chấp nhận.

Trong ví dụ thứ ba, hoán vị ẩn là ~[p_0,p_1,p_2,p_3] = [0,1,2,3]~. Ví dụ này thỏa mãn ràng buộc của các nhóm test ~2~, ~3~, ~4~, ~5~ và ~6~. Lưu ý rằng không nhất thiết có thể suy ra đáp án chỉ sau một lượt chạy này, nhưng lời giải trong ví dụ đã đoán đáp án và gặp may.

Ghi công và giấy phép

Bài toán này có nguồn gốc từ EGOI 2025 (Olympic Tin học nữ châu Âu), Ngày 1, được tổ chức tại Bonn, Đức.

• Đề bài gốc: Dark Ride

• Tác giả: Ivan Gaspardy.

• Chủ sở hữu bản quyền: Olympic Tin học nữ châu Âu 2025.

• Tài liệu chính thức: Đề bài và lời giải · Dữ liệu kiểm thử, trình chấm và các bản dịch

• Giấy phép: Creative Commons Ghi công – Chia sẻ tương tự (CC BY-SA), theo siêu dữ liệu chính thức của bài toán. Siêu dữ liệu không chỉ rõ phiên bản giấy phép.

• Các thay đổi: Dịch sang tiếng Việt và định dạng lại cho ClueOJ.

Bản dịch này được phân phối theo cùng các điều khoản CC BY-SA áp dụng cho bài toán gốc.

ClueOJ không có quan hệ liên kết với EGOI hoặc ban tổ chức EGOI 2025, cũng không được các bên này chứng thực.