Một thí nghiệm không gian mới sử dụng \(N\) vật thể, được gắn nhãn từ \(1\) đến \(N\), trong đó \(N\) là số lẻ. Mỗi vật thể có một độ mạnh là số nguyên dương chưa biết, nằm trong đoạn từ \(1\) đến \(N\). Độ mạnh của các vật thể đôi một khác nhau. Vật thể có độ mạnh trung vị là vật thể mà số vật thể có độ mạnh nhỏ hơn nó bằng số vật thể có độ mạnh lớn hơn nó.

Hãy viết chương trình xác định nhãn của vật thể có độ mạnh trung vị. Cách duy nhất để so sánh độ mạnh là dùng một thiết bị: với ba vật thể khác nhau, thiết bị cho biết vật thể có độ mạnh trung vị trong ba vật thể đó.

Giao diện thư viện

Bạn nộp một chương trình C++ hoàn chỉnh có hàm int main(), dùng #include "device.h" và gọi các hàm dưới đây. Không tự cài đặt các hàm của thư viện device.

Chương trình sử dụng thư viện device cung cấp ba thao tác:

• GetN: gọi đúng một lần ở đầu chương trình, không có tham số, trả về \(N\).
• Med3(x, y, z): nhận nhãn của ba vật thể đôi một khác nhau, trả về nhãn của vật thể có độ mạnh ở giữa trong ba vật thể đó.
• Answer(m): gọi đúng một lần ở cuối chương trình để báo nhãn \(m\) của vật thể có độ mạnh trung vị trong toàn bộ \(N\) vật thể. Lời gọi này kết thúc chương trình.

Với C/C++, dùng #include "device.h". Các khai báo là:

int GetN(void);
int Med3(int x, int y, int z);
void Answer(int m);

Với Pascal, dùng uses device;. Các khai báo là:

function GetN: integer;
function Med3(x, y, z: integer): integer;
procedure Answer(m: integer);

Giới hạn

Có \(5 \le N \le 1499\) và \(N\) lẻ. Mọi nhãn \(i\) thỏa mãn \(1 \le i \le N\). Mọi độ mạnh \(Y\) thỏa mãn \(1 \le Y \le N\), và các độ mạnh đôi một khác nhau. Trong mỗi lần chạy, chương trình được gọi Med3 không quá \(7777\) lần. Chương trình không được đọc hoặc ghi bất kỳ tệp nào; mọi trao đổi với thiết bị phải thông qua ba thao tác của thư viện.

Thử nghiệm cục bộ

Trong giao diện thử nghiệm của đề gốc, bạn tự tạo tệp DEVICE.IN gồm đúng hai dòng: dòng đầu chứa \(N\); dòng thứ hai chứa một hoán vị của các số từ \(1\) đến \(N\), trong đó số thứ \(i\) là độ mạnh của vật thể mang nhãn \(i\). Thư viện ghi hai tệp: dòng đầu của MEDIAN.OUT là nhãn được truyền cho Answer, dòng thứ hai là số lần chương trình đã gọi Med3; MEDIAN.LOG ghi lại cuộc trao đổi giữa chương trình và thư viện.

Tệp đính kèm median-template.zip cung cấp device.h, khung chương trình template.cpp, mã kết nối device_stub.cpp và trình thử local_test.py. Trình thử đọc DEVICE.IN do bạn chọn, trả lời các lời gọi thư viện và tạo MEDIAN.OUT, MEDIAN.LOG theo ý nghĩa trên. Xem README.md trong tệp ZIP để biên dịch và chạy thử. Chỉ ghép device_stub.cpp vào chương trình khi chạy thử trên máy của bạn; khi nộp bài, chỉ nộp mã C++ của bạn có hàm main, hệ thống sẽ cung cấp các hàm thư viện. Không đưa độ mạnh của các vật thể vào mã nộp bài và không đọc trực tiếp DEVICE.IN từ chương trình. Mã kết nối không tự mô phỏng thiết bị: cần chạy chương trình thông qua local_test.py, không chuyển thẳng nội dung DEVICE.IN vào đầu vào chuẩn của chương trình.

Ví dụ

Dữ liệu mô tả thiết bị gồm hai dòng: dòng đầu là \(N\), dòng thứ hai là một hoán vị của các số từ \(1\) đến \(N\), trong đó số thứ \(i\) là độ mạnh của vật thể mang nhãn \(i\). Đây là dữ liệu của thiết bị, không phải dữ liệu để chương trình của bạn đọc trực tiếp.

5
2 5 4 3 1

GetN() -> 5
Med3(1, 2, 3) -> 3
Med3(3, 4, 1) -> 4
Med3(4, 2, 5) -> 4
Answer(4)