JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Lightning Round
Problem: KnightsAndPawns

Problem Statement

    You are given an H x W chessboard with some pawns placed on it. Place several chess knights on the board so that each knight attacks exactly two pieces (pawns or other knights). The pieces attacked by the pawns don't matter.

For example, this is a valid knight placement for example 0 (seed = 1). The knight in row 4 attacks two pawns, the knight in row 1 attacks two knights, and knights in rows 0 and 3 attack a pawn and a knight each.

Implementation

Your code should implement a single method placeKnights(String[] board). board[i][j] will be 'P' if there is a pawn in the cell in row i and column j, or '.' if there is none.

The method should return a String[] describing the placement of the knights on the board. It should consist of H strings, each of length W. j-th character of i-th string should be 'K' if you placed a knight in the cell in row i and column j, and '.' otherwise. You can place as many knights as you want.

Scoring

Your raw score for an individual test case will be the number of knights you placed. If your return has invalid format (wrong dimensions, invalid characters in it, knights which attacked fewer or more than 2 pieces etc.), your raw score for that test case will be -1.

Your normalized score for each test case (except the ones on which your raw score was -1) is (YOUR/MAX)^2, where YOUR is your raw score, and MAX is the greatest raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, your total score is sum of your normalized scores for all test cases, divided by the number of test cases and multiplied by 1,000,000.

Tools

An offline tester is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation and score calculation. That page also contains links to useful information and sample solutions in several languages.

Test Case Generation

Each test case is generated as follows. The dimensions of the board H and W are chosen between 10 and 100, inclusive. A pawn is placed in each cell independently with a certain probability, chosen between 0 and 60%.
 

Definition

    
Class:KnightsAndPawns
Method:placeKnights
Parameters:String[]
Returns:String[]
Method signature:String[] placeKnights(String[] board)
(be sure your method is public)
    
 

Notes

-The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing.
-The match is rated.
-There are prizes for top 3 finishers among attendees of Buenos Aires regional event and top 3 finishers among virtual participants. See the rules for details.
 

Examples

0)
    
seed = 1
H = 5
W = 10
Probability of a pawn = 0.2395486402248515
........P.
...PPP....
.....PP..P
.....P..PP
..PP......
1)
    
seed = 2
H = 55
W = 55
Probability of a pawn = 0.015368128186056328
.......................................................
........P.........................P....................
............................................P..........
.......................................................
.......................................P...............
.......................................................
.......................................................
.......................................................
P.............P.......................P................
.......................................................
.......................P...............P...............
...........................P...........................
.......................................................
......................................................P
.......................................................
.......................................................
.......................................................
.......................................................
..PP...................................................
P.....................................................P
.................................P.....................
.......................................................
.......................................................
......................P................................
................................P......................
.................................................P.....
.............................P.........................
..P.............P..................P...................
.......................................................
.................P...................................P.
........P..............................................
..........................................P............
..........PP.......................................P...
.......................................................
.......P..............................P................
.......................................................
.........................................P.......P.....
.P.....................................................
..........................P............................
..................P....................................
..........................................P............
.......................................................
...................................P...................
.......................................................
.......................................................
...............P.......................................
.......................................................
.......................................................
.......................................................
P................................P.....................
......................................................P
................................................P......
..........................................P............
..........P............................................
.......................................................
2)
    
