JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 11
Problem: SnakePlayer

Problem Statement

    

Introduction

Snake is a classic computer game (a simple search will turn up dozens of versions you can play yourself, such as Yahoo's). In the game, you control a snake who moves around on a grid and eats food. Each time the snake eats food, it grows slightly longer. If the snake runs into an obstacle or runs into itself it loses. The goal is to eat as much food as possible before losing.



Game Play

More specifically, a NxN grid is generated with randomly placed obstacles (see below). The snake starts out in a single empty cell of this grid, facing in the up (+Y) direction. At all times, there are M units of food at non-obstacle cells. When the snake eats a unit of food, another one appears at a random empty cell. At each time step the snake advances one unit in its current direction. You, as the controller of the snake may change the direction of the snake by turning left or right before the snake moves. When the snake moves, the cells occupied by the snake remain mostly unchanged: the head advances to its new location and the tail disappears (playing the game will make this more clear). The exception to this movement rule occurs immediately after the snake eats food. On the time steps immediately after the snake eats food, the tail does not disappear when the head moves. Each time the snake eats, it grows by K units. Eating twice in row will cause the snake to grow by 2K units.



Sample Game Play

Snake if headed to the right, and then turns right ('H' is head, 'X' is the rest of the snake, 'T' is tail)
..XXXH..      ..XXXX..
..X.....  ->  ..T..H..
..T.....      ........

You should imagine that the tail moves first, and then the head, so that the snake may continue straight here:
..XXXX..       ..XXXX..
..X..X...  ->  ..X..X..
..XTHX...      ..THXX..

Snake eats two food and continues straight ('F' is food), K = 2
..XXHFF...      ..XXXHF....      ..XXXXH....      ..XXXXXH...      ..XXXXXXH..      ..XXXXXXXH.      ..TXXXXXXXH
..X.......  ->  ..T........  ->  ..T........  ->  ..T........  ->  ..T........  ->  ..T........  ->  ...........
..T.......      ...........      ...........      ...........      ...........      ...........      ...........

Implementation Details

To play the game you should write a method play, that take N, M, and K as parameters. In addition, you will be given parameters obstacleX and obstacleY as well as foodX and foodY, specifying the x and y coordinates of the obstacles and food at the start of the game. Finally, you will be given sx, and sy specifying the starting location of the snake. To move the snake, you should call a static function moveSnake in a class Snake. This function takes a single String which is a sequence of moves. The String should specify one or more moves for the snake to make, where 'R' means turn right and move, 'L' means turn left and move, and 'S' means continue straight. For example, if the snake starts at (0,0) facing in the +Y direction and sends the command "SRS" it will end up at (2,1) facing to the right. This function will return a int[] specifying the location of any new food which appears on the board as a result of the moves you make. Elements 2*i and 2*i+1 of the return give the x and y coordinates of the new food (so {4,5,8,9} indicates new food at (4,5) and (8,9)).

End of Game

The game will stop under a number of conditions:
  • You lose by running into an obstacle, yourself, or by running off the board.
  • Your program crashes or calls Snake.move with an invalid parameter (the empty string, or a String with invalid characters)
  • You return normally from your play method.
  • You exceed 20 seconds of processing time.
  • The game has run 20,000 steps or 1,000 calls to moveSnake.
On the call to moveSnake that ends the game, the int[] {-1} will be returned. This is your signal to finish execution gracefully.

Scoring

Once the game is over, your score will simply be the total amount of food eaten. Your overall score will be the sum of your normalized scores, where your normalized score for a test cases is computed as YOUR SCORE/BEST SCORE (BEST SCORE is the best score on that test case out of all competitors).

Board generation

All ranges are inclusive, and all random choices are uniform and independent.
  • N will be chosen randomly between 20 and 100.
  • M will be chosen randomly between 5 and 20.
  • K will be chosen randomly between 3 and 10.
  • A real value p will be chosen between 0 and 0.5. Each cell in the grid will be selected as a potential obstacle with probability p. Once the potential obstacles are selected, they will be randomly ordered and installed as actual obstacles one by one, so long as doing so does not create two disconnected empty areas. For instance, if there were an obstacles at (1,0), and the next potential obstacle were at (0,1), that obstacle would be skipped (unless (0,0) were an obstacle), since it would disconnect (0,0) from the rest of the board.
  • Food and the snake's starting position will be chosen randomly from the empty cells, with no two food occupying the same location, and no food at the snake's starting position.

Visualizer

A visualizer has been provided which you can use to watch your snake. It will also allow you to test the same examples that are in the problem statement. This tool is provided as is, though we will to our best to fix any bugs that crop up.
 

Definition

    
Class:SnakePlayer
Method:play
Parameters:int, int, int, int, int, int[], int[], int[], int[]
Returns:int
Method signature:int play(int N, int M, int K, int sx, int sy, int[] obstacleX, int[] obstacleY, int[] foodX, int[] foodY)
(be sure your method is public)
 

Available Libraries

    
Class:Snake
Method:moveSnake
Parameters:String
Returns:int[]
Sample Call:val = Snake.moveSnake(sequence);
    
 

Notes

-Eating is cumulative. Thus eating two food in a row will make the snake grow by a total of 2K unit.
-Coordinates are 0-indexed, and hence range from 0 to N-1.
-If there is nowhere to put food (because all locations are taken) then no food is placed.
-In the diagrams (and the visualization), +x is to the right, and +y is up.
-The memory limit is 64MB.
-For convenience, the example seeds are: -2138290827, -1910768650, 32378291, 538769737, -474836816, 628242945, 419079253, -2139897132, 1340840114.
-The return value of your function will be ignored -- return any value you like.
-Notice that nothing about the board changes in a random way until you eat some food. Thus, if you only make calls to moveSnake with sequences that result in food being eaten, your snake will probably die or hit the 20,000 step limit before hitting the 1,000 call limit.
 

Examples

0)
    
