Home
IOI 2011

      Honorary Patron
      Welcome
      Organizers
      Sponsors
      Logo
      IOI Committee

Competition

      Call For Tasks
      Contest Environment
      Practice Tasks
      Rules
      Tasks
      Results
General Information
Registration

      Registration System

Visa Information
Gallery

      Album

Location

      Competition Site
      Room & Function

Press Room

      Newsletter

Sawasdee Thailand

      About Thailand
      Tourist info
      Practical Info
      Talk Thai
      Thai Food
      Shopping Center
      Transportation

Schedule

      Detailed Schedule
      Conference Schedule

IOI TV Program
Contact
TH | EN

Valley

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 constraints:

  • 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.

Your task

You have to implement procedure find(N,X) that returns 1 if 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 find.

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.

Example

Suppose that N=4 and the height of each sensor is:

sensorheight
010
17
29
315

Note that in this case, k=1. The following are the return values from procedure query:

callsreturns
query(0)10
query(1)7
query(2)9
query(3)15

The correct implementation of procedure find, when called by the grader, should return as in the following table.

callsreturns
find(4,10)1
find(4,2)0
find(4,9)1
find(4,15)1
find(4,100)0

Subtasks

Subtask 1 (25 points)

  • N <= 35.

Subtask 2 (25 points)

  • N <= 1 000; and k = 0.

Subtask 3 (25 points)

  • N <= 200.

Subtask 3 (25 points)

  • N <= 1 000.

Implementation details

  • Use the RunC programming and test environment. (See the contest environment information here)
  • Implementation folder: valley/ (download prototype here)
  • To be implemented by contestant: valley.c or valley.cpp or valley.pas
  • Contestant interface: valley.h or valley.pas
  • Grader interface: graderlib.h or graderlib.pas
  • Sample grader: grader.c or grader.cpp or grader.pas
  • Sample grader input: grader.in.1, grader.in.2, ...
    Note:
    • 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 find.
  • Expected output for sample grader input: grader.expect.1, grader.expect.2, ...
  • 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