|This is the archived CodeCup 2007 website.|
Click here to go to the new CodeCup website.
Rules of the game On The Run
IntroductionOn The Run is a two player game that is played on a world map that consists of cities and connections between the cities. One player controls the fugitive; the other player controls the four detectives in the game. The fugitive must try to stay away from the detectives.
MovesThe fugitive moves from city to city through the world. Each turn the fugitive takes a form of transportation to move to another city.
The detectives do not know where the fugitive is, nor where he is going. The detectives only receive information about the mode of transportation that the fugitive has used.
After the detectives have heard what mode of transportation the fugitive has used, they also pick some transportation to move to another city.
The fugitive knows at all times where the detectives are.
On predetermined times in the game the detectives receive information on the specific location of the fugitive. If one of the detectives is close enough he can move immediately to arrest the fugitive.
The fugitive and detectives can use the same types of transport: car, train, or plane.
BeginAt the beginning of the game a player is told which role he will play.
The player that has to control the detectives has to first pick the four starting positions of his detectives. The fugitive is told these positions and decides on where the fugitive will start. The detectives are told the starting position of the fugitive.
Rounds and turnsAfter the initial positions have been determined, ten rounds of five turns each are played. The first four turns of each round are normal turns, the final turn is an announcement turn.
In a normal turn the fugitive travels to another city. The detectives are told which type of transportation the fugitive has used. The detectives then all move to a new city. At the end of the turn no two detectives can be in the same city.
In an announcement turn the fugitive travels to another city. The detectives are then told in which city the fugitive is. The detectives than all move to a new city. And the end of the turn no two detectives can be in the same city.
Note that every turn both the fugitive as well as the detectives have to make a move. They are not allowed to stay in the same city.
Catching the fugitiveIf the fugitive travels to a city where there is a detective, or if a detective arrives in the city where the fugitive is, the fugitive is arrested and the game is over.
ScoringThe total number of points to be distributed in a game is 20.
If the fugitive has not been caught at the end of the tenth round, he wins the game. The score is then 20-0.
If the detectives catch the fugitive, the detectives win. Their score is 10 points + the number of announcements that have not been used. For example, if the fugitive is caught in the first round before the announcement, the detectives win 20-0. If the detectives catch the fugitive in the first round after the announcement, the detectives win 19-1. If they catch the fugitive in the last round after the announcement is made, so after the tenth announcement, the score is 10-10.
If, during an announcement round, the fugitive moves to a city where a detective already is, the announcement has not been used. So if this happens at the end of the first round the score is not 19-1, but 20-0 for the detectives.
The Playing FieldThe playing field consists of cities and connections between the cities. A connection always connects two different cities. A city can have several connections of different types. Every connection uses a specific type of transportation; car, train, or plane.
Note that it is possible to have several connections of different types between two cities.
Every city can always be reached from every other city by car. Every city has always at least two different connections of type car.
There are never more than 200 cities.
If you look at one specific connection type the graph is always a planar graph (connections do not intersect).
The cities that can be reached by train are a subset of the cities that can be reached by car.
The cities that can be reached by plane are a subset of the cities that can be reached by train.
In principle the car is used for short distances, the train is used for longer distances and the plane is used for larger distances. The number of cities with plane connections is generally limited.
All playing fields are similar, and you do not have to expect strange surprises.
Input formatThe playing field is described in the file connect.txt. The first line contains an integer n (n = 200) that indicates how many cities are on the playing field. The cities are labeled from 1 to n.
On the following lines the connections between the cities are described. Each connection is described by one character indicating the connection type, a space, the label of the first city, a minus symbol ('-') and the label of the second city.
The following (uppercase) characters are used to describe the connection types:
On the last line of the input file are the uppercase characters 'END'.
The playing field must be read at the beginning of the game.
Note that for different contests a new (unknown) playing field is used.
Example InputThe following lines describe an example input file that describes a playing field. This example matches the given image.
connect.txt 8 C 1-2 C 1-5 C 2-5 C 3-4 C 3-6 C 4-7 C 5-8 C 6-7 C 6-8 T 1-8 T 2-3 T 3-4 T 3-8 P 1-4 END
Playing the GameYour program should communicate with the jury program using standard-input (stdin) and stdandard-output (stdout).
You will read information from stdin and you will write your move(s) to stdout.
On the first line that you read you can find the word 'Fugitive' or the word 'Detectives'. This text indicates which role you will play.
If it is your turn to make a move, you calculate what your move is and then write the move to stdout. The fugitive has to write both the move as well as the type of transportation; the detectives only output the new positions of the detectives. The output of the fugitive should be always one line, the output of the detectives should be one line for each detective. For the detectives there should be noting on each line but the number of the city a detective goes to. For the fugitive there should be a single character denoting the type of transport, a single space character and a number of the city (except the initial announcement).
After you have made your move you read the move of your opponent from stdin. A move that you read is always a valid move. The input of the detectives is always exactly one line, the fugitive should expect a line for each detective.
If your program, or the program of your opponent has made an invalid move, or if the game is over because one player has won, you will read 'Quit' from stdin. This indicates that your program has to terminate normally. Note that even if you know that you have made a winning move you have to wait for the command 'Quit'.
The only time you terminate your program without receiving the 'Quit' command from the jury software is when you have made your last move in turn fifty.
Time limitYour program has a total playing time of 5 seconds. The jury computers use a Pentium IV, 2.8GHz that has 64Mb of internal memory available for your program.
It is up to you to decide how to divide these 5 seconds over the various moves.
Only the time between reading from stdin and writing to stdout is counted.
Example GameThe following table shows how initially the players do not know which role they will play. Each player reads its role from the input.
The detective then determines the initial placement of the detectives.
The fugitive is told where the detectives will be placed and then decides where the fugitive will start.
The first turn starts with the fugitive outputting its move. The detective only reads the type of transportation (in this case T for Train) from the input and then decides where the detectives will move. The fugitive is told where the detectives will move.
The turns 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, etc... all look similar to the first turn. The turns 5, 10, etc... all look as follows:
In the final turn the fugitive is not given the moves of the detective because the game ends. The final turn therefore looks as follows:
Contest NotesNote that in the demonstration files (connect01.txt - connect10.txt) there is information after the 'END' line. This information is used by the applet that shows the games. In the official contest files that are used during judging there is no information present after 'END'.
Note that in the demonstration files the city with label 1 can always be placed in the upper left corner, near the city with label 2. In the maps that are used during the competition this is not the case; in a planar representation of the map the cities may appear in any order.
Download the connect01.txt - connect10.txt files.
About CodeCupCodeCup is a computer programming competition that is organized by the organizers of the Nederlandse Informatica Olympiade (NIO), the Dutch organizers of the International Olympiad in Informatics.
The competition is hosted online and can be followed live from the internet.
Programmers from all over the world can enter the CodeCup competition. Enter the competition on the website http://www.codecup.nl. The organizers of the NIO are not eligible to participate.
Click here to see a sample game.