seed = 3
H = 100
W = 100
Probability of a pawn = 0.07180990411376299
......P..................P.....P..........P.....P....P.P..........P.............P...................
......P....P...P..........................................P..........P............................P.
.............P...P..P........PP.................P..........................P.....P..................
..........PP.................P......P...P................P..P.P.P............P............P.......P.
................P.P.....................P.P.....................P....P.........P......P.P...........
......P..............P.P.P.P............PP..........P...P...........................................
..P.........P................PP.........P..PP...........P.................................P.........
...PP.............P..P.............P.........................P............P......P..P...P...........
...P.....P...................P........P...........................P.................................
.................................P.........P..................P...P................P...........P....
........P.........P...P........P........P.P...............................P...........P.............
....PP.....P.P....................P............................P..........P..................P.P...P
.........P....P......................................P.........................P.........PP...P.....
...............PP.P...P...P........P...........P..........P..............P.....P....................
..P....P............P.................P..P............P.............................P....PP.........
.................P.....P...P..P..PP........P.....P............P........P........P........P.......PP.
........................P.........PP...............................................P................
............P.......................P..P...............P..P................................P........
...................PP..PP.....P...........................P.......P............P........P...........
.............P.........P...............P.................................P........PP............P...
...............P......P........P.........P.........................P............P...................
....P..P.....P.....P........P.PP.................P....P....P.............P......P............P...P..
.................................................PP...P...............P............P................
...................................P.P...........P.................P...P................P...........
..P......................PP.P..........P.................P................................P.........
...........................P...P......P.P...................P.......P.........................P..PP.
.......................................................P...P.........P..............................
..............P.......................P......................P......................P...............
...................P.....PP.....P............................P..............................P.......
..P......P......P....P..................P.....P...P..P...........................P..........P..P....
..P........P....P..P....P...........P............P..................................................
........P...P.........................P....................................P...............P........
.P.....................................P.......P.............................................P......
....................................P................................P..P........................P..
...............P.P...PP........P........P........P.....P.P.....P.P........PP.......P.....PPP.P......
...................P........................................PP.........P............................
...P......P.......P....P..P........P..............................P..........P............P.........
........P......P.....P.........P.......................................P.........................PP.
....................P...............P..P............P.P...PP.............P..........................
....................................P........P...........P........P..........P.......P.....P.P......
......P....P.........PP.........................P..P.............P..............................P..P
..P...........P.................P...........P..............P..........P...................P.........
..............P.P...............................P..............P.............P.................P....
...........................P...................P.P.P......P..P.P....................................
.P.............P..........................................P............P........P.................P.
............................................................P.........................P...P.........
....................P........P.....P..........P...........P........P.......................P........
..........................................................P..P..P.................................P.
............................P..P.................PP.........P.........................P.............
...............PP.......P...........P..P.......................P........P.........P.................
...P.....P.......P........P...................P..............................P..P......P..P.........
................P....P.....P..P............PP.........P.............................P......P........
....................P.......P................P..............................P.....................P.
.....P.P............P...P.............................................P.............................
..........P......P.........................PP.......P.......................PP.........P.........P..
......................................P....P....P.P...P...P.........................................
.P...............P..................P...P.............................P......P..........PP..........
........PP....................P.............................P.P..................P..................
...P............P.P..............PP...........P..P......P...........P.........................P.....
P....P...........P..P..P...............PP..............................P.P......P........P..........
...............P.......................PP.P.........P.......P..P.................................P..
........PP.P................P......P.................PP...................P......P.....P........P...
.........P...P...............P.........................................P...........P................
......P..................................P..P...P.........P...........P.................P........P..
.....P....P..........P..P...P.....P.P...P..................PP..P......................P.......P.....
..........................P.........P.P...P......P.....P...............P.....P.........P............
.........P................P..........................P............P...P.P............P..............
..................................................................P....P............P...............
.........P..P.P....................P......P..P...P..P...............................................
.......................P...............P............P...............................................
............................P...............................P.......................................
...P.............................................P......P.........P........P...P....................
.P........PP.P........................................P..........................................P..
...........P...P..P................P..P............P..................P....PP...........P...P......P
PP......................................P............P.............P..P..P........P..PP.............
.....................P.........................P...........P........................P...............
.......P........P..P...................P...................P....P.........PP......P..P......P.....P.
P.........P.......PP...P........P......................P.P...........PP........P...........P........
.....................P.......P......P....P.P...............................P...P..........P......P..
.....P...........................P..................P........................P......P...............
.......P...................................................P.......P..P.........................P..P
.......P.....................P...P...PP...........P.P.PP......P....P..........................P.....
.....P.....P........................P.P..P.........P...P...P......................P.........P.......
.........................P...P........P..............P.......P....................................P.
...............................P............P................P...............P........P...P....P....
....................P...P...................................P.P.....................................
.......................P....P..P..................P.............P....P............P.........P.....P.
.................................P.....................................................PPP.....P...P
.................P...........................P................................P.....................
.P.P.............................P................P.......P.....PP.........P..P..........P..........
...........P.....................P...................P..P...................P.......................
.............................PP.................P..........P..P..P......P...................P..P....
..............P...............P..P.......P....P.........................P.....................PP....
...P....P.....................P...P...P..............P.P..................PP.........P..............
.......P...P................P......P..P................................................P....P.P.P...
.........P..................................P.............P.........................................
........P.....P...............P..P.............................P...PP.............P.....P...........
.................P.P.P....P.......................P..P.............................................P
.......................P.P...............P.........................P............PP..................
...........P....P.......P......P.PP.................P....................PP.........................
3)
    
