Internet Problem Solving Contest

• Easy input data set – E1
• Hard input data set – E2

Sometimes it’s hard to see the forest, because all the trees get in your way. Other times, it’s hard to see the volcano, because of all the ash in the air.

Problem specification

The world is represented by a rectangle of M ×N cells. There is exactly one volcano somewhere in the world. The volcano occupies one of the cells. Your task is to find this cell.

Note that there are two separate data sets. The easy data set and the hard data set are completely independent and use two different maps. You have to solve each of them separately.

In the beginning, there is no ash anywhere. Our volcano erupts in rounds that correspond to your submits, and there is a changing wind which then distributes the ash over the world.

In each your submit you can check K locations of the map to see if there is currently any ash present or not. These probes are binary – it will report ash presence if and only if the cell contains at least one unit of ash.

Each round consists of the following steps, in order.

1. You submit a list of probes.
2. The volcano releases 100 units of new ash into the air at its location (no wind applied yet).
3. Your probes are evaluated.
4. A new wind is calculated and applied to the whole map. (In each round the current wind is the same everywhere on the map.)

The answer you’ll receive for your submit will contain all probe results and a description of the wind that was generated in step 4.

Wind model

The wind is specified by a 5 × 5 matrix called the wind matrix. Rows and columns of a wind matrix are labeled from -2 to 2.

A wind matrix specifies how to distribute the ash from any given cell into its surroundings. In each wind matrix the numbers are non-negative integers that sum up to 100, and they should be interpreted as percentages.

Formally, suppose that there are a units of ash in a given cell (x,y) before the wind blows. Let W be a wind matrix. After the wind described by W blows, the ash from (x,y) will be redistributed into cells (x′,y′) with x − 2 ≤ x′≤ x + 2 and y − 2 ≤ y′≤ y + 2. More precisely, the cell (x + d_x,y + d_y) will receive ⌊a ⋅ W_dx,dy∕100⌋ units of ash from this cell. Any ash that leaves the map boundary in this way is gone forever. Also note that (due to rounding) the total amount of ash the cells receive may be less than a.

It is important to note that the ash from all cells is being redistributed at the same time. (The process resembles a blur operation in a graphics editor.)

Input specification

The input file contains 3 integers: M, N and K. The map size is M × N cells. In each submit, you may specify up to K probe locations.

The volcano will be placed in a cell such that in any direction there are at least two other cells before we reach the map boundary.

Output specification

In each submit you can specify up to K cell locations x_i,y_i (0 ≤ x_i < M, 0 ≤ y_i < N). All values should be separated by whitespace. In case one of your probes matches the volcano location, the game ends and the data set is correctly solved.

Otherwise, you will receive a “WRONG ANSWER” message with the following information:
– the current round number,
– ash presence values for all your probes (0 = no ash present, 1 = some ash present),
– and a new wind matrix.

Submission limit

Please note that the submission limit for each data set is 10 submits, as is the case for any other task.

Be careful about the submissions you make. Try not to waste any, and always double-check whether the one you are about to send is correct.

Example submission (in the middle of a game)