PROBLEM STATEMENT
Rabbits often feel lonely, so one group of rabbits decided to gather together and play a game.
The game is played on a horizontal row of N cells (N >= 2), numbered 0 to N - 1 from left to right.
Each cell is colored white, black or red.
You are given a string field of length N,
where the i-th character is the color of cell i ('W' for white, 'B' for black and 'R' for red).
There are r rabbits playing the game.
The rabbits choose their starting cells randomly such that no two rabbits are on the same cell.
Each subset of r distinct cells has the same probability of being chosen as their starting cells.
The size of the field is the number of cells it contains (which is initially N).
The following is repeated while the size of the field is greater than 2:
Each rabbit steps onto a neighboring cell.
Since each cell potentially has up to two neighboring cells,
the following rules are used to determine which cell the rabbit will choose:
If a rabbit is on cell 0, she must step onto cell 1.
If a rabbit is on cell size - 1 or size - 2, she must step onto the left neighboring cell.
All other rabbits choose which neighboring cell to step onto according to the color of the cell
they are currently on:
White: She must step onto the left neighboring cell.
Black: She must step onto the right neighboring cell.
Red: If this is her first move, she must step onto the left neighboring cell.
Otherwise, she must return to the cell she was on immediately before she was on the current
cell.
After all rabbits finished their steps, for each cell that contains more than one rabbit, all
rabbits on that cell will be removed from the field.
The rightmost cell will disappear (causing the size of the field to decrease by 1).
By the rules above, this cell will always be empty.
When the game ends, 0, 1 or 2 rabbits will remain on the field.
Return the expected number of rabbits left on the field when the game ends.
DEFINITION
Class:RabbitStepping
Method:getExpected
Parameters:string, int
Returns:double
Method signature:double getExpected(string field, int r)
NOTES
-The returned value must have an absolute or relative error less than 1e-9.
CONSTRAINTS
-field will contain between 2 and 17 characters, inclusive.
-Each character in field will be either 'W', 'B', or 'R'.
-r will be between 1 and N, inclusive, where N is the number of characters in field.
EXAMPLES
0)
"WRBRW"
4
Returns: 0.8
The initial positions of the rabbits are cells
{ 0, 1, 2, 3 }, { 0, 1, 2, 4 }, { 0, 1, 3, 4 }, { 0, 2, 3, 4 }, or { 1, 2, 3, 4 }.
For example, if { 0, 1, 2, 4 } is chosen,
they will step as follows and 2 rabbits will remain on the field:
1)
"WWB"
2
Returns: 1.3333333333333333
2)
"WW"
1
Returns: 1.0
No moves will be performed, and one rabbit will remain alone on the field.
3)
"BBBBBBBBBB"
4
Returns: 0.9523809523809523
4)
"RRBRRWRRBRRW"
8
Returns: 0.9696969696969697
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.