산악 구조대 Interactive 컴파일 명령

IOI 산에서는 조난 사고가 끊임없이 발생하고 있습니다. 이에 IOI 나라의 정부는 IOI 산에 전문 산악 구조대를 설립했습니다. 설립한지 며칠이 지난 어느 날, 구조대에게 조난 사고를 알리는 통보가 왔습니다. 통보에 따르면 조난당한 사람들은 해발 고도가 X인 곳에 머물고 있다고 합니다.

IOI 산은 R행 C열의 격자판으로 표시되고 각 격자에 해발 고도가 적혀 있습니다. r번째 행과 c번째 열의 교차점에 있는 격자는 (r, c)로 나타냅니다. 구조대는 산의 모양이 다음과 같이 되어 있다는 것을 알고 있습니다.

• 고도가 같은 서로 다른 두 격자는 존재하지 않습니다.
• 모든 칸의 고도는 1 이상 1,000,000,000 이하의 정수입니다.
• 산의 정상 (R_S, C_S)가 존재합니다. 즉 고도가 가장 큰 격자는 (R_S, C_S)입니다.
• 두 격자 (r₁, c₁)과 (r₂, c₂) 사이의 거리를 |r₁ - r₂| + |c₁ - c₂|로 정합니다. 이 때, 인접한 두 격자에 대해, 정상에서부터의 거리가 먼 격자가 고도가 더 작습니다. 두 격자가 인접하다는 것은 한 변을 공유하고 있다는 것을 말합니다.

산악 구조대는 설립된지 얼마 안 되었기 때문에, IOI 산을 많이 조사하지 않았고 따라서 꼭짓점을 포함한 각 격자의 해발 고도는 알려져 있지 않습니다. 전문 측정 장비를 이용하여 어떤 한 격자의 해발 고도를 알아낼 수 있습니다. 그러나 고도를 측정하는 데에는 일정한 시간이 걸립니다. 구조대는 이 측정 기기를 사용하여 조난자가 있는 고도가 X인 격자의 위치를 특정하고 싶으나, 이 측정 장치의 사용 횟수는 1000회 이하로 하고 싶습니다.

해야 할 일

IOI 산을 나타내는 격자판의 크기를 나타내는 두 정수 R과 C, 정상의 위치를 나타내는 두 정수 R_S, C_S, 조난자가 있는 격자의 해발 고도 X가 주어집니다. 측정 기기를 최대 1,000번 이용하여 조난자가 있는 격자의 위치를 특정할 수 있는 프로그램을 작성하세요.

구현 세부 사항

여러분은 측정 장비를 사용하는 방법을 구현한 프로그램을 작성해야 합니다. 이 프로그램은 아래 함수를 구현해야 합니다.

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

이 함수는 각 테스트 케이스(실행)에 대해 단 한 번만 호출됩니다. 인수 R과 C는 각각 산을 나타내는 격자판의 행의 수 R과 열의 수 C입니다. 인수 RS와 CS는 각각 산 정상의 행 번호와 열 번호 R_S, C_S입니다. 인수 X는 조난자가 있는 격자의 해발 고도 X입니다.

또한 이 함수는 아래 함수들을 호출할 수 있습니다.

int Measure (int RM, int CM);

이 함수는 측정 기기를 사용하고자 할 때 호출됩니다. 인수 RM과 CM은 측정 기기가 고도를 확인할 격자의 행 번호 R_M과 열 번호 C_M입니다. 1 ≤ R_M ≤ R, 1 ≤ C_M ≤ C를 만족해야 합니다. 이 함수의 반환값은 (R_M, C_M)의 고도를 나타내는 1 이상 1,000,000,000 이하의 정수입니다.

1 ≤ R_M ≤ R, 1 ≤ C_M ≤ C를 만족하지 않는 인자로 이 함수를 호출하면 Wrong Answer [1]이 판정되며 프로그램은 즉시 종료됩니다.

또한 이 함수의 호출 횟수가 1000회를 초과할 시 Wrong Answer [2]가 판정되며 프로그램은 즉시 종료됩니다.

void Pinpoint (int RP, int CP);

