Problem Statement

This problem is based on a reduced version of a little known game called Tonga. We'll call this version PseudoTonga.

PseudoTonga is played by two players, Black and White, on a NxN board, for some even N. Pieces are black and white stones a little smaller than a square of the board. Players alternate turns, with Black playing first.

In each turn the player in turn places a stone on any empty square. A square is said to be uncolored if it's empty and is said to be black or white if it has a black or white stone on it.

As the game goes on isles of each color will become apparent. A Black isle is a group of solidly connected black squares, each being orthogonally adjacent to at least one neighbor black square. White isles are similar groups of white squares.

       . . . . . .
       . . W B . .
       . B W W B .
       . . . W B .
       B W W . . .
       . . B . . .

^{White has a four-square isle and a two-square isle. Black has four one-square isles and one two-square isle.}

The game stops when there is no room for a new stone. The total points of each player are calculated as the sum of the squares of all that player's isles' sizes.

   W W B B
   W B W W
   B W B B
   B W W B

In this example, White has 3²+3²+2²=22 points and Black has 3²+2²+2²+1²=18 points.

Getting to the problem, you will have to make a program that plays PseudoTonga against the TopCoder server. The TopCoder server will play with a fixed strategy as follows:

If the board is empty, he plays in one of the 4 middle squares.

If its not empty, for each square the server calculates a score. The score of a square is calculated in the following way: First simulate playing in the square, then try every play the oponent (i.e., you) is allowed to play and for each of those try playing again optimally. Compute the best scenario you can achieve for the worst scenario your oponent can leave you (do a minimax) and that's the score. The scenarios after the three moves (two server moves and one player move) are evaluated by assigning a score to each isle of area²*perimeter, where area is the number of squares in the isle and perimeter is the number of unoccupied squares adjacent to the isle (squares off the board don't count). The server's isles contribute positive points to the scenario, while the player's (your) isles contribute negative points. Finally, the server randomly selects a square which leads to the maximum score (in other words, ties are broken randomly).

For each game it will be randomly decided with 50%-50% probabilities who starts.

You have to implement two methods init and move. First init will be called with 3 ints, N, row and col. N will be an even number between 6 and 16 representing the number of squares of each side of the board. row and col will represent the row and column of the first play of the server (both 0-based) if he was selected to start or will both be -1 if you were selected to start. You have to return a int[] with exactly two elements, the first one being the number of the row of your first play and the second one being the number of the column of your first play (both 0-based). For each subsequent turn move will be called with two parameters row and col with a play from the server. In each call you have to return a int[] with two elements, in the same format as in init, representing your next move.

If at any point you return an invalid play (an int[] that does not have exactly two elements or in which one of the numbers is less than 0 or greater than N-1 or the square you play in is occupied), your program returns a runtime error or your time is up, a stone of server's color will be put in each remaining square and points will be awarded according to the resulting layout.

The number of points for a test case is the number of points you got minus the number of points the server got when the game finished. Note that is possible to have negative points for a test case. The points you get overall is the sum of the signed square root of the points of each individual test. For example, if your individual points in the 5 test cases were:

3, -4, 0, -1 and 8

then your overall score is:

sqrt(3) + (-sqrt(4)) + sqrt(0) + (-sqrt(1)) + sqrt(8)

Note that this calculation is doing with floating point numbers, so having a score of sqrt(2) is better than a sqrt(1), even though they are both 1 if truncated or rounded to an integer.

The time limit is 20 seconds and the memory limit is 64 megabytes.

Definition

Notes

Examples