seed = -2138290827
N = 21
M = 5
K = 6
sx = 8
sy = 19
p = 0.3150846017326555
#..####F.#..##.##....
#...#...H.#..#...#.#.
#.#...##...#..#..#..#
...####..####...##...
....##.#...#....##...
######..#............
....#.....#.#.##.#..#
....#.#..#.#.......#.
.....###.#...###.....
#F#.....#...#..#..#..
.###....#...........#
...##.#...#.#.##.F...
.#.#F#.##.#.........#
..##........#.......#
.#..#.##.##..##..#.#F
.....#.#...#.####....
.........#.......#...
...##..#....#..#..#..
...##.....#.....#....
....###...#.#.....#..
.........#...#.#.....
1)
    
seed = -1910768650
N = 25
M = 17
K = 4
sx = 21
sy = 2
p = 0.15118920582490047
...##.##.........#...#...
....#....#..#.##.........
#....#F.....#..#..#.F....
#..##...#......#....#....
...#.F.......#...........
..#...#.#..F#............
..........F........##F...
........#....#.#..#..#.#.
...##....F.#......#..#...
#..##..#.F............#.#
...#................#....
......#..#.F.F...........
.#...F..##.............#.
.#........#........#.F#..
...#..#......#.....#..#..
.#.........#.#...........
#..................#.....
.......#..............#..
........#.............#..
...#........#.#...#...##.
.#.....#.................
.#.#.............F.......
....##.##..........#.H...
.#.....F..........#...F..
....#...#......F.......#F
2)
    
seed = 32378291
N = 30
M = 14
K = 5
sx = 3
sy = 26
p = 0.46152558142840144
#..#..##...#.###.#....F..#..#.
##...##..#...##....#.#.#...##.
....####.#.#.######...##....#.
#..H########..##.##....#...#F.
.....#....#....#...##.#..#....
......#...##.#.F##...#.#..##F#
.#.#.#..#.#..##.##..#..###F...
.##..#.##.....#####..#....#..#
##..###.....#.###....##....#..
###...#.##...####.####..##.F.#
.#.....#.....#....###..#....#.
..##...##..##..#..##.#..#.#.#.
..#...###..###F...#.....###.F.
.##.#.#.##.####.F.###.#.#....#
...##...##......#..#.##.####.#
.#..#.#.....###.###..##.#####.
..#.#.#.#..####..#.#.#....F...
.#...#...###..#.##.......#.#..
.##....##..##..##.....#..##...
..#.....#..#.FF##F#.#####....#
...#.#..F.........#.#####..#..
#.#....###...#...#......#.#..#
.##.#.....####..#...#....##...
....###.#...#..#.....#.#.##...
#...##...###....#.###...#....#
#.####.#..###.#..##...##..#..#
.....#..##..#.#.##...##....#..
#.###......##..#.....###..##..
#..#...#....#.##..#####..##...
##.#####..#.#...#.....##.....#
3)
    
seed = 538769737
N = 43
M = 18
K = 4
sx = 23
sy = 40
p = 0.22855053598120068
......#..#.#.....#...#..#..#.............##
.#..#....F....###...#............##.##..#..
..##.#...#....#####.F..H..#........###.#.#.
..#.......#...#...##....###......#....#F...
......#.....#...#..##....#.##..#....#..#.#.
...##..#..F..##..#....#.......#.F#.........
.#.#...............##.#.......#..#.......#.
..#..##........#.................####......
....##.....##......#..#..#..#..#.........#.
...#.....#.#.....#........#.#.##.#..##...F.
#...#..#...#...........#.#..F....##.....#..
##....#......#....#.#...#..#...#....#......
...#............##..#...........#.#.......#
.........#..#.....##..#....#......#.#..#..#
.#.#.#...#........#.......................#
#....#.#......#...........####.#...#..##.#.
.#.......#.............................#...
........##..F..#...#......#.........#......
#...........##.#.#.#.........###.#.........
..........#...#....##.#...#......#..#......
....#...#...#.......#...#...##....#.#...#.#
.###.###.#...#.....#.....#..#.###.......#..
..........##..#..#........##..##.......##..
......#....#............#..##......##..#...
.#.#..#F.............#....#........#..##...
........#.....##......#.......##..#..#.....
..............#......##.....#.##.##..#...##
#.......F........#.#.#...F#....#...##..#...
.....##.....#.............#...#.........#..
..#............F#.............#......#...#.
......#..#....###....#.##........#.....##.#
........#..###.#...#..#...###F..##...####.#
.............#....#.#.....###........#..#..
.....#.#..##.#.....F.#..........##..#......
.##..F..#...........###.....#..###..#....##
...#............F.......#.#..##...#.##..#.#
#............#.............###...#...##....
......#.#####....##....#....##...F.#.......
..#.#....##...........#..#..#......#.....#.
.#..........#.....#..........##......F.#.##
..#......#..#.#...##.#....##..#.#....#.#...
#.#.#..#...#...#...#..###.#..#...#...##....
#......#....###..............##...##..##...
4)
    