seed = 4
H = 52
W = 83
Probability of a pawn = 0.1043136365782046
...P.........................P..................P..P...........................P.P.
....P.........P....PP.P.............P..................................P...........
........P...P.......P..P....P............PP.P.............P...P..........P.........
..PP.....P................P.........P.......P.P.............PP..P.P.......P........
....P...........P..................P.......P....P................P..........P......
.........................P...P.............P.........................P....P.PPP....
.........................................................................P.........
......P.......P.........P.............P...P.P..P.....................P....P......P.
.P........P.P...P......P.................P.............................P..........P
.................P..P...........P.P..........P...........P....P.......P...P........
..............P...........................P.......P................................
....P....P.............P.P..............P..P......P......................P.........
P......................P................P............P..............P.P....P.......
.....P........P...P...P........P..............P.................P.P................
.....P.....P............................P........P.......P................PP.......
P..P.....P..P.P...P...P..P.....................P..........P.....P.....P........P...
.........P...P......................P.P..P........................P.P..P...........
...P.PPPP.................P......P.......P........P.......P......P.........P.......
.........PP...........P.........................P.....P............................
..........P...............PP..............PP....P..................................
............P........P.............P...........PP..P.......P.P........P............
......P.........PP.....................P...........P.........P.P..P.P............P.
P.....P.....P...P......P..............................PP.P.........P..............P
...........P........P.....................P.P................P..P.................P
.P........................P.........P.....P...............P....P...P..P.....P......
......P..P..PP....................P.P..PP...............P.P...........P......P..P.P
....P..........................P..PP...........P.P........P........P..PP.PP.....P.P
................P..P............P.......P........P....P...........P....PP...P......
..........P...............P...P........................P.......P..........P........
....P..P.P......P.P............................P..P....P.P...P.............P....P..
.........................P.........P......P............P...........................
....P...P...P..P....P........P........P....................P......P.........P......
P..................P.P.P................P................P....P...........P....P...
........P..........P.........P........P........................P...P.....P.........
P............P.....P......P.................PP..P...P................P..........PP.
.P..............................P............P.....P........PP...P.................
...P...P............P.....P........................................................
..................................P..P.............................P....P..........
............P......PP...P.....................P.........PP..........P...........P..
....................P.........P.............P.............PP.............P..P......
...P......P....P...............P........................P..........P..P............
.P.....P......P..P....P............P...................P.......P.P....P..P.........
.P....P.PP...P.P..P.......P................P.........P....P..PP............P...P...
...P...........P....PP..................................P.P.P............P.....P...
............P..............................P.....P.............P.....P.P.....P.....
P.............P.........P..P........................PP.............................
.......P..........PP.....P.........P....P...........P............................P.
...........P..............P..........P.P............P........................P.....
.............................P........P................P...P...P...P.....PP........
.....P..PP..............P...............PP..........PP.............................
PP............P..P........P.........P.......................P.......P..P...P...P...
......P...P........PP.P..P.............P........P....................P.............
4)
    
