#AVMG1. Another Valentine Maze Game (1D)
Another Valentine Maze Game (1D)
Happy Valentine Day!
Picture Source: http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html
In this valentine day, I'm very happy to know that many SPOJ user happy to help me on my old Valentine Maze Game (2 years ago). I can't imagine what happen if no one guide me in the maze to meet her (my love), of course it will be much worse, because I can lost in the maze for long time. Now, can you help me again to compute what is expected time needed to meet her in the maze if I just walk uniform randomly on all possible dirrection without any guide? I will be very grateful for your help.
For simplicity, in this problem there will be no Chocolate, Wall, and the Maze will be 1 Dimension only.
Given a map length l, containing 3 possible elements:
'.' denoting road (I can walk on this area)
'T' denoting my position (Tjandra) at start (time 0), only appear once on the map.
'W' denoting Woman I want to meet (Destination), only appear once on the map.
Tjandra always walk one step left or right (if valid, valid = I still inside the maze) for each unit of time with equal probability, I never stop until I arrive on my destination.
Input
On the first line, there is an integer t denoting number of test cases. Number of test case will be less than or equal to 250.
For each test case there are two lines, the first one there is an integer l denoting length of map. Length of map will be less than or equal 50. Next line there are l characters, each character is element of map that has been described above.
Output
For each test case, output expected time required for me to meet her if I just walk uniform randomly on all possible dirrection. Your answer are considered correct if absolute error with judge (my) solution is less than 10-5. It's guaranteed that my solution has absolute difference less than 10-19 with exact answer.
Example
Input:
3
3
T.W
3
.TW
4
.T.W</p>Output:
4.000000000000
3.000000000000
8.000000000000
Explanation
On first test case at time 0, I have one choice: walk right, at time 1 the map will be ".TW" I have two choice , walk right or left with equal probability 0.5 vs 0.5. If I walk right then my mission is completed, so there are 0.5 (50%) chance that I completed my mission at time 2. If I walk left, at time 2 the map will be back to first "T.W" I have one choice again (walk right), at time 3 the map will be ".TW" I have two choice again with equal probability. If I walk right then my mission is completed, so there are 0.5*0.5=0.25 (25%) chance that I completed my mission at time 4. By continuing, we get the series:
2 step with (1/2) chance
4 step with (1/4) chance
6 step with (1/8) chance
...
the answer (expected time) will be 2*1/2+4*1/4+6*1/8+8*1/16+... this series will converge to 4.
On second test case, initial map is equal to first case at time 1, so the expected time will be 1 unit less than first case. The expected time = 4 - 1 = 3.