seed = -474836816
N = 57
M = 12
K = 5
sx = 44
sy = 12
p = 0.3866633823455691
......#.....#..#..###.#.......##.#...#.#..#..#.....#..###
#....##.##.#..#.#...#.#.###.##....##...##.....##........#
#.#....#.#...##.....#.......##.##.....#.#..#...#.....#..#
..##..##.#....##....#..#.#..#..#...........#....#..##.#.#
.#.#.......#.#..##..#.##.##...##............#..##.##....#
##...#.##.##......#...#....#....#..###..#........#.......
..#.....##..##....##......###.#.#.....#.........#..#....#
#.###...##.....##.#....##.....##.....#.###.##.#......#...
....#.#...#...#...#.##..#.##.##.###..#...#.F........##..#
.#.##..#.#...#.......#..#.#.F#..#...#..####...#........##
.#F....##...########......##...#..#...#.....#.#..........
##.#...#..#..#....#..####.........##.#.###..........#.##.
.#...#####..#.#.##.....#...###..###.##.#####..##.#...#...
..#####.........#..#..##.....#.#........####.....#..#.###
.###.#....#.#..##.######..##..#.....##...#...#.....#....#
..#..#.#...##.##.#..#..#....##..###.#####.##........#.##.
.#.#...##.....#...#.##.###..#.#.#...#........#..##..#....
.........#.#...##.#.##........#....#.######.....##..#..##
..#.#.##..###...#...#..##....#####...#.#..#..#...##......
..###..##....#..#....##....#....##.....#.#.#...##......##
.#..##..##....#...F.####..#..#.#...#.....#.##..#.#.#...#.
..#.#..#......##.....#...#.....##..##..##...####..##.....
..#..###.#...#......#..######.#..##.......##..#...###.#.#
.#.#...####..##..#.#.#...#..##..#######.##.....##....#..#
##..#......#.###...#.#.###F#.##..##......##.#...##...#.##
#...#...#.###..##..#..###.......#..##..#.#.#.#..##.####.#
........#...#........#...####...#.#..#.#.#...#......###..
.#....#...........##.#..##..##.#....#...##.#.##...#...#.#
#...#.##..##.......###.###..#...#.....###............#..#
#..##.#.#.....####...#..##..#..##..###................#..
..#..F....#..#.##....#..#.#.........#.#.#.##.###........#
......#..#..#.....##...##.##...........##.##...#...##.##.
#.#.#..#.#...#....#.##.##...#.#...###.#..#.#.##..##......
...##......#...#..#.#..#...#.......#.....#....#.###.#...#
#.#.#......#....#...#.#...##.#####.#..#......#.##.#.#..#.
##..#.#.#.##..#..##..##.....#...##.##.#..#.........#.#...
...#.#..#.#.#..#....#..#.......#.F...###.##.###..##......
.##.....##....#.......##....#..#.#...#..###.#.###..F###..
.........#..#.#.#.##.#.##..##.#..##.#..#....#....##..#...
.......#.###.F#..#...#....####.#.#..#.#####.##.....#####.
.##.##.......#..#..#.###...#.#.##..#..##...##..#.#.......
..#####...#..#.#....##...#...#..#.#.#.#..#.##...........#
.###..#.#...#...#..##.###.....#.##..#.....#...#.#....##..
##...#.#..#..#..##.#...#.#..#....##...#.###..##..#.###..#
...#....#..##..##..#.#....#.......###.....#.H....####....
##.#.....#...#...#...##.#..###.....###.#...####......#..#
....#......######..#..###....###..###.#.##.......###.....
...#.##....#......######.....##...#.#...###.##.#####.##..
##.....#.#.###.#..#........###.#.##........#...#....#....
..###...#.....#####..##..#.#.#...#...##..###....###......
....#.##...#....##..#.##..##.#.#.#..##.#.##.#......###..#
.###...#.#...#.#.#..#..#.......####.....#.....#..#..##.#.
.###...#.#.#...#.#..#..####.#..#..#....##.#.#.....#.##...
.###..#.F#.###....##....#...#.###..##...###..#....###..#.
....#..#..#.##...###..#.##..###.....#.#.....#.##..##.....
.#.F.#.##....#.#......#.##..##.#...#...#...##...#.....#..
..##.....#...##..#....###........#....#.......#..#.#..F#.
5)
    
