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):
In phase 1 your position becomes the new one.
In phase 5 dead characters respawn randomly on the board, and no randomly placed object will have some other object at a distance of 150 or less. Also, if there is no fruit on the board (because it wasn't one at the beginning of the turn or because it was recently eaten) with a probability of 0.1, one fruit is placed randomly on the board (more than 150 away from any other object). Note that there will be no fruit before the initial movement of the characters.
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)):
You only need to implement a method nextStep which takes as input two ints 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 xFor your convenience, a visualization tool is being made available, which may interact with your program via stardard in/out. You may download it here. You may also play manually here.
|-||When "randomly" is mentioned without further clarification anywhere in the statement, it means uniformly between every valid choice.|
|-||The memory limit is 64M.|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.