Problem Statement

In this problem you'll play a continuous PacMan that fights against 4 evil ghosts. Ghosts outnumber you, but are silly, and each of them has a predefined strategy to follow in order to capture you (they do not do any team work as they should). There can also be a fruit that can be eaten by you or the ghosts. You, the ghosts and the fruit form the set of objects of the game. All objects except the fruit form the set of characters.

The board in which the game is played is a rectangle of 10000 by 10000 units and at each instant you and the ghosts are at some point with integer coordinates (X,Y) where 0 <= X,Y <= 10000. If two objects are within 75 from each other (meaning their distance is less than or equal to 75) we say they touch each other. At each instant, each object decides its move, and after that each move is performed in the following order (keep reading for a description of each item):

1. You are moved
2. Score and death calculations are made
3. Ghosts and the fruit are moved
4. Score and death calculations are made
5. Dead characters are respawned

In phase 1 your position becomes the new one.

In phase 3 all ghosts and the fruit positions become the new ones.

In phases 2 or 4, zero or more of these things can happen:

• If you touch a ghost, you are said to be dead, and get -10 points.
• If some ghost touches some other ghost, then it is said to be dead and you get +1 points for each dead ghost.
• If any character touches a fruit it eats it and the fruit disappears. If you eat the fruit you get +10 point, if any number of ghosts eat the fruit you get -10 point. If you and any number of ghosts eat the fruit during the same phase, the fruit disappears and no points are added nor substracted to your score.

You and each of the ghosts can move in steps of at most 100, which means the Euclidean distance between the current position and the position to where any character is moving must be less than or equal to 100. Moves outside the board are prohibited. The fruit can move to a distance of at most 50 units, but it moves randomly and always to a far location (the exact algorithm is given at the end of the problem statement).

The strategies for each ghost, numbered from 1 to 4, are (suppose your position is x,y and the ghost position is gx,gy, and let dx=abs(gx-x) and dy=abs(gy-y)):

• Move to the position that minimizes dx, and in case of ties, the one that minimizes dy
• Move to the position that minimizes dy, and in case of ties, the one that minimizes dx
• Move to the position that minimizes dx²+dy² (minimize Euclidean distance)
• Move to the position that minimizes dx+dy (minimize manhattan distance)

You only need to implement a method nextStep which takes as input two int[]s x and y representing the coordinates of each object in play and both contain exactly 6 elements. The 0th elements represent your coordinates, the 1st, 2nd, 3rd and 4th elements represent the 4 ghosts, in the order that was mentioned in the strategy description. If there is a fruit in play, its coordinates are described in both 5th elements, if there is not, both 5th elements are -1. This method has to return a int[] with exactly two elements, the x and y coordinate, in that order, to which you want to move next. If you return an invalid number of elements, or an invalid move (numbers outside valid range or a position too far away from your current location), it is assumed that you want to stay still (move to your current location) and then end the test case (see below).

Each test case will consist of up to 10000 calls to nextStep method, up to 30 seconds of execution in total, until a runtime error is produced or until you return an invalid move, whichever comes first. After each of the calls, every calculation is made. If your time is up, you give a runtime error, or return an invalid move, the last call will be assumed to return the same position you were in, the calculations will be made and then the test case will be over, even if the full 10000 steps haven't been executed. Your total score will be simply the sum of the score of each individual test case. If this total is negative, it will be increased to 0. There will be 20 system test cases.

The algorithm for the fruit movement is:

double theta = nextAngle();  //this selects a uniform value between 0 and 2*PI
newX := fix(oldX + trunc(cos(theta)*50)) 
newY := fix(oldY + trunc(sin(theta)*50))

fix(x) is max(0,min(x,10000))
trunc(x) is the integral part of x

Definition

Notes

Examples