Potter and his brother Voldemort likes to fight at home. At a time they got into a really bad fight and Potter was injured at his head (leaving a scar that looks like lightning), but he also hurt Voldemort really badly, and his mom yelled at Potter: "Don't you ever maim your dear brother again!!" Thus giving Voldemort the very-long-nickname "He-who-must-not-be-maimed". Anyway... these are irrelevant
One day Potter woke up late and there are only M seconds left before school. He hurried out of his home but there's a long way to go.
The way to school can be viewed as a straight line with N traffic lights. The distance from Potter's home to the first traffic light is d0, the distance from first traffic light to the second is d1, ..., the distance from last traffic light to Potter's school is dN. Every traffic light function as follow: it stays at red for 30 seconds, then green for 30 seconds. Also, when Potter arrives at a traffic light, the state of the light is completely random (the probability that it's at a particular state, ex. 4 seconds after red, 12 seconds after green ...etc, is equal).
Given N and all the distance di, and the time before school M, determine the probability Potter will arrive at school in time. (If he arrives on the spot, it is also considered "in time")
p.s. Potter needs exactly one second to move one unit distance.
The first line is an integer T, indicating the number of testcases.
Each testcase contains the integer N and M, then follows N+1 integers being the distance di for i = 0 to N.
T <= 200
0 <= N <= 32
0 <= M <= 4500
0 < di <= 100
Print one floating number, indicating the probability Potter will arrive at school on time.
2 1 65 20 30 2 60 10 10 10
0.75 0.875
Info: 本題輸出為浮點數，絕對或相對誤差 1e-4 以下視為正確
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|