Chính phủ IOI thành lập một đội cứu hộ chuyên trách núi IOI. Một ngày nọ, đội nhận được tin báo rằng những người bị nạn đang ở một vị trí có độ cao \(X\).

Núi IOI được biểu diễn bằng một lưới có \(R\) hàng và \(C\) cột. Ô \((r,c)\) nằm ở hàng \(r\) tính từ trên xuống và cột \(c\) tính từ trái sang, với chỉ số bắt đầu từ \(1\). Mỗi ô có một độ cao cố định. Địa hình thỏa mãn các tính chất sau:

• Độ cao của các ô đôi một khác nhau.
• Mỗi độ cao là một số nguyên từ \(1\) đến \(1\,000\,000\,000\).
• Ô \((R_S,C_S)\) là đỉnh núi, tức là ô có độ cao lớn nhất.
• Hai ô kề nhau nếu chúng có chung một cạnh. Trong hai ô kề nhau, ô có khoảng cách đến đỉnh núi lớn hơn luôn có độ cao nhỏ hơn.

Khoảng cách giữa hai ô được định nghĩa bởi

Đội cứu hộ biết vị trí đỉnh núi nhưng chưa biết độ cao của bất kỳ ô nào, kể cả đỉnh. Thiết bị đo có thể cho biết độ cao của một ô được chỉ định. Có đúng một ô có độ cao \(X\), và đội cần tìm ô đó bằng nhiều nhất \(1\,000\) lần đo.

Yêu cầu

Cài đặt hàm Rescue để xác định ô có độ cao \(X\), sử dụng không quá \(1\,000\) lời gọi Measure, rồi báo vị trí bằng Pinpoint.

Giao diện cài đặt

Nộp tệp mountain.c hoặc mountain.cpp, có chỉ thị

#include "grader.h"

Header grader.h khai báo đúng hai hàm do trình chấm cung cấp:

int Measure(int RM, int CM);
void Pinpoint(int RP, int CP);

Bạn phải định nghĩa hàm có chữ ký sau, không tự viết hàm main:

void Rescue(int R, int C, int RS, int CS, int X);

Trình chấm gọi Rescue đúng một lần cho mỗi bộ dữ liệu. R và C là số hàng, số cột; RS và CS là hàng, cột của đỉnh núi; X là độ cao cần tìm. Hàm có kiểu trả về void; kết quả được báo bằng lời gọi Pinpoint.

Trong khi thực hiện Rescue, bạn được gọi:

• Measure(RM, CM): Đo ô ở hàng RM, cột CM, với \(1 \le RM \le R\) và \(1 \le CM \le C\). Hàm trả về độ cao của ô đó dưới dạng int. Mỗi lời gọi hợp lệ được tính là một lần đo, kể cả khi đo lại một ô. Tổng số lần gọi không được vượt quá \(1\,000\).
• Pinpoint(RP, CP): Báo rằng người bị nạn ở ô hàng RP, cột CP, với \(1 \le RP \le R\) và \(1 \le CP \le C\). Phải gọi hàm này đúng một lần. Hàm không trả về giá trị; trình chấm kiểm tra đáp án rồi kết thúc chương trình ngay trong lời gọi này.

Các trường hợp bị chấm sai:

Với Measure, trình chấm kiểm tra tọa độ trước khi kiểm tra giới hạn số lần đo. Nếu Pinpoint chỉ đúng ô có độ cao \(X\), đáp án được chấp nhận và chương trình kết thúc.

Dữ liệu vào

Mã dự thi nhận dữ liệu qua các tham số của Rescue và các giá trị trả về từ Measure. Ma trận độ cao được giữ trong trình chấm; mã dự thi không đọc ma trận từ đầu vào chuẩn.

Để thử chương trình, chạy grader mẫu bằng đầu vào chuẩn có định dạng sau:

• Dòng đầu tiên chứa năm số nguyên \(R,C,R_S,C_S,X\), phân cách bằng dấu cách.
• Trong \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(C\) số nguyên; số thứ \(j\) là độ cao ô \((i,j)\).

Grader mẫu đọc toàn bộ dữ liệu này, đóng luồng đầu vào, đặt bộ đếm số lần đo về \(0\), rồi gọi Rescue(R, C, RS, CS, X).

Dữ liệu ra

Mã dự thi báo kết quả duy nhất qua Pinpoint(RP, CP); không in tọa độ ra đầu ra chuẩn.

Grader mẫu ghi một dòng ra đầu ra chuẩn: Accepted nếu đáp án đúng, hoặc một trong các thông báo Wrong Answer [1] đến Wrong Answer [5] trong bảng trên. Với đáp án sai vị trí, dòng được in chính xác là Wrong Answer [4]. Grader mẫu kết thúc với mã thoát \(0\) khi chấp nhận, hoặc mã thoát bằng số lỗi khi chấm sai.

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

Biên dịch cùng grader.c hoặc grader.cpp và đặt grader.h trong thư mục biên dịch:

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

hoặc

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

Chạy ./grader, cung cấp dữ liệu cho grader qua đầu vào chuẩn và nhận kết quả của grader qua đầu ra chuẩn. Trình chấm dùng khi chấm bài có thể khác grader mẫu nhưng tuân theo giao diện và giới hạn của bài.

Giới hạn

• \(1 \le R,C \le 200\).
• \(1 \le R_S \le R\) và \(1 \le C_S \le C\).
• \(1 \le X \le 1\,000\,000\,000\).
• Độ cao của mọi ô nằm trong đoạn từ \(1\) đến \(1\,000\,000\,000\) và thỏa mãn các tính chất địa hình đã nêu.
• Có một ô có độ cao \(X\).
• Được gọi Measure nhiều nhất \(1\,000\) lần trong mỗi bộ dữ liệu.
• Thời gian: 1 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình tìm đúng vị trí trong tất cả bộ dữ liệu của nhóm, tuân thủ giao diện, giới hạn số lần đo, thời gian và bộ nhớ.

• Bài toán con 1 (20 điểm): \(R \le 50\) và \(C \le 50\).
• Bài toán con 2 (80 điểm): Không có giới hạn bổ sung.

Ví dụ tương tác

Grader mẫu nhận dữ liệu sau từ đầu vào chuẩn:

5 5 3 3 76
14 59 84 62 28
15 73 92 76 35
68 97 100 89 75
58 67 86 79 55
17 25 71 10 5

Grader gọi Rescue(5, 5, 3, 3, 76). Một chuỗi lời gọi hợp lệ trong hàm này là:

Chuỗi lời gọi trên minh họa giao diện tương tác và không quy định chiến lược phải sử dụng.