Internet Problem Solving Contest

• This problem has no input files.

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

• wolves are allowed to form packs of up to 10 animals
• hunting is only allowed on a torus divided into 30 × 30 cells
• there are 60 sheep randomly placed on the torus
• in each round:
  • wolves move before sheep do
  • a move means that an object moves from its cell into one of the four neighboring ones
  • all wolves together can do up to 10 moves
  • no single wolf can do more than 5 moves
  • each sheep can do up to 1 move
  • sheep moves are deterministic – they basically try to move away from the closest wolf
• if at any time a wolf moves to a field occupied by a sheep, the sheep is eaten
• if at any time a wolf moves to a field occupied by another wolf, one of the wolves is eaten

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.

Scoring

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

• You will get a time penalty (a ’*’ in the results) for each submission that does not obey the “five minutes between submissions” rule.
• Rejected submissions count towards the data set you are working on. I.e., until you eat 10 sheep all penalties are assigned to the easy data set, afterwards they are assigned to the hard data set.
• The limit is 10 incorrect submissions per data set, as usual.

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

Example

The above game description contains 3 wolves and 5 sheep.

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:

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.