Internet Problem Solving Contest

IPSC 2009

Problem H – Hunt!

This year new sheep-hunting rules were set in Wolfenstein:

A torus is a surface shaped like a donut. You can imagine the hunting area as a normal 30 × 30 chessboard, except for the fact that in each column the top and bottom cells are neighbors as well, and the same holds for the leftmost and rightmost cell in each row.

Problem specification

You are controlling the wolves. To gain one point for solving the easy data set, your task is to eat 10 sheep. To gain two more points for solving the hard data set, you have to eat all 60 sheep.

Note that you only play a single game for both data sets, and this game can not be restarted.

You are allowed to send us the moves of your wolves multiple times. However, there must be at least five minutes between any two consecutive submissions you make. Each time you send us your moves, we evaluate them and then move the sheep in your game.


As this task is a bit special, so is the scoring:

Input specification

There is no input for this task. You will receive your game description after your first submit.

Output specification

Every round we expect a list of 0 to 10 moves of your wolves (all tokens are separated by any whitespace). Each move is described by a pair id dir where id is the number of wolf (1 to 10, in the order they appear in the latest state description), dir is one of ‘U’, ‘D’, ‘L’, and ‘R’ (for moving the wolf up, down, left or right along the grid). Invalid moves in your submission will be ignored.

After any non-rejected submit you will receive the description of the current state.

Which data set to use?

Don’t worry about this. Regardless of how many sheep you already ate, you may always submit your moves as your “solution” to either of the data sets H1 and H2. The tester will handle it for you.

State description

The state description you receive after each submit is formatted as follows: It consists of 2 blocks – wolves block and sheep block. Each block starts with a number N giving the count of wolves/sheep. This number is followed by N pairs x y (0 x,y < 30) describing positions of each wolf/sheep.

You may assume that in each state all living sheep have distinct positions.

The directions up, down, left and right are such that from a cell (4,7) a move up takes you to (4,6), and a move left takes you to (3,7).


game description
4 0 5 5 29 7
4 8 4 28 15 3 18 12 6 27

The above game description contains 3 wolves and 5 sheep.

1 U
1 U
1 L
3 R
3 D

This is a sequence of moves in which first wolf 1 makes three moves, and then wolf 3 makes two moves.

If we apply this sequence of moves to the game state described above, we’ll get the following new state:

game description
3 28 5 5 0 8
4 8 15 3 18 12 6 27

Note that after two steps wolf 1 ate the sheep at (4,28).

Now the sheep would move. For example, the sheep at (6,27) is closest to the wolf at (3,28), hence it would move away from him.