seed = 5
H = 83
W = 59
Probability of a pawn = 0.029159179079913077
.....................................................P....P
........................P........................P.........
..P....................................P...................
...............................P....P..................P...
..............P...P...P....................................
................P..........................................
......................P....................................
.......P...........P..............P........................
...........................................................
..P...............................P...P....................
.........P......................P.....P.............P....P.
....P.........................P............................
..........................................P................
P............P.................P..................P........
.P.......................P.................................
.P.........................................................
................................................P..........
.....P.....................................................
..............................P............................
....................P......................................
....................................P......................
......................................P....................
....................P..................................P...
...............................................P...........
...........................................................
...........................P.........P..................P..
...P..................P....................................
.....................P...........P.........................
...........................................................
....................P...............................P......
.....P..........................P..........................
........P..................................................
.......................P.................P......P..........
..............P............................................
.......................................P...................
.P...........................P.P.............P........P....
..............P....................P.......................
...........................................................
....................P...........P..........................
...........................................................
..........PP......................................P...P....
...........P.......................................P.....P.
......................................P.....P...P..........
...................P.......................................
..............P........................P...................
...........................................................
......................................................P....
...........P...............................................
......P..............................P...P....P............
..................................P........................
......P............P.......................................
...............P...........P...P................P..........
...............................................PP..........
.......................P.....................P.............
..........................................P...P............
..............P.........P.......P..........................
...............................................P...........
...........................................................
..........................................P................
...........P...............................................
.....P.P.................................................P.
...........................................................
................P..........................................
...........................................................
................................................P..........
.............P.................P...........................
...P..P...P................................................
............................................P..............
...P....................................P..................
..................................................P........
.P......................P..................................
...........................................................
...............................P.......................P...
.................................P.........................
..................P...........P............................
.......................................................P...
....P.........................P............................
......PP.........P...................P....P................
.....P...................................P.................
.....................................P.....P......P........
..................................P..............P.........
....................P.............................P......P.
...........................................................
5)
    
seed = 6
H = 34
W = 36
Probability of a pawn = 0.3715090429184032
P.P.PPP...PP....P.....PPP.PPP.....PP
PP.P...PP.PPPPP.......P.P.P..PP...P.
....P..PP......P..P....P....P....P.P
PP.....P..P....P.P..P....P...PP....P
.P..P.P.P.P.P..PP..PP.P...P.PP.PP.P.
..P...PP.PPP..P..P...P...P.P.PP.PPP.
P...P..P.PP...P....PPP.....P.....PPP
.PPPP...PP...P.PP.......PPPP......PP
..P....P..PP.PPP.P............PP....
P..P.PP.P.....PP...PPP...P....PP....
........P......P......PP.....P......
P.PP.PP.P...P.P...........P.P.P.P...
...P.P...P..PPP..P..P...P.P..P..P...
P..P.P.P.PP...PP......P.....PPPP...P
P.P..........PPP.....P.......P..P..P
.P...P.PP..P.P.P........PPP..P.P...P
P.PP.P.PP.P...P..PPP.P..PP.P.P......
PPPP.P..PP......P......PPP..P..PP..P
.....PP..P...PPPPP...PP.P.P.PPP...PP
...PP....PP.PP.P......P.P..P...P....
P.P.P...P..P....PPP.P..P..P....P...P
P.P.PP..P..P..P.P....PPPPP.....P..P.
.....P.PP...P.P..PP...P.PP.P...P...P
P...P.......PPPP......P......PP....P
...P....PP..P.P.PP.....P.P......PPPP
......PPP...PP...PPP....P.P....PP..P
PP.PPPP.PP....PP......P....P........
.PPP...P...P..PP.P.PP.PP.PPPP...PPPP
.....PP.......P........P.P.P...PP.P.
PP.PP.PPP..PP.P.P..P.............P.P
...P.PP.P....P...PPPPP.P.P.P..P...P.
P.............PPPP.P.PP......P....PP
...PP.PP.......PP.P.PP.P...P..PP.PPP
...P.....PP.P.......P..P.P...P....P.
6)
    