이 함수는 조난자가 있는 격자의 위치를 측정하고자 할 때 단 한 번 호출해야 합니다. 인수 RP와 CP는 각각 조난자가 있는 격자의 행 번호 R_P와 열 번호 C_P입니다. 1 ≤ R_P ≤ R, 1 ≤ C_P ≤ C를 만족해야 합니다. 이 함수는 반환값이 없습니다.

1 ≤ R_P ≤ R, 1 ≤ C_P ≤ C를 만족하지 않는 인자로 이 함수를 호출하면 Wrong Answer [3]이 판정되며 프로그램은 즉시 종료됩니다.

프로그램이 이 함수를 호출했을 때 (R_P, C_P)의 해발 고도가 X와 같다면 정답, 그렇지 않으면 Wrong Answer [4]가 판정되며, 프로그램은 즉시 종료됩니다.

Pinpoint 함수를 단 한 번도 호출하지 않고 종료한 경우, Wrong Answer [5]가 판정되며 프로그램의 실행은 종료됩니다.

컴파일 및 실행 방법

작성한 프로그램을 시험해 보기 위한 예제 채점 프로그램은 여기를 클릭하시면 내려받을 수 있습니다. 이 파일에는 제출해야 할 파일인 mountain.c(pp) 역시 포함되어 있습니다.

예제 채점 프로그램은 1개의 파일로 구성되어 있습니다. 그 파일은 grader.c 또는 grader.cpp이다. 작성한 프로그램을 컴파일하려면, 다음과 같이 명령을 실행해야 합니다.

• C의 경우: gcc -O2 -lm grader.c mountain.c -o grader
• C++의 경우: g++ -O2 grader.cpp mountain.cpp -o grader

컴파일에 성공하면, grader라는 실행 파일이 생성됩니다.

실제 채점 프로그램은 예제 채점 프로그램과 다르다는 점에 유의하세요.. 이 프로그램은 표준 입력(stdin)으로부터 입력을 받고, 표준 출력(stdout)에 출력합니다. 단 입력 파일이 이상한 등, 프로그램의 실행과 관련 없는 비정상적인 오류가 발생했을 시 stderr에 출력합니다.

입력 형식

예제 채점 프로그램은 표준 입력(stdin)으로부터 아래와 같이 입력을 받습니다.

• 첫 번째 줄에는 네 개의 정수 R, C, R_S, C_S, X가 주어집니다. R과 C는 산을 나타내는 격자판의 크기를 나타내고, 정상의 위치는 (R_S, C_S)이며, X는 조난자가 있는 격자의 높이입니다.
• 다음 R개 줄에는 산의 고도의 정보가 주어집니다. 이 중 i번째 줄 (1 ≤ i ≤ R)에는 C개의 정수가 공백을 사이로 두고 주어집니다. 그 중 j번째 정수 (1 ≤ j ≤ C)는 격자 (i, j)의 고도를 나타냅니다.

출력 형식

프로그램 실행이 정상적으로 종료된다면, 예제 채점 프로그램은 표준 출력(stdout)에 프로그램의 실행 결과를 나타내는 메시지를 한 줄에 출력합니다.

• 정답의 경우, "Accepted"으로 출력됩니다.(따옴표는 실제로는 출력되지 않습니다.)
• 오답의 경우, "Wrong Answer[1]"과 같이 출력됩니다. 괄호 안의 숫자는 위에서 기술한 오류 번호와 같습니다. Wrong Answer[4]에 대해서는, 조난자의 위치 (R_X, C_X)와 Pinpoint 함수의 인자 RP, CP의 값이 "Wrong Answer[4]:(RX, CX)=(3, 2),(RP, CP)=(4, 1)"과 같이 출력됩니다.

제약 조건

모든 데이터는 아래 조건을 만족합니다.

• 1 ≤ R ≤ 200
• 1 ≤ C ≤ 200
• 1 ≤ R_S ≤ R
• 1 ≤ C_S ≤ C
• 1 ≤ X ≤ 1 000 000 000

부분문제

부분문제 1 [20점]

• R ≤ 50
• C ≤ 50

부분문제 2 [80점]

추가 제약 조건이 없습니다.

예시

위 예시는 단순히 이해를 돕기 위한 것이며, 올바른 방법과는 관계가 없습니다.