JOI và IOI đều thích mì ramen. JOI thích ramen có vị thanh nhẹ, còn IOI thích ramen có vị đậm béo. Thị trấn nơi hai bạn sống có \(N\) quán ramen, được đánh số từ \(0\) đến \(N-1\).

Hai bạn chưa biết quán nào bán ramen đậm béo, quán nào bán ramen thanh nhẹ. Vì vậy, JOI và IOI quyết định đi ăn thử ở các quán trong thị trấn để xác định quán bán ramen thanh nhẹ nhất và quán bán ramen đậm béo nhất.

Mỗi quán có một độ đậm béo xác định cho món ramen của mình. Độ đậm béo là một số nguyên từ \(0\) đến \(N-1\), và độ đậm béo của các quán đôi một khác nhau. Mỗi ngày, JOI và IOI có thể đến hai quán, nếm thử và so sánh để biết quán nào trong hai quán có độ đậm béo cao hơn.

Vì sức khỏe, hai bạn muốn giới hạn số ngày ăn thử và so sánh ramen ở mức không quá \(600\) ngày.

Yêu cầu

Cho số quán ramen \(N\) trong thị trấn, hãy viết chương trình xác định quán có độ đậm béo thấp nhất và quán có độ đậm béo cao nhất trong số \(N\) quán, bằng cách ăn thử và so sánh trong không quá \(600\) ngày.

Chi tiết cài đặt

Bạn cần viết một chương trình cài đặt cách xác định hai quán nói trên bằng không quá \(600\) lần so sánh. Gói chương trình được cung cấp có tệp tiêu đề ramen.h; mã nguồn của bạn khai báo:

#include "ramen.h"

Chương trình phải cài đặt hàm sau:

void Ramen(int N);

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu. Tham số N là số quán ramen trong thị trấn. Hàm phải dùng các lời gọi Compare để xác định quán có độ đậm béo thấp nhất và quán có độ đậm béo cao nhất, rồi kết thúc bằng cách gọi Answer.

Chương trình của bạn có thể gọi hàm sau:

int Compare(int X, int Y);

Hàm này thực hiện một lần ăn thử và so sánh ramen. Các tham số X, Y là số hiệu của hai quán được so sánh.

• X và Y phải là hai số nguyên khác nhau, đều thuộc đoạn từ \(0\) đến \(N-1\). Nếu gọi Compare với tham số không thỏa mãn điều kiện này, chương trình bị đánh giá Wrong Answer [1] và kết thúc.
• Hàm trả về 1 nếu độ đậm béo của quán X lớn hơn độ đậm béo của quán Y.
• Hàm trả về -1 nếu độ đậm béo của quán X nhỏ hơn độ đậm béo của quán Y.
• Nếu gọi Compare quá \(600\) lần, chương trình bị đánh giá Wrong Answer [2] và kết thúc.

Hàm Ramen phải kết thúc bằng cách gọi hàm sau. Nếu Ramen không gọi Answer, chương trình bị đánh giá Wrong Answer [3] và kết thúc.

void Answer(int X, int Y);

Chỉ gọi hàm này khi các phép so sánh đã xác định được quán có độ đậm béo thấp nhất và quán có độ đậm béo cao nhất. X là số hiệu quán có độ đậm béo thấp nhất; Y là số hiệu quán có độ đậm béo cao nhất.

• X và Y đều phải là số nguyên từ \(0\) đến \(N-1\). Nếu tham số không thỏa mãn điều kiện này, chương trình bị đánh giá Wrong Answer [4].
• Nếu chỉ có duy nhất một cặp đáp án không mâu thuẫn với kết quả của các lời gọi Compare, và bạn gọi Answer với đúng cặp đáp án đó, chương trình được chấp nhận. Nếu không, chương trình bị đánh giá Wrong Answer [5].
• Khi Answer được gọi, chương trình kết thúc.

Lưu ý về chấm điểm

Khi chấm bài, nếu kết quả của các lời gọi Compare chưa xác định duy nhất đáp án, chương trình sẽ bị đánh giá Wrong Answer [5], bất kể các tham số truyền vào Answer là gì.

Trong một số bộ dữ liệu chấm, giá trị trả về của Compare có thể thay đổi tùy theo các lời gọi Compare trước đó. Ngay cả trong trường hợp này, giá trị trả về vẫn không mâu thuẫn với kết quả của bất kỳ lời gọi Compare nào trước đó.

Biên dịch và chạy thử

Gói dữ liệu chính thức chứa trình chấm mẫu để kiểm thử chương trình của bạn, cùng với các tệp mã nguồn mẫu cần nộp. Các tệp dành cho bài này nằm trong thư mục ramen/dist/ của gói dữ liệu.

Trình chấm mẫu gồm một tệp: grader.c hoặc grader.cpp. Chẳng hạn, nếu chương trình của bạn được lưu trong Ramen.c hoặc Ramen.cpp, hãy đặt tệp chương trình, tệp trình chấm tương ứng và ramen.h trong cùng thư mục rồi biên dịch như sau.

Với C:

gcc -O2 -lm grader.c Ramen.c -o grader

Với C++:

g++ -O2 grader.cpp Ramen.cpp -o grader

Nếu biên dịch thành công, tệp thực thi grader sẽ được tạo ra.

Lưu ý rằng trình chấm thật khác với trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa hai số nguyên \(N, T\) cách nhau bởi dấu cách. \(N\) là số quán ramen. Trình chấm mẫu chỉ xử lý dữ liệu có \(T = 1\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i+1\) (\(0 \le i \le N-1\)) chứa số nguyên \(A_i\) (\(0 \le A_i \le N-1\)), là độ đậm béo của quán \(i\). Các giá trị \(A_i\) đôi một khác nhau.

Dữ liệu ra

Nếu quá trình thực thi kết thúc bình thường, trình chấm mẫu ghi một dòng thông tin sau ra đầu ra chuẩn, không kèm dấu ngoặc kép:

• Nếu đáp án đúng, ghi Accepted.
• Nếu đáp án sai, ghi loại lỗi, chẳng hạn Wrong Answer [2].

Lưu ý: nếu gọi Answer(X, Y) với \(A_X = 0\) và \(A_Y = N-1\), trình chấm mẫu vẫn chấp nhận ngay cả khi trường hợp đó thuộc lỗi Wrong Answer [5] do các phép so sánh chưa xác định duy nhất đáp án. Hành vi này khác với trình chấm thật.

Ràng buộc

Tất cả dữ liệu thỏa mãn \(1 \le N \le 400\).

Phân nhóm

• Nhóm 1 (20 điểm): \(N \le 30\).
• Nhóm 2 (30 điểm): \(N \le 300\).
• Nhóm 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Dưới đây là một ví dụ dữ liệu vào của trình chấm mẫu và một dãy lời gọi hàm tương ứng.

3 1
1
2
0

Các lời gọi hàm