seed = 7
H = 98
W = 54
Probability of a pawn = 0.18350049983845465
...PP....PP....P......P....P.P....P.....P.......P.....
..PP......P...............P.P..P..........P.........P.
....................P..........PP..PP.P....P..P.......
P........P......P.......P........P....P.....PP........
PP........P..P....P......P.....P.P..................P.
........P.P..P....P..P.....PP.........P......P.....P..
....P.......PP.PP...P......P.P...P.P..P.P...PP........
.P...P.......P.....P......P...P.P..P...PP........PPPP.
......P............................P...........P...P.P
..P...P..................P......P......P.......PP.P...
..P...P.........P..P..........PP...P..........P.P.P.PP
P.......P....P..PP..........PP...PP.P.....P...P.......
..P...P.....P.....P.....P..........PP.....P....P......
....PP.P.....P.......................P......P.......P.
P...PP.P.......PP.P.........P..............P...P..P..P
.........P.......P........P......PPP.............P....
....PP......P.P................P..P.P.....P..P.P..P...
..P..P.P......PPP....P.PP..........P.....PP.....PP...P
........P...............P.P......P..PPP..........P..P.
..P....PP......P....P..............P...P.........P....
.....................P......P...P.PP......P...........
................P......PP....PP..P......P......P......
.......P.........P.........P.P.....P...P...P..P..P....
..............P.PP..............P..P..P...PP..........
.....P.....P.P..P............PP...P.P............P....
...P...P...P..........PP....P..P................PP....
P...P....................PP.P...P..............P.P.P.P
P..P..P...P.P..................P..........P.P..P..P...
..P..PP.......P............P.P..P.P....P.......P......
..P..P..PP.P.......PPP...P........PP...P....P....PPPPP
...........P.....PPPP.PPP.P..P..PP...........P.....P..
..........P.P................P.....P.................P
...P...P...........P..P.P.......P............P..P.....
P..................P..............P.P..............P..
.P.........P.P..P...P....P...P....PP..P.P...P..P......
.....................P...P......P.........P...PP...P..
....P..........P.......PP...........P..........PP.....
...P.......P.P.PP....PP........PP.....................
......P...P..P.P.P..PP...................P...P.P..P.P.
..PPP...P..PP.........P.PP........P...P........P.P....
....P......P..P.P.....P......P......P........P...P....
P......P...P........P...P.P.....P.P....P.P.....P.PP.P.
........P........P............PP..............PP...P..
..P......P.PP..P.....P.........P.P..........P.......P.
..PP..P......P......P..P......P..P.......P.P...P..P.PP
P.PP......P...P..P......P.P.....P.......P......P......
P.PPPP.P.P.P......P..P.............P.....P.P..........
.P...P................P..PP...PP...PP.................
.....P...PP............P..........P.P...............PP
..P..PP...P.P...P.P.........P....P....P....P..P...P..P
...PP.P.P..P......................P...........P...PP.P
..........P.............P.......PP...........P......P.
.....P......PP..P.....P...P...PP......PPP...P.P.......
.P..........P...P..................PPP.P.PP..PP....P..
........P...............P..............P..........P...
.......PP.P...........P...PP...P..PP.......PP.........
.......P.P.P.P.P.P...........PPP.....PPP..P.....P.....
.......P.....PP.................PP........P.P.P.P.P...
...........P....PP.....P...........P...P....P.......P.
.PP..P..........P..................P.P.......P...P...P
.........P.......................P.....P.......P.P...P
PP.P.PP..........P....................P.....P..P.....P
...........P.PPPPP........P.P....P...P...........P....
.PP.P..............P........................P...PP.P..
.P...........P.....PP..............P....P.........P.P.
..P.......................P.P.P...........P.P.........
..............PP..P......P.......P.P......P..........P
........P.....P.P....P..........P........PP.P.........
..P......P.P............P....................P........
..P.....P.P.P.P................PP..P..........P.......
.P.......P.P.P..P.......PP.P......P.........P.........
....PPPP...PPP.......P...........P..P.P............PP.
.........P..P............P..P.P..............P....P.P.
.PPP......P...P....PP..P...P...................P...P..
.........................P....PP.....P...........P....
...................PP..........P.P..P..............P..
...P....P........P..P...PP...P.P.P..........P..P...PP.
.P.....P.......P.........PP.P..P...P.P................
.......P..........P.PP..P.......PPP..P.P..P..P...P....
........P...P..............P...P.P..P.........PP......
.....PP.....P..........P.P............PP..P..P........
.......P.........P.P..P.P.....P.....PP...P.P.......PP.
PP.P.P.....PP..PPP....P..........P....P...P..P.PP.P.P.
.....P...........P............PP..P...P.P....P........
........P..PP...................PP.....PP..P.P...P....
P......................PPP.................P..........
..P...P..P.P....P............P......P........P........
..........P..........P......PP......P.P.P.....P....P..
......P........P..P.....P..P..............P.P......P.P
.............P..........PP..........P...P.........P..P
P.........PPP......P.....PP..P..P....P..........P...P.
.........PPP..........P............PPPP.......P...P...
.PPP.P.P....P....P...PPP..P..............P.....PP.P...
...........P...P.P.P..........P.........PP............
P.....P...P.P.P.........P...P..P............PP......P.
.PP.P..P.P...PP.............P...P...P.................
.................PP.PP......P..P..PP..................
P.P...P...P....P..P..P..........P.P......P....P.......
7)
    
