Cops and Robbers

 2014-1c-copsandrobbers.jpg?400

Mouse Stofl was asked by Scotland Yard to help find and arrest the dangerous Mouse X. Your job is to direct the cops through the streets of London to make sure that there is no way for Mouse X to escape. Or do you feel adventurous? You can also help Mouse X to avoid the cops as long as possible.

The Game

The city is modelled as a graph consisting of $N$ junctions and $M$ streets, each of which connects two different junctions. Between any given pair of two junctions, there is at most one street, and each street can be used in both directions. The graph is connected, i.e. for any two junctions, it is possible to get from the first junction to the second using a sequence of streets.

There are $C+1$ mice. One of them is Mouse X and is controlled by the first program, and the remaining $C$ are cops and controlled by the second program.

At the beginning of the game, the mice are distributed randomly over the junctions. It is guaranteed that no two mice start on the same junction, and that no two mice start on neighboring junctions (i.e. two junctions connected by a street).

The game is played in rounds. In each round, Mouse X moves first and after that all cops move simultaneously. The following are valid moves:

  • Move to a neighboring junction.
  • Stay on the same junction.

Note that it is allowed to have several cops on the same junction at the same time.

The game ends as soon as one of the following happens:

  • Mouse X moves on a junction occupied by one or several cops. In this case, the cops win.
  • A cop moves on the junction where Mouse X is. In this case, the cops win.
  • $R$ rounds have been played without Mouse X being caught. In this case, Mouse X wins.

Input and Output

Your program will be run by a game server. It has to read from stdin and has to output its moves to stdout.

When the game starts, you are given a line containing the letter «P» (for police) if you have to play the cops or «X» if you have to play Mouse X.

After that, you get a line containing the integer $C$, followed by a line containing the integer $R$.

Then you are given the street graph of the city in the following format: One line containing two integers $N$ and $M$, separated by a single space, followed by $M$ lines, each of which contains two integers $a_i$ and $b_i$ which indicate that there is a street between junction $a_i$ and junction $b_i$. Junctions are numbered from $1$ to $N$, and $1 \leq a_i, b_i \leq N$.

Then, you read the initial position(s) of your player(s): If you're Mouse X, that's a line containing one junction number, and if you're the cops, it's a line containing $C$ space-separated junction numbers, the $i$-th number being the initial junction of the $i$-th cop. Note that the order of the cops in the input remains the same throughout the whole game. Then, round after round is played.

If you're Mouse X, a round works as follows:

  • You get a line containing $C$ space-separated integers, indicating on which junctions the cops currently are.
  • You have to output one integer, the number of the junction to which you want to move.

If you're the cops, a round works as follows:

  • You get a line containing one integer, indicating on which junction Mouse X currently is.
  • You have to output $C$ space-separated integers, the $i$-th number being the number of the junction to which you want to move the $i$-th cop.

Once the game is ended, your program will be terminated by the server.

Sample communication

An example of a game is illustrated in the figure. Below you can find the corresponding communication for the Mouse X and the cops.

2014-1c-copsandrobbers-example.jpg?500

Example game

Mouse X communicationCops communication

> X
> 2
> 100
> 7 7
> 1 2
> 1 3
> 2 4
> 3 4
> 3 5
> 5 6
> 5 7
> 3
> 6 7
< 1
> 5 5
< 2
> 3 3
< 2
> 4 1
< 4

> P
> 2
> 100
> 7 7
> 1 2
> 1 3
> 2 4
> 3 4
> 3 5
> 5 6
> 5 7
> 6 7
> 1
< 5 5
> 2
< 3 3
> 2
< 4 1

Limits

  • $1 \leq C \leq 8$
  • $10 \leq R \leq 100$
  • $10 \leq N \leq 200$
  • $10 \leq M \leq 500$

Tips

For interactive tasks, it is important that you flush the output buffer after every round to make sure that your output becomes visible for the server. Use the following commands:

  • C/C++: fflush(stdout);
  • C++: cout << flush;
  • Pascal: flush(output);
  • In other languages, similar commands exist.

Further, when reading input, it is important that your program does not wait for more characters than the server gives you as input. Especially spaces or line breaks in the format string in C are a common cause of error. For instance, if you read the last variable of the input with scanf("%d ", &x);, the scanf function waits for the next character which is not a space or a newline. However, you will get such a character only after you have announced your move. So, your program would block here. To solve this, use scanf("%d", &x); instead, i.e. no whitespace after the %d

Sample Bots, server and visualization

During the first round, we will provide the following material:

  • Sample bots in different programming languages.
  • A server program that you can use to let your own program compete against your and other programs.
  • A visualization to animate simulated games.

You can find this material here (ZIP-File 150KB), and since they are continuously developed, it is worth having a look at the website from time to time.

You can also find an updated version here. It contains the improved visualization used at the SOI day and more interesting maps.

Grading

The grading scheme for the creativity task is different than for the other tasks. You get:

  • 50% of the points for a program which plays the game correctly, i.e. which respects all the rules and plays at least as well as the sample bots. Important: You are not allowed to simply copy and submit the code of the sample bots. However, you are allowed and encouraged to use them as instructions on how to correctly do the input/output in your programming language.
  • The remaining 50% of the points are awarded according to the result at the tournament at the SOI day.

Submission