IOI 2011 | Practice task
Animal behavior researchers would like to
get information on animal movements in a valley. They have placed
N motion sensors along a straight line crossing the valley at
various heights. For 0 <= i <= N-1, the i-th sensor's
height is hi (0 <= hi <= 1 000 000
000). No two sensors are on the same height.
Since the line is on a valley, the heights of sensors satisfy these
- there is an integer k (0 <= k <= N-1), such that the
k-th sensor has the minimum height,
- for all 0 <= i < k, hi > hi+1, and
- for all k <= i < N-1, hi < hi+1.
However, because the sensor installation team forgot to measure the
sensors' heights, the value of k, and all the heights
hi's are not known.
You would like to find if there is a sensor at height X. This
seems to be hopelessly impossible, but you recall that each sensor has
a height meter and can report its height. To minimize the power
usage, you would like to make only a small number of height queries.
You have to implement procedure
find(N,X) that returns
there exists a sensor at height
X and returns
0 otherwise. Your
procedure can call a procedure
query(i) to get
hi. However, you can make at most 50 calls, for each run of procedure
Note: In a single run, the sample grader, provided with the prototype, may perform many calls to find in one run. While the sample grader uses the same heights for all calls, the real grader may use different heights between each call to procedure
find. Therefore, you should not assume that two different calls to procedure
find share the same height information.
Suppose that N=4 and the height of each sensor is:
Note that in this case, k=1. The following are the return values
The correct implementation of procedure
find, when called by the
grader, should return as in the following table.
Subtask 1 (25 points)
Subtask 2 (25 points)
Subtask 3 (25 points)
Subtask 3 (25 points)
- Use the RunC programming and test environment. (See the contest environment information here)
- Implementation folder:
valley/ (download prototype here)
- To be implemented by contestant:
- Contestant interface:
- Grader interface:
- Sample grader:
- Sample grader input:
- The sample grader reads N, hi's, the number of X's, and X's from the standard input.
- In a single run, the sample grader may perform many calls to
find in one run. While the sample grader uses the same heights for all calls, the real grader may use different heights between each call to
find. Therefore, it is safe to assume that the heights change between different calls to
- Expected output for sample grader input:
- Compile and run (command line):
runc grader.c or
runc grader.cpp or
runc g rader.pas
- Compile and run (gedit plugin): Control-R, while editing any implementation or grader file.
- CPU time limit: The grader would make 100 calls to procedure
find; the total running time should be within 1 second.
- Memory limit: 256 MB