QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 256 MB 總分: 100 互動

#1418. Mountain Rescue Team

统计

The government of the IOI nation established a mountain rescue team specializing in Mount IOI due to the frequent accidents occurring there. A few days after its establishment, the rescue team received a report of an accident. According to the report, the victims are currently staying at a location with an altitude of $X$.

Mount IOI is represented as a grid with $R$ rows and $C$ columns, and an altitude value is determined for each cell. Let $(r, c)$ denote the cell in the $r$-th row from the top and the $c$-th column from the left. The shape of the mountain is known to satisfy the following conditions:

  • There are no two distinct cells with the same altitude.
  • The altitude of every cell is an integer between $1$ and $1\,000\,000\,000$, inclusive.
  • The cell $(R_S, C_S)$ is the peak of the mountain. That is, the cell with the highest altitude is $(R_S, C_S)$.
  • The distance between two cells $(r_1, c_1)$ and $(r_2, c_2)$ is defined as $|r_1 - r_2| + |c_1 - c_2|$. For any two adjacent cells, the one further from the peak has a lower altitude. Note that two cells are adjacent if they share an edge.

Since the rescue team was established only recently, the survey of Mount IOI is not complete, and the altitudes of the cells, including the peak, are unknown. You can use a specialized measuring instrument to check the altitude of a single cell by specifying its position, but it takes a certain amount of time to perform a measurement. You want to identify the position of the cell with altitude $X$ where the victims are located, but you must limit the number of times you use the measuring instrument to at most $1\,000$.

Task

Given the integers $R$ and $C$ representing the size of the grid, the position of the peak $(R_S, C_S)$, and the altitude $X$ of the cell where the victims are located, write a program to identify the position of the cell where the victims are located by using the measuring instrument at most $1\,000$ times.

Implementation Details

You must write a single program that implements the method of using the measuring instrument. Your program must implement the following routine:

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

This routine is called exactly once for each test case. The arguments $R$ and $C$ are the number of rows and columns of the grid representing the mountain, respectively. The arguments $R_S$ and $C_S$ are the row and column indices of the mountain's peak, respectively. The argument $X$ is the altitude of the cell where the victims are located.

In your program, you can call the following routines:

  • int Measure(int RM, int CM)

This routine is called when you want to use the measuring instrument. The arguments $R_M$ and $C_M$ are the row and column indices of the cell whose altitude you want to check, respectively. They satisfy $1 \le R_M \le R$ and $1 \le C_M \le C$. The return value of this routine is an integer between $1$ and $1\,000\,000\,000$, representing the altitude of the cell $(R_M, C_M)$.

If this routine is called with values that do not satisfy $1 \le R_M \le R$ and $1 \le C_M \le C$, it will be judged as Wrong Answer [1], and the program will be terminated.

Also, if this routine is called after it has already been called $1\,000$ times, it will be judged as Wrong Answer [2], and the program will be terminated.

  • void Pinpoint(int RP, int CP)

This routine is called exactly once when you have identified the cell where the victims are located. The arguments $R_P$ and $C_P$ are the row and column indices of the cell where you have identified the victims to be, respectively. They satisfy $1 \le R_P \le R$ and $1 \le C_P \le C$. This routine has no return value.

If this routine is called with values that do not satisfy $1 \le R_P \le R$ and $1 \le C_P \le C$, it will be judged as Wrong Answer [3], and the program will be terminated.

When the program calls this routine, if the altitude of the cell $(R_P, C_P)$ is equal to $X$, it will be judged as Correct; otherwise, it will be judged as Wrong Answer [4], and the program will be terminated.

If the Rescue routine terminates without calling this routine even once, it will be judged as Wrong Answer [5], and the program will be terminated.

Input

The sample grader reads the following input from standard input:

  • The first line contains the integers $R, C, R_S, C_S, X$ separated by spaces, representing the height $R$ and width $C$ of the grid, the peak position $(R_S, C_S)$, and the altitude $X$ of the victims' location.
  • The following $R$ lines contain information about the mountain's altitudes. The $i$-th line ($1 \le i \le R$) contains $C$ integers, where the $j$-th integer ($1 \le j \le C$) represents the altitude of the cell $(i, j)$.

Output

If the program terminates normally, the sample grader outputs the following information to standard output in one line:

  • If correct, it outputs "Accepted".
  • If incorrect, it outputs the type of error as "Wrong Answer[1]" based on the numbers written in the "Implementation Details" section. Furthermore, for Wrong Answer [4], the correct location of the victims $(R_X, C_X)$ and the information about the cell $(R_P, C_P)$ specified by the arguments when the Pinpoint routine was called are output as "Wrong Answer[4] : (RX, CX) = (3, 2), (RP, CP) = (4, 1)".

Constraints

All input data satisfy the following conditions:

  • $1 \le R \le 200$
  • $1 \le C \le 200$
  • $1 \le R_S \le R$
  • $1 \le C_S \le C$
  • $1 \le X \le 1\,000\,000\,000$

Subtasks

Subtask 1 [20 points]

Satisfies the following conditions:

  • $R \le 50$
  • $C \le 50$

Subtask 2 [80 points]

There are no additional constraints.

Examples

Example 1

Input:

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
Call Return Value
Measure(1, 1) 14
Measure(3, 5) 75
Measure(2, 4) 76
Pinpoint(2, 4) None

Note that this example does not necessarily represent a meaningful sequence of routine calls.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.