Đây là 1 bài tương tác với máy chấm
a độ dài n. Nhiệm vụ của bạn là tìm ra hoán vị mà đang có. Mỗi lần bạn được hỏi cung cấp dữ kiện để tìm kiếm bằng cách chọn 2 chỉ số i,j (1\le i,j\le n; i\ne j) và sẽ cho bạn biết giá trị của a_i\ mod\ a_j
đang có 1 hoán vịBạn chỉ được hỏi 2n-2 lần. Nhiệm vụ của bạn là tìm ra hoán vị mà đang có.
không quáHướng dẫn cách giao tiếp với máy chấm
Để câu trả lời của bạn có thể đến được với máy chấm, bạn cần phải flush output của mình ra. Sau đây là cách flush output ở một vài ngôn ngữ phổ biến
- C++:
cout << endl;
. - Pascal:
flush(output)
. - Python:
stdout.flush()
. - Java:
System.out.flush()
.
Để hiểu rõ hơn, bạn có thể đọc blog của codeforces tại đây: https://codeforces.com/blog/entry/45307
Lưu ý: Một số test/submit có thể có verdict Time limit exceed
khi cả chương trình của bạn và máy chấm đều cùng muốn nhập input. Lúc này máy chấm và chương trình của bạn đều chờ output của nhau và sẽ hết thời gian.
Lưu ý: Bạn có thể chạy thử chương trình interactive trên máy của chính mình.
Input, Output và Subtasks
Input
- Dòng đầu tiên chứa một số nguyên dương t là số testcase (1\le t\le 10^3)
- Sau đó là t testcase, mỗi testcase gồm duy nhất một số nguyên dương n là kích thước mảng mà đang có (2\le n\le 10^4)
- Dữ liệu đảm bảo tổng n trong tất cả testcase không quá 10^4
Interaction: (stdin
/ stdout
)
- Sau khi đọc input, bạn không được hỏi quá 2n-2 câu hỏi, với mỗi câu hỏi được định dạng như sau:
- ?\ i\ j: Bạn chọn 2 chỉ số i,j, và máy chấm sẽ xuất ra giá trị của a_i\ mod\ a_j
- Sau một vài lần hỏi, trường hợp bạn đã tìm ra hoán vị, bạn xuất ra đáp án với định dạng như sau:
- !\ a_1\ a_2\ \dots\ a_n: Bạn trả lời hoán vị mà bạn đã tìm thấy. Thao tác này sẽ không tính vào số lần hỏi. Sau hành động này, ta sẽ chuyển qua testcase tiếp theo.
- Trường hợp bạn xuất ra hành động không hợp lệ, số lần hỏi của bạn vượt quá số lần cho phép hay bạn tìm ra kết quả sai, chương trình của bạn sẽ nhận kết quả
Wrong answer
. Bạn chỉ được nhận kết quảAccepted
nếu bạn xuất ra đúng hoán vị trong tất cả testcase
Sample
Interaction: (stdin
/ stdout
)
Máy chấm | Chương trình nộp | Giải thích |
---|---|---|
2 |
Có t=2 testcase | |
2 |
Trong testcase này, n=2 | |
? 1 2 |
Bạn chọn 2 chỉ số là i=1, j=2 để hỏi | |
1 |
a_1\ mod\ a_2=1 | |
! 1 2 |
Bạn đã tìm thấy kết quả, hoán vị a={1,2} và may mắn đúng! Ta chuyển sang testcase tiếp theo | |
3 |
Trong testcase này, n=3 | |
? 1 2 |
Bạn chọn 2 chỉ số là i=1, j=2 để hỏi | |
0 |
a_1\ mod\ a_2=0 | |
? 1 3 |
Bạn chọn 2 chỉ số là i=1, j=3 để hỏi | |
1 |
a_1\ mod\ a_3=1 | |
? 3 2 |
Bạn chọn 2 chỉ số là i=3, j=2 để hỏi | |
0 |
a_3\ mod\ a_2=0 | |
! 3 1 2 |
Bạn đã tìm thấy kết quả, hoán vị a={3,1,2} và may mắn đúng! |
Bình luận