seed = 8
H = 49
W = 30
Probability of a pawn = 0.3036082844466211
PP....P.PP..P...P.....P...P..P
...P...P.P.PP......P..PP......
...PP.......P...P.P..P........
......PP...........P.P...PP.PP
.P..P......P....P...P....P.PP.
P.P...............P.P...PPP...
....PP.PP..PPP.....P.P.....P..
P..PP.......P.P.P.PPPP.PP.....
P.PPP...................P.P.P.
......PP.......P.P..P.P....P..
...P..P...P..PPP.P....PP..P...
...P.P.PP...P..PPP....P.P..P.P
P..PP.P.P.P.P............P..P.
.P..P.....P..........P..P.P...
........P.P...P..PP...P.....P.
.......PP..P.P.P..P.P......PPP
......P.........PP..PPP.....PP
.P....P.P..PPP...P.....PPP...P
.......P...PP...P..PP.P..PPP..
.P...PP.PP.P.P.............P.P
..P.PP...P...P..P..P.......P..
.P.P.P.......P..P..PPP........
P..PP.P.P..P..P..PPP.......PPP
...PP.P....PPP...P..P.P...P...
..PPPP.P.PPPPP.......P....PPPP
...P.PP.....P.P......P......P.
...P.PPPP....P.......P.P..P...
P.P....P.P.PPPP.......P...P...
.......................PP.....
P....P........PP......PP.P.PP.
......P......P..PP....PP.P.PP.
...P..P...PP......P.......P.P.
.......P..........P....P..P..P
P........P.......P.P.PPP..PP..
..PP.P...P...P...P.P..P..PP...
.P..P....PPPP.PP..P..P.PP.....
P..........P.....P...P.PP.P.P.
.P....PP...P.P.PP.P..P..P..P..
P......PP..PP......P..P.....PP
PP..PP.PP.PP..P..P....P.....PP
P....PP.PP...P.............PPP
.P.......P.P....P....P.PPP....
.P...P.P...P.P.P..............
...P.PP.P...P..PPPP....PP.P...
P.P...PPP.P..PPPP....P........
......P.P.....PPP...PP....P...
P...P....PPPP.P.....P..P.....P
....PP....P...P.P..P.......PP.
.P..P.P.PPPP..PP..P......P..P.
8)
    