seed = 628242945
N = 75
M = 16
K = 3
sx = 22
sy = 67
p = 0.4626937984132135
.##.#.#...#....##..####.#.....#..#..#...#...##..#...###.#....F#.##......#..
.......##....#.##..##...#.##....#..#.##.#..#...#...###...#..###.....##....#
..##....##..#...##..##..#...#.##.....#..F..###...#..#.#.....##...###..##.##
.#.##..#.#.##.##...##..#..#.##...###..###.#.#..######....#.#......#..#..#..
.#..#.#......####..##.....#..###...#........#.#...#...##.####.###......#.#.
##..F.#..#..#....#...#.####..##.###.##.#...##.#.....#.#.....##..#..###...#.
..##..#.#.#.##.###..#..#..####.........#...##.....##..#.#.#..##.#..###.###.
#.#..#.##......###.#..H.#.##.#..#####.F.......#..#...#....#.......#..#.#.#.
#...#.....#.#....#....###.............#.#.#.#..#.##...#..##...###.....#..#.
###....#####..##..##..###.#.#.....##.#..##.#.......#..#.##......#....#.#...
##.#....#...#.#..#.#.##...##..###..#.#.....###..###.##.####.#.##...#....#.#
......#.###.#..#.....##..####..#.#.##...#.#.#..##.#.#..........#####..#.#..
.##.#....#...##.##...###...#...#.##.#..##...###......#.##........##..####.#
##.#..#.....###....##..#.#.#.#.#.#..##..#.#..##..#.....##..###..##.#....#..
.#..#.#F##...###........#.##.#...#..##.####.##..##.#..###..#.##.#..#...##.#
.##.....#.##..####.#####..#.#.##.#..##.F.##..####..#.#.##...F.#.#....##...#
......##...####.............#..####..#########..#.#.##....###.#..##.....#..
..#.#..###......##..####.#..##.#....##.#...#.##..#.....#.#.####..#..###.##.
..#..#..#.#.#....##.#..#.##......##.#...#..#.....#.#####.....#####.#.#....#
#..#.####....#.#..#.##...##.##...#..#.#...###...#..#..#.#..####.##.......#.
#.###########..#..####.##....#...##..#.........#.#.........##....####......
#.#.#...#####.###.#......#.#...#...###..#.##.#.#....#...#.####.#...#...####
.#..#.#.#.#..####..#..#.###.#####.#.####..##.####.##....##.#.........#....#
.##.......##..#..#.#.#......#.##.....##.###..###.#...###.#..#.#.##...#...#.
.#####.#.#..#..#....#...#####.##.#.......#.#...#.##.##....#.####...#..#....
..#...#...#.##..##.#.##..#....##.#...##.#.....#...#..#.#.#.....######..#.#.
.####....#...#....#.....#..#..####..#..#....#.#.#............#.#####....#..
......#.#..#..#.#.....#.##...#..#F##..#..#..###.##.###....##..#....#.##.###
..#.#####.......##.#..#.#......##..#..###............####...#.###..##..#..#
.#..##....#..#....#...#.##...###...##.#####.#.......#.##.#.##.##..####...#.
.#.##.###..#..##.###.....#.#......#....##.#.#.###.#.#.#..####...#......#...
.#.#..#...##...#..#.##.###..##.#.###.#.##......#..##...#.#..#.#.#..#.#..###
##.#..#.##...#..#...###........###.#.##########.....##.#.....##.#F#.##....#
.......#....#.###.......#.....#.##.#.##....#.#.##.###.....#....#....###.#..
####.###..###...#.##.#...##.#.#..........###...........##.#..#.###...###.##
.#.#..##.###..#...#...#.#..#.#...##.##..##.###.....###..#..#..#..#.#.##...#
.#....#....#####.#..##........#...#..#.##...###..#....#.###.###....#..#.##.
.#.#....###..#..##..##..#..##...#..#.######..######..#..###.####..#..##....
.#..#....###...##..##......#...##......#....#...##.##..#.........##....##.#
....##..##.....##..#..####.#..##.........###..#..#..........####.##..#..#.#
##..###..#.##.....##.#..###.####...#.........###.....##.####.##....#F##...#
..###.#.#..#.#..###..##...#.......###........#..##...#####...#####..#..##.#
#.###..###.#.....#..##..#..#.####.###..#.##...#.###..##...##........##.....
..###....##.###.#...###...##...#.....#######..#.#...####....#..#.##.#.#.##.
....###...#..#.######..#...####.....##..##.#....#..#.##..###..##.###....#..
..##....#.##.#.....##...#.....#......##.#.....##.##....#.....###..###.#####
#......###.....#####.#.#..#.#.#..####...#.#.###........#.##.##...##.....#.#
##..#......####......#...#...#.#...#.##....##..##.#....##....###...###.....
...##....#...####.#..#..##..#...###...##.#.#...#...##.###..#.##.#..##...#.#
#....####..#.#..#...#..##....#...#.##..#....##..#..##..####..#..#...####..#
#..##...#.#....##.#.###.#.##...#.....#...#..###..#F..#...#.#..#.........###
####..#...#.#.#.......#.#.#.####.###...###..#...#.####.#...#..##...##..#.#.
..###.##.###..##.###.#...#..#..#...#..#...#..##.....####...#####.##........
....#.#F##...#....##.##....##....####..##..#......#...#..#..#.#..##.##.####
##.#....#...#..#.#####.#......#.#.###.###.....#.#####..#..#.#...##.###.....
.......#...##...###...F.##..###.....##...#.##...#..#.#...###..###...##.#.##
#..###..###....####.##.#.......#...###.###...#.##.....#...###.##..####....#
.#..###...###........#####.##.#..#......###.#..##...#.####.#####....#..#...
..##.....###....#...##..#....##...#...####..#.....###........##..###.#####.
......####...#...#.#....#..####.#..#.##.........##....#..#.#.....##.......#
##.#...#..####...##..#...#.#..#.#..###..###.#..##.##...###..#..#..##...####
.....#........##..#..#.###......#####.#..#..##.F#.#..###.#...#....#.#..#.##
##..##.#.##..##..#..#..###.##...##..#..####...###..#.##.......#.....#..#...
.##.#...###..#.....#......##...#..#....##...#..##..#.##..##..##.#.....#..##
..##.#F#.#.##.#.#######......##...##....#.##...#..##....##.##...#...#...#..
#..#...#.#..#..#..###.##.#.#.#..#....###....##.#..#......#........#.#####..
..#.#....#........#.#.#....#.##.#.#.###..#####..#.##..#.#.#...###...####..#
.##..##.......#...#.....##.###..##...#..####.##.#...#.#.....#.###...#......
.........#....#.....####.####..###....####.#..#.#.#..#..#....#.##.##.#..#..
#####..#.#.#.....#..####..#.....##.#.#.#....#.....#...##.#.##..#.#.#...#.##
#.#..#..##.#.#.##..#.###.##.#.#..#..#...#.#.#...#.###.##....#.#..#..#......
#....##..#.#..##......#.....###.##.###F...#..#.#####....##....#.#....#.#.#.
#..#....#..#..#...###.#...##....##.......#.##....###.#.##..##...#.##.#.####
##.##..#...#.#.##.##......#...##.#.##.#.#.....#.###..#.###.#..#....#.......
##..#####..#...##...#...#.#.#..#.....#..#.#...#..###.#..###...#....#.#...##
6)
    
