Lễ bế mạc EGOI có \(N\) vị khách quan trọng cần ngồi ở hàng ghế đầu theo một thứ tự ngoại giao đã được xác định nhưng bị thất lạc.

Khách và ghế đều được đánh số từ \(0\) đến \(N-1\). Gọi \(g_I\) là khách ngồi ở ghế \(I\), và \(s_I\) là ghế của khách \(I\).

Hình 1: Một hàng có năm khách, với \(g=[3,1,0,2,4]\) và \(s=[2,1,3,0,4]\).

Một ứng dụng nhận đúng ba số hiệu khách phân biệt \(I,J,K\) và trả số khách ít nhất xuất hiện trong một bức ảnh chứa cả ba người, tức:

Hãy dùng ứng dụng để xác định dãy \(g_0,g_1,\ldots,g_{N-1}\). Luôn có đúng hai đáp án, là hai chiều đảo ngược của nhau; có thể in một trong hai. Điểm phụ thuộc vào số truy vấn.

Giao thức tương tác

Đây là bài tương tác qua standard input/output.

Đầu tiên đọc số test \(T\). Với mỗi test:

1. Đọc \(N\).
2. Để hỏi, in ? I J K, trong đó \(I,J,K\) là ba số phân biệt thuộc \([0,N-1]\), rồi đọc một số nguyên dương là câu trả lời.
3. Để trả lời, in ! g_0 g_1 ... g_{N-1}.

Sau khi giải hết \(T\) test, chương trình phải kết thúc bình thường. Grader chính thức có thể thích nghi: ở một số test, hoán vị chưa được cố định trước mà được chọn dần tùy theo các truy vấn đã hỏi.

Phải flush standard output sau mỗi lệnh. Trong C++ có thể dùng cout << endl hoặc fflush(stdout); trong Python dùng print(..., flush=True).

Ràng buộc

• \(1\le T\le10\).
• \(N\) chỉ có thể là \(5\) (chỉ ở ví dụ), \(8\), \(40\) hoặc \(2000\).
• Mỗi test được hỏi nhiều nhất \(10\,000\) truy vấn.

Phân nhóm

1. \(9\) điểm: \(N=8\).
2. \(11\) điểm: \(N=2000\), và khách \(0,1\) ngồi cạnh nhau.
3. \(15\) điểm: \(N=40\).
4. \(65\) điểm: \(N=2000\).

Nhóm 1 và 2 nhận trọn điểm nếu giải đúng mọi test. Với nhóm 3 và 4, gọi \(Q_s\) là số truy vấn lớn nhất trên một test và \(X_s=\max(1,Q_s/N)\). Khi đó:

Điểm được làm tròn đến số nguyên gần nhất theo từng nhóm. Để đạt trọn điểm cần giải nhóm 3 bằng không quá \(55\) truy vấn và nhóm 4 bằng không quá \(2597\) truy vấn.

Ví dụ giao thức

Grader       Submission
1
5
             ? 0 2 4
3
             ? 3 0 1
3
             ? 0 4 3
5
             ! 3 1 0 2 4

Trong ví dụ, ba câu trả lời đủ xác định thứ tự là [3,1,0,2,4] hoặc thứ tự đảo ngược [4,2,0,1,3].

Công cụ thử nghiệm

Gói đính kèm cung cấp testing_tool.py, các template seatingplan.cpp, seatingplan.py và input mẫu. Input cho công cụ gồm \(T\), rồi với mỗi test là \(N\) và hoán vị \(g\). Công cụ chỉ hỗ trợ thử cục bộ; grader chính thức có thể thích nghi và có hành vi khác.

Nguồn

EGOI 2026 - Ngày 2, Seating Plan.

Đề bài EGOI 2026 được phát hành theo giấy phép Creative Commons Attribution (CC BY).