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) | | (be sure your method is public) |
|
| |
|
| |
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) | |
| | | 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) | |
| | | Returns: 1.3333333333333333 | |
|
| 2) | |
| | | Returns: 1.0 | | No moves will be performed, and one rabbit will remain alone on the field.
|
|
|
| 3) | |
| | | Returns: 0.9523809523809523 | |
|
| 4) | |
| | | Returns: 0.9696969696969697 | |
|