seed = 419079253
N = 86
M = 10
K = 5
sx = 81
sy = 33
p = 0.21899626660490412
.............#....#...#....##...#..#.....#......#...#.......#...##.....#..##..#.......
#.##.......#..#...#..#.#..#...#.#...........#............#...................#........
...#.................#..#.###....##......#..#...........#.......#...........#......##.
..............#..#.....#.......##..#......#.###.....#...#........###.#..#.........#...
.........#.####....#..#.#.###..#....#.............#....#......##......#..#....#..##...
.....#.......#....#.......#.#......#........#.##..#..##...#....##..#..#..#....##...#..
#......#.....##...#...#.......##.....##.#..........#...###..###......#......#..#......
....##.#.......#.#.....##.....#......#...##.......#.........#.......#....F......#...#.
......#.........#........#..#.......###..#....#F.#...............#....#..#..#.........
#...#.................#.#..#.#...#.#...#.................F................##......#.#.
..................##..#.#....#......#..........#....#.###....#......#.#.......###.....
..##....#......#......#.#....#.....#F.........#.......#......#....#..#..#..#......#...
.......................###.........#..............#....#....#..#........#....#..##.#.#
.#..#....#..#.....##.#................#.##..........#....#.#.........#.#......#.......
....#..............#..#.............#.......#..#.....#.#.....##...#...#.......#...#.##
.........#..#...........#...#..#...........F.#.#..##...#................#....##..#....
................#...#..........#.#........#...#.....#......#.....###........#.....#..#
###......#.....#............#........#..#..##.....#..........#.#..##.#....##..........
...........#....##................#.#....#...#..#..............#............#...#.##..
...#........#..#.##.#.###......#..#............#...#..#....#.....#...#...........#.#..
.........#.......#........###......#........#..#.......#......#....#..#...............
...#..#........##.........#.......###..#..#...............#.....#.#....#.....#........
...................####.....##.####...#.#..#..#..............#.......#..##.#..........
...#......#.#...........#.#.#...#....#....#.#..................#....#..#......#.#.....
#..#......##......#.#..#....#........#.###...#...#.....#...#..#..#.......#......#..#..
##....#..#.#.#....##....#.##....#.#.#...###.......##.#.#......#....#......#...........
###....#...##...#..#.#......#.....##...#................#......#.###.#....###.....#.##
..#....#..#.....#.#.....####.........#..##.....###.#.##...#...#...#...#..##......#.##.
...#..#.#..#..#.#.......#......###....#...#....#.#.##......#.#...........#..#.#.......
..#........#.......#.#.....#...#...#.......#.......#............#..#.....#.#.........#
.#....##...........###.......#.......#.......#..#...#.....#...##.#..#.#.....####.#.#..
..##...#.##....#.#..........###.......#.......##.##...#....#.#........#..#.......#....
..#.#..##..###..#....###...#......##.....###.....##.#..#.....#......#.......#.....###.
..#.....##...#......##........##.#.#.#........#..#..............#........#........#..#
....#......#....###..##.#....#.#.#.##......#...#.#..#.......#.#.##.#..#....#...#..#...
.............#...#####.#####...#.......#.....#............#...###.........#.#....##..#
.#...............#..#..##.......##..........#......#.#....##.#......###......#...##..#
..........#...#.#.............#..........#...#....#...#.......#.#...#..#.............#
................#.........#....##...#..#.....##.....#..#....#.#...#..#.#.......#....##
......#..............##...#.##.#..#..#....##...##..#..#...#............#.....##......#
........#.....#..#.....#...#..........#...#......#.F......####.#..#.......#.#.........
.....#....#...#...#.......#..#...#........#...#......#...#.#.......#...#..#.....###...
..........#.....#..#.#.#...#...........#.....##.......#.......##....##....##........#.
#..#..#........#.##...#......#....#.......#..#........#....#.#........#...#...#.#.....
.........###.....##..........##.#.##....#.........#.#.#.....##..##......##....#.#.#..#
.....##....##............##.#......#.#..#.#..........#.....#.......##.......#..#......
##.......#.#.#.#..........####..##.....#........##...#.#..#.#.#....#........#....#...#
.##....##....#.....##.#...........#....................#..............#......#......#.
..#........#....#.#.##.##.........#...#.......#....#.#.......#.##.....#.#.......#.....
......##..#..............#..#..#....###...........#...#........#.#.##...#......#..#..#
#.#.......##.###.......#..##.######..#..##.#...#...#.#......#.#.........#..#...#.....#
...#........###.....##.....#.#.#.....#.......##...#..............#.#.###......#.......
F.......#.#...............#..#.#.......##......#........#........#.#......#......H.#..
...#.........##...##...#.#........#..#..##...........#.#.......#.#.##...##...#...#..#.
.#.##........#...........#.#..........#...#.......##....#.##....#...#....#...#.#.#..##
##..#......#..#...###........#.........###.#.......####.........#........#..#...#.....
..#..........#.#...#...#...#..........#.......#.##...##..#.#.....#.............#......
......#...#.#....#.......#..#.........#.......#..#.##.##.#.#..#...###.......#.#..#.#..
............#..###........#.#.#..#.................#..##....##.##....#....#.......##.#
#.............#....#............##..#...#.........#......#F..............#.##.....#..#
..#....#..#..###.###..#.#..#....##...........#..#.#....#.........#...........#......#.
.#.#.#.......#....#...##......##.....#........#...##...##..#..##...............#.#....
#...#........#......#.........#.....##.#.......#.##..#....#..#........##...#....#..###
.#...........##.#.....#.......#.....#....#.##..#..#...#..##.#.........#..#.........#..
..........##.....#.....#.##......#...#......#.......#..#......#....#.........#........
.......#...#.#...#..#........##...#...#.##......#.......#.#......#.#.......#........#.
..........#.##.#....#..##.#.............#.....#..#.........#......##.#..#...##..#.#.#.
#........#.....#.#........##...#..#..#..#.#.....#......#.#....#..#.........#....#.#...
.F.#..#...#..##................................##.........#.......#......#.#.#.....#..
.#.####.#.#..#..#....#....##.................#........#...#.....#...#..##.#...##......
..#...........#.........#.#.....#....###.......#.#..#..#..#....#......#...##.........#
.......#.#..#.....#..#.#....#.#.....#...#.#..........#..#....#####.#...........##..#..
.....#.................##.#..#...........#.............##...#.#.....#...#.........#.#.
..........#....#......##...#.##......#..........#..#.............#....#...#....#.....#
.....................##.#.#.#.#...............#...#....#.#..#....#......#.##...#......
.#.......#.....######.#..##..........#............#................#..#.............#.
...###..#..............#...##....#.#...#.#..........#....#....#.#....#.....#.#......##
..#.....#.#...#........F#.##....#.#.#.....#....##....#.#..#.#.........#.#.............
..................#.#..........#...................#.#......##.#........#......####...
.#.#.....#....#........#...#........###.#........#..##...............#....#..#......#.
.#.........#....#......###.........#......##.#..#.....##....#........#.#...#.#........
#.#....#.#.##.##..#.........#.#...#..###....#...#...........#.....##...#..#....#..###.
..#.####......#..#..#.#....#....#......#..##.#.##.##........#.....#....#.....##.#.....
..............#.....#.......#.#........#..#....#.........#......#...##.............#..
....#....#...#......#.....##......##..#....###.##..#..#.....##...##.#...........#.#.#.
...#..............#...#.#....................#.......#.....##.....#.......#...#.#.....
7)
    
