# 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 **h**_{i} (**0 <= h**_{i} <= 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**, **h**_{i} > **h**_{i+1}, and
- for all
**k** <= **i** < **N-1**, **h**_{i} < **h**_{i+1}.

However, because the sensor installation team forgot to measure the
sensors' heights, the value of **k**, and all the heights
**h**_{i}'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
**h**_{i}. 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:

sensor | height |

0 | 10 |

1 | 7 |

2 | 9 |

3 | 15 |

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

:

calls | returns |

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

calls | returns |

`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)

### Subtask 2 (25 points)

### Subtask 3 (25 points)

### Subtask 3 (25 points)

## 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**, **h**_{i}'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