Nghịch thế
Đề bài
Mô tả
Đây là một bài toán tương tác.
Trong lúc chuẩn bị bài H. Bài khó nhất (một bài về đếm, hoán vị và nghịch thế) cho kỳ thi ICPC khu vực năm 2022, ban giám khảo phát hiện ra rằng một số lời giải chậm có thể được tối ưu rất nhiều bằng cách đổi chỗ hai phần tử bất kỳ của một hoán vị để được một hoán vị mới. Lộc, một thành viên ban giám khảo, đưa ra giả thuyết rằng nếu lời giải bằng cách nào đó duy trì được số nghịch thế mà không cần lưu hoán vị thật sự, lời giải đó sẽ chạy cực nhanh, thậm chí có thể nhanh hơn cả lời giải mẫu!
Nhưng làm sao dùng thông tin về số nghịch thế để tìm lại được hoán vị ban đầu? Để minh họa, giả sử có một hoán vị ẩn độ dài . Lộc nói rằng có cách tìm ra bằng câu hỏi có dạng sau:
- Chọn hai chỉ số và (). Số nghịch thế của là bao nhiêu nếu đổi chỗ và ?
Hiện giờ chỉ Lộc biết cách dùng các thông tin này để tìm mảng , nên Lộc thách mọi người làm được điều tương tự!
Hoán vị ẩn độ dài do Lộc nắm giữ. Hãy tìm bằng cách hỏi Lộc không quá câu hỏi dạng trên.
Một nghịch thế của hoán vị là một cặp () sao cho . Câu hỏi chỉ là giả định: hoán vị ẩn không thay đổi sau mỗi câu hỏi.
Dữ liệu vào
Quá trình tương tác như sau:
- Đầu tiên, chương trình của bạn đọc một số nguyên () là độ dài hoán vị ẩn .
- Tiếp theo, bạn được hỏi Lộc (chương trình chấm) không quá câu hỏi. Để hỏi, in ra ? i j (), rồi đọc câu trả lời là số nghịch thế của nếu đổi chỗ và .
- Khi đã tìm ra hoán vị , in ra ! và kết thúc chương trình.
Sau khi in mỗi dòng, đừng quên in ký tự xuống dòng và flush đầu ra: dùng fflush(stdout) hoặc cout.flush() (hoặc endl) trong C++, sys.stdout.flush() trong Python.
Dữ liệu ra
Các câu hỏi và câu trả lời cuối cùng được in theo đúng định dạng mô tả ở trên.
Ràng buộc
- Không quá câu hỏi.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 2 2 |
? 1 1 ? 1 2 ? 1 3 ! 1 3 2 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Hoán vị ẩn là . Đổi chỗ với chính nó không làm thay đổi , có nghịch thế. Đổi chỗ và được với nghịch thế. Đổi chỗ và được với nghịch thế. Đề gốc minh họa cùng hoán vị này bằng các câu hỏi ? 1 2 (trả lời ), ? 2 3 (trả lời , vì không có nghịch thế), ? 3 1 (trả lời ) rồi in ! 1 3 2. |
| 1 | ! 1 | Ví dụ bổ sung: , hoán vị duy nhất là , không cần hỏi. |
| 2 1 0 |
? 1 1 ? 1 2 ! 2 1 |
Ví dụ bổ sung: có nghịch thế; đổi chỗ hai phần tử được với nghịch thế. |
Bình luận