seed = -2139897132
N = 91
M = 19
K = 10
sx = 28
sy = 16
p = 0.0843895027036643
............#........#.....................#....#............#.....................#.......
...................#.....#.................#.#................#...#.......................#
........#.#....#............#...............#........#.#..........#..........#.............
#F...........#...............#....#...........................#.......#....................
##...........F..........#.##....................................#........................#.
.............................................................#.............................
...........#.#..........#....#...............#.........#..................#........##....#.
..F#...........#.....#.#........#........................................#................#
.....#.........#.................#........................#.............#...#.....##.......
#.....#.......................#...#........#.............##...#............................
.......#.............#....................###..............#...............................
.......#...........#.#.##...................................#..#.......#F..................
..............#.......#...........................#........................#....#....#.#...
.....#....#.#.......#.......#...#.#.....#............#...#.......#........................#
.#......#...##......#........................................#...#..................##.....
.................#.........#.....#.....##...#..#.......#.......#....................##.....
.......#....#...#........#.....#......#......................#....#...............F.....#..
...#........#..................#...................#....#.......#..........................
..............#..........#.......#............###......................#........#..........
...#....#.##.........#.................#....#...#............#.........................#.#.
.....#.......#........#.................#.#.........#..#..............................#....
.##..........#...#............#......#..............................................#......
#.........................#........#........................#.....#.........F..............
...#................#........................#..........#.#................................
..................#.........F.........#....#.......#........##.....#......#.........#......
........#..........#................#F.#.................#.#..#......#.....................
..................#..................#................................#............#.......
...#..................#.............#..............F................#.#.........#.....#.#..
.........#...#....#......#...#......#.........#.........................#.......F#..#......
........F..................................#......##...#...................................
.................#.......#.................#.............#.#..............##...............
..........#.#......#F........#....F.............................................#..#..#....
..........#............#..#.......#.....#.#...#...........#...................#....#.....F.
.........#.................#.......#.......#..#.........................#.....#.......#....
....#...#......##............#........#...........................................#.......#
.......................#.................................................................#.
......................#.........##..................#.......#.........#.......##...........
#...#....#.........#....##..............#.#...#..........#...##...#........................
..............#.............#..........................#........##.....#.#..........#..#...
......#..........#.....#...#..........#.......#.................................#.#........
...................###..#..#.....................#.....................#...................
........................##.....................#............................#...........#..
.........#........#....#...............................#.............#.......#.......#.....
.........#......F......#...........................#.......#.#.......##....................
....#...#.......................#.#...#......................#..............F.#.#..........
..#..#...............#............................#.....#...#...#........#..#.............#
.........................#..............#...........#.........##...........................
..#............................................#..............#.......#..#.....##........#.
.....#....................................#....................#...........#..#............
#.......#......##...............#...#..................#..#...#..............##...#...#....
.....................#.......................#.#.................#...#.......#.............
..............................#..#.#.#.......................#..........................#..
...........................................................#....#......#..#.....#..........
.#..............#.......#........................................#......................#..
..................#.#........##.........#..................#.....#.....#.....#..........#..
...................................#.#..#..................#.......................#.......
...........................#..#...#.#................#....#....#..#.....#...............#..
#.......#.#..#.#..........................#...#...........#......#....#........F...........
.#...............#...................#.............#......#...........#.............#......
................................##......................#..................................
........#.....#...........................#..............#......#...#.....#................
............#.....#.................#.............#.......................#.....#..........
..............#..........#.#....##........................#........#..#..#.................
.................#.........#......#..#..........#........#.................#....#..#.......
#.........................#..............#......#...#..##...........#....#....#............
........#......#..#..........#...........#.#.....................#............#..#....#....
....#.............#........#..........#...#......#........#.#..............................
.......#.#....................##.....#...........#.........................................
..............................#......#.#....#...................#........#.#.#.#.....#.....
............................#........#...##.........#....#............#......#.............
...................#............#...................#................#...#.................
.#...........#...##...........................#.........#..................#...............
...............#.....#...........................#...........F.....................#...#...
.#.........#.....#.......#.......................#.........#...........#......##......#....
....#......#.#.............#H..#.....#......#......#.........#.....................#.......
...........#..............#...........................#...........#...................#....
........................#.......##....##..#.........#...............#...........##.........
..............................#...#........##.............#.......#..............#...#....#
.....................................#...#................#....#.#......##.............#...
........................................#.........#................................#.......
..................#...........#.....................#...............#............#......#..
.....#........................................#....#.#......#............#....#......#.....
.#.............#......#..................#.........#............F...................#......
...............................#.#........................#........#.......................
.#...................#............................................#...........#...#......#.
.....#.......#..........#............#......#.........................................#..#.
.....#.#...........#...#......#..........................#...............#...........#.....
.........#.........#.......##..........................#..#................................
......#.................#....#...................#.....#...............##.................#
....###..............................#..........#....................#.........#.........#.
..................#.....................#..................................................
8)
    