seed = 9
H = 55
W = 74
Probability of a pawn = 0.4991993018172991
.P..P.P.P..P...P.PPP.PPPPP..P.PPPPPP..P.PPP..PPPP.PP.P.PP.PP.P..P.PP..P..P
P....P..P.P...PP.PP..P....P.PP.P.....P.P.PP.PP..P..PP..PPP..PPPPP...PPPP..
P.....PPP.PP...P.P..P..P.PP.P..PP.....P.PP.P........PP.P.P.P...P..PP..P.PP
....PP..P..PP........P.P.P.P...PP.PPPP.PPPP..P.PP..PPPP...P..PP...P.PPPPP.
..P.PP.PPPPPPP.....P..PP.P....P.P.......PP..PPPPPP..P.....P.PP.PP.PP..P.P.
PPPPPP..P...P.PPPP.P.PPPP...P.P..PP.P.PP..PPP.PPPPP..P...P..P...PP.P....PP
PPPPPP.P..P..PPPP.PP....PPPP..P.P....P.....P..PP.P....P.PP.P...P.P.....PP.
....P..PP.PPPPPP..PP...PP.P...P.P...PP.P.PP.PP..PP..PP.P..PPP.PPPPP.PP.PP.
..PP...PPPP...PP.PP.P.P..P......PP...PPPPPP.PPPPPP.P.P.P...PPP.......PPP.P
.PP.P..PPP...PPPP.PP...P...P..P..........P...P.PP..P......P..PP...PPPPPP..
.P...P.P..PPPP...P..P.P.PP.P.P...PPPP.P.PPPPP...P..P..P...P..P..P.P.P.PPP.
.PP.P..P.P..PPPPPPP.PPP...P..P.P.PPPP.PPPP.P.PP.P..PP..PPP.PPPP.PPPPPP...P
P.P...P.PPP.P.P.PP...P....PPP.PP.....PP.P..PP..PPPP.PPPP.......P..PPPPP...
PPP.P..PP.....PPPP.P...P.PPPPP.P....PPPPPPP.P....P.P..PP..PPP..P...PPP....
.PP.P...PPP..PP.P.P...PP.....P..P....PP.P..P.P.....PPP..PP.P.P..P..P....P.
...P..P..P...PPP..P...P...P..P.P....PP..P..P.P..P..PP..P.P.PPP..P.PPPP.PPP
PPPPPP..P.....P.P....PPP..PP..PPPPPPP..P..PPPP...P.P..P.PP..P..P.P.PP....P
PP.P.PPPP.PPP...PPPP.....PP...P.P..P....PPPPPP..PP...PP...PP.P.PP.PPPPPPP.
P..PPPP...PPP.PPPP..PPP.PP...PPP.P..P.PPP.P...P.P..PPP.P.PPP.PP.P.P..P.P.P
...P.P..PPP..PPPP.P..PP.PP.P.P...P.P.PP.PPP..P.PP.P.P..P.PP....PPP..P.PPPP
PP.P.PPP.P.P..P.P.P.P.P..PPP.....PP..P.P..PPP.P..PP....P.PP.P.PPP.P...PP..
P.PPP.P..P.PPP.P.PPPPP.PP.........PPP..PPP.P..PPPPPP.PP.....P.P.PP....PP..
.....P.....PPPP..P.......PPPPPPP.PP..PPP.PP.PP.PP.P.PPP.P.PPP..P..P..PPPP.
PP.P.PPP...PPP..P...P.P.PP.PPP.P.....PP..P.PP.P....P.PP..P.PP.P.PP.PP.P.P.
PPP..PPPPP..PPPPP.P......PP...P....P..P..PP.P...P..P..P..P.PP..P..P..P.PPP
..PP...PP.P....PP.P.P...PP.P.PPP.P...PPPPPP.PPPPPP..P..P.P....P...P.P.P..P
PP.PP...PP.P.P...PPPP.PPPPP.PPP.P....P..PP.PPPPPP.P.P..PP......P.PPPPP.P.P
P..P...P.PPPP.P..P.P.PP.P.PPP.PP..PPPPP.....PP.PP.PPPPPPPPP.....PPP..P.PPP
..P..P..PPP.P..PP.PPP.P.P.PP..P.PP.PP.PP.P.P..PP.PPP..PPPP.PPPPPPPPPPP.PP.
P.PP..P....P.PPP..PP..PPPP....PPP.P..PPP....P...P.P..P..PP..PP...PPPPP.P..
.........PP..P.PP.P...PP.PP.P...P..P..PP....PPP..PPPPP..P..P...PPPP...PP.P
PP..PP.P.PPPP..P.P.PPPP..PPPPP..PPPPPP..P....P.PPPPPP...P.......PP.PPP.PP.
PPPP....PP..PPP.PP...PPPPP.P..P..P.PPP...P.P..P.PPP...P.PP.P..P.P.P..PPPPP
.P.PP..P.PP......P.P.PPP.PPP.PPPP...P.......P.PP.PP...P..PPP.P.P.PPP.P.P..
.P.PPPP.P......P..P.PP...P..PPPP...PPPPP..P.....P..P...PP......P..PPP...PP
PPPP...P..P...PPP....P.PPPP.P..P.PPPP.PP..PP..PP...PP.P.P.P.PPPP....PPPPPP
P...P.PP...PP..P.PP.....PPPP.P.P..PP.PP.P.P.P...P.P..P.P...P.PPP.PPP.PPPP.
.PP.PPP.PP..PPP...PPPP.PPPPP.P..PP..PPPP.PPP...P.PP....PP..PP.PP.P..P.....
.....PP.PPP.PPP.P......PP.....P.PP...PP...P.PP.P..PPPP.P..PP.P.....PP.P...
P.PP..P.PPP...PPP.P.....P..PP.P..PPPP.P.P..PPP..PPP.P..PP.PP..PPPP.PP.PPPP
......P.PP..P.P....PPP..P..PP.PP...PPP...PP...P..PPPP...PPP.P....PP.PP.P.P
.PP...PP..PP..PP..P...PPPP.....PPP.P.PPPPP......P.PPPP...P.P.PP.PPP.PPPP..
.PP...PP...P.....P.PP..PPPP.PPPP..P.PPP..P.....PP.PPPPPP.PPPP...P....P.PP.
.PPP..PPPPP..P.PPP.P.PPP.P..PP.PPP.P.P..P..P..P.P.PPPPPPPPP...PP.PP..P...P
...PP.PP...P.PP.....P.P...P.P.P.PP...PPP...........P.PPP..PP.P....PPP....P
P...PP.....PPPPPP.P.P.PPP.P.P.PPP.PPP....PPP..PP..PPPPP.PP.P......PPP.P.PP
....PP..P...P.....PP.PPPP...P..PP.P..P.....P..PP.PP.PPPPPPP.P.P.PP.P.P...P
.P...PPP....P......PPP.PPPP.PPP..P...PP.P.P......P....P...PPPPP.PPP..P.PP.
P..PPPP..P...P...PP..PP.PPP..PPPP...PPPPPPP.P.....P.....PPP.PPP....PPP..PP
..PP....PPPPPP.PP..PP.PPP......P.P.P..P.PP.PPP.P..P.PP.P.PP.P....P..PP.P.P
PP.P...P.P..PPPP..PP..P.....P.PP..P....P..P.PP....PP...PPP.P..P........PP.
.P....PPPPP..P.PP..P.PP.P.PPPP.PPPPPP.P.......PP.PP..P.PPP.PPP..PPPP.P..P.
P.PP..PP.P.PPP..P.PP.P..P...PPP.PPP..PP.PPPP.PPP.....PP.PP.P.P..PP..PPPPP.
P..PP.P.P.PP...PP.PPPP...P..P..PP...PP..PPP....PP....PPP.P.PPP..PPPPP.PP..
.P.....PP..P.P.PP....P..P......PPP.P.PPP..PPP.P.P....PPPP..PP....PPPP...P.
9)
    
seed = 10
H = 84
W = 41
Probability of a pawn = 0.012842906934946075
.........................................
.........................................
.........................................
.........................................
.........................................
...........P................P............
.........................................
......................................P..
.........................................
......................P..................
...................................P.....
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
..........................P..............
.........................................
.........................P...............
.........................................
.........................................
..................................P......
.........................................
.........................................
........P................................
..........................P..............
.........................................
..................................P......
..............................P..........
.........................................
.........................................
.................P.......................
.........................................
.........................................
.........................................
..........P..............................
..P......................................
...................................P.....
.....................................P...
.........................................
.........................................
...P.....................................
...............................P.........
.........................................
............P........................P...
.....P...................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.......................P...........P.....
.........................................
........................P................
.........................................
.........................................
.........................................
.......P.................................
.........................................
...P.....................................
......P..........................P.......
............P............................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
.........................................
......................P..................
.........................................
.........................................
......P..................................
.......P.................................
.........................................
.........................................
....P....................................
......P..................................

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.