seed = 1340840114
N = 98
M = 15
K = 7
sx = 37
sy = 43
p = 0.3366800755790871
.....###.##.##...#......#.#...##...####....##.###..#........#..#..##....#.....#.#####.....#...#..#
.##.......#...#...##....#......#.#.#.....##.#...##..###.#.##.#.#.#.#.###........#.#.#.......#.....
#.####.......#..#.#..#......##..#...###...#.#......#.#...#............#.....#.##.....#.#.#.###...#
.....#.#..##.....#.....#..#...#.##.##...#...#...####...####....#...##.##.#......#.##...###.##...#.
....##.##.#..##..##.....#..#.#.#....#.....##..#..........#.#.....#.......#......#..#..#.#.....#...
#....#........#....###..###......#...#.#.#....#.#.#.##.....#...#.#.###...#..........###....##.#...
..###.....##.#.....###...........#....#......#..#.#...........#.#.#.#.....####.......##...##...#..
#.##.##..##.#....##.#......#....#...#....#.###....F...###..##.....#...##......#.#........##.......
.......#.........#....#....#######..#.###..#.###...#.....###...#.......#.#.###....#..#............
..#.##......#...#....#.#..#........#.##.......####....#.#..#..#..#....#......#.#.#######..........
..#..#.#..#.....##.##..##...##..#......#.#....#.####.###.#..#....#....#####...#..#..#....#.....F.#
.##..#....#....##..#...#..##.......#..#...#..#.........#..#...##...###......###....#...##.....#..#
#.#...#.#.....#..####..##...###.#.....#.#......#.#.#..#.#....#....##.......#...#.#.#..#......#..#.
..##......#.....##...#.#...#.#.......##....#.......###..###...#............#.....#....#........##.
......#....#.#..#...#...####......#........####..#.#..#.#..#.#.#.#........#.#.....#...#.....###...
...#......#.#.###..##...#.##...#.#.#..#.#.#...#...##......#..#...##.....###.#.#.#..#.#.#.#.##.#.#.
..#.#.....#.....#.#..............#.####.#.#...#.###..###..##..##.....###..#......#.#............#.
.##.#..##.#........##.#..#.##.##.#......##..#........#.....#...####.....#....##.###.#.#.##..##.#..
.##.##...#....#..##....##...#.#...#.#...###.#.##.#..#...#....#.#....##.#...###.##.#..#.#####.#....
#.#..#..###.....##...###....#...#......#...##.#.#..#.#.##..#..#.......#....##...........##...#....
...#.#.#.###......##.#....#...#....#.#..#...#...###...#.#.#.##...#......#.#...#.#...#...##.#.#.##.
.##..#.#.##...#.........####.#..#........#.#.##...#.#....##.##.#..#..#..#........##.##........##.#
.........###...#.#..#.##....#.#...#.....#....##...##......#.#..#.###..##...###.....#....#.........
..###...#...#...#.#..##.###...#.##..#......##.......##......#.#..#.##.##.#.......####.......####..
#....##..#...#....#..#........#..#...#.##.###.......#..#.#.##..#.....#...###.#...##...#..#........
.###...##..#..#...........#......#...###...#..........#.#.##....##..........#..##..##.#...#...#.#.
.....#.........#....#..#.####........#..#..##.#.###.#.#.#.###..#.#..#.##.....##...####..#.#F......
##.#..##.#..##..##.##......##....#.#..#....#..##..#..........#.#.##......##......#.......###.#..#.
.#####.####....#....#....#..#..##.#..#.##..#.#....#.......#.#..#.##..#...##.....#........##.##...#
...#.#...#.##.#.##..#...#..........##...#....#.#.....##......###.....#........##.....#...#...##.##
#..#....##..#.#..#..#.##...#........#......#.##..#..#......####......##........##..#.........#.##.
.....#..#.....#........##........#.#...#.##........#.#.##...................##...#..##.#...#....#.
###..##...#.....###...#.#...#...#.#...#..##.##.F...#...#.............#.....##.#..#...###.....#..#.
..#.......#....#.#.##...##..##..#......##..#........##.#.#....#....#.......#..#..#.#..#...#.#.#...
...#..#..##.##...#..#.#...#.#.#..#.......#..##..#.#..#.####..#...#.....#...#...#...#..##.#.#..#..#
##..#.#......#...##.#.#.#.......#......###....###.#.........#......##..#...#.F#..#.###.#....#.....
...........##.#.....#.#...#......##....#.....##..#.##..#.##.....#.......##.#.......#......##..#...
#..#.#..#..##..##.#.....##..#....##.#....#...##..#..#.....###.#####.#####..#...#.#...##.....#.#...
##.#..#.##....###..##...#..##.....#.###..##.#.........##.#..#.#..##...#..#.##.#..#.#..##.#..##..#.
#..#....#.#####...#####.#.#..###.###......#.#.##....#.#......##.#####...##....#...##....#..#....#.
#.........#.#...F#####.F.#..#.#.###....#...#..#.#.#..#...#...##......##..#..#....#......##...#.##.
.#....#.....####........##....#...##.#.......##.#.......#.##.....#..##......##...#....######..#.#.
....#..#.####.......#.#..#..##.....#.#.#.#...##......##...####.#....##..#....##.###.........#...#.
.#..#........#.#....##....#...##F.#...#..............#.#.#..#.....#.#.....#.#......##...#..#.###..
....##..###.......#....#......#...#................#.#.#..#...#......##....#..##.#..#....#...#..#.
.#..#..###.###.#.....###..#......#...###......##..#....#...#...#..#..##.##.#..##.#....#..........#
...#.#......##.......##.#..##.####.....##.##............#.#.###.###............#..#.#.......##.##.
.#....#.#...##.##.#.......##.#.........#.##.##...###.##.#....##....#...##....###.#........####....
.#..#.#.#....#...#.#.....#.....#...#......#.##..###..#...###....#...#..##.#.......#.#.#...#......#
.##.............##.....##.#.##..#..##....#......#.#..####..#.#.#..........#.......#.#.........#...
....##.####...####......#...#.....####.##..#...#..##.####..#.##.#.#........##.#.##..#.#...#.#.#...
.#......##.#.#...##.#.##...#....#.#....#.......##.###..#..#........#......#......#.##...#..#..#...
#.#...#.#..##....###...#...#.#.####......#.#.........#..#..#.......#.......#...#...#......#.#..#..
#...##....#.#.#...##..#.#..#.....#..##...##.#..#.#.#.#......#.#...#.#.#...##.#.......#.#..#.......
...#.#..#...##..##.......##.....#....H..#...#.#..#..##..#.#...##.....#...##.....#...#.....F.##.##.
#.#..###...###.#.#...##..#.....#....#..#.....#...#....####.#..#.#.##..##...#.##...###....#..###..#
.###.##..#...#....####...##..#.......#...#....###.....#.#...#....#.#...#.....##...#....#..........
.....##.#.##.#.##..#..#.#....##.#.##..###.......#...#.#.#.##....#.......#..##..#..#.#.#......#..##
...#.#.#...#..###..#...#....#..#..##..#.#.#..#....#...#....#.#.##...####.#.##....#.#..##..#.....##
....##.#.#..##...#..........#...#...###.......#...#.##......#....#.###....##.##.#..#.....#....#...
........#...###........#....#.........#..#..#.....#..##.........#..#..##......#.....#....####.....
.#.#..#...####.................#.#...#.###.###..#....###..........##.###.....#..#.#......#..##.##.
.###..#..............#.#.#..#...##.#......##.#...##......#..##.###...#...#.....##....#.##.....###.
..#.#.##.#.#.#.#..#.#..##.#...#####.....##.#.#...##...##........##......#.#....#.......##..##....#
.........##....##.....#...#......#..#...#.....#..#.###.##.#...#...#...#.#.#......##.#.##.....#..##
...####.####......#.#.#.##....#.##..#..#..#.##..........#.#....#.......#....#..##.#...#..##.......
.##...#...#...#....#.#...##......#.#....#........##...#..####.#.#.....##.##.......#.#.#....##.#...
.#....####.##.#.......#..##.##..#####..#.##.#.#.#..#..##.#......##..#...#.##.........#.....##.....
..................#.....#.#F........#.#...#.#..#..#........##...#..#...##.......##...#..#...##...#
...#..#.##.####......#..#....#####.#.....#.#....#..#......#...#.###..#####..##.#.........####..###
....#..#...F##.#.##..#....#..........#......#..#.............####....F#....#...#....#.#....#..###.
...##..#.#.###.......#....##...#.###.##.##.#.#.##.#......#..#......#...........#..###.##.....#.#..
...##.##...#....##.....#.##....#........#........#....#..####.#.#...#...##.#..###..##....##......#
....##.#.#....##.#.....##..#...#..#.##..#..#..#.#..#.......##.#.#..###...#...###..#..#.#...#.#..#.
.###.#.####...#..##..##..#.....#.........#.....#.##..#.....#.....#.#...##............#..#.#.##....
.#.....#.....#.#....##...#....#.....#.....#..##...#...#.##.....##....#.....#...#######......#..#..
...##.#.........##.#..##......#.#..#.#..#.#....#..#.#...#.#.###...##...#.#..##.....###...##.....##
##.#....#.......#..#.....#...##.#..#.....###......#........##.#..###.#...###......#..#...#.#.##...
.....#.#.....#...#...#..#.....##...#.....###.##...####.#.#....##..#.#...##.##...#.#.##.#...#.#.##.
#....##...##....#.###...........##....##.#....##....#.#.....#..###..###.#....#............#.#....#
#.....#.....##.##......##.##.....#.#..##..#.#...####....#.##..#..#....#...........##.###....#.#...
...#....##...#.#.#.#.##...#....###.............#....#.##....#....#.##......#.#.####.###....##...#.
....#.#..#....##...##...#..........##.....#F..#.#.#...#..###....#..##.#.##...#...##..#.#.#........
.##..##...#....#.#..........###...##..#.#...........#.#...#......#..#.#....###..#.#....##.....#...
#.....#.####....#..#......#...#....#...#.#......#.#..##...####....#..###...##.##...###.##.#....#..
##...#..#......#.......##.....#.#..#.....##.##.#######.#.#..#.....#..#.#.##...###.##.......#..#...
.#.##########..#.#.##.#.#.#.......#..#..#..#...#...##...###...###...#....#...##....#.#...#...##...
......######....###......#...###......##....#..#...##.........#.#...#...##...#.....##....#.##.....
..######....#..#.#....##.#..#..#...#.#...#.#.....#..#.......#....###...#.##..#........##.#.#.#.#..
#...#...##..#.#..##...##.#.###.##..##.##.##..#.........#.###...##........##..#...#.#.#.........##.
...#...##.#.####....#.#........#..##......#.##.#..##..#....##.#.......#...##.......#..........#...
.##.#.#.......#.#.#.##...##.#.....###...#....#.##.......#.#.....#####.......###..#.F.....###.#...#
#.......##.........##..#............####.....#.###..###..#.##....##..#.#.#..#..#.#.##.######......
....##.#....##.##.....##.......##....##...#.#####.......#......#.#..#..#....#..#..............#...
......#..#.#...#..###..#...#.###...#....#...#.#.........#.#.#..###..#.#..#.##......#..####......##
#..#...##...##.#..##..........###...#.#.....#............##..#..#.#...##.#F..##..##....#...#..#..#
..####..#.##.##......#...#.#....##.##.....#....#......#...####.##..#.##...#..........#......###.##
.#.....##....#......#.....##......####...#..##....###..#..###......#...####.#.#.#.#...#####.......

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)2010, TopCoder, Inc. All rights reserved.