Problem1271--Tower Defense

1271: Tower Defense

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]


Bob is playing a Tower Defense Game. The game is so hard that Bob has spent several hours on it.

At the start of the game, Bob will build n towers. For every i (1 ≤ in), a tower with height hi will be built at position xi. In each round, the monster will attack the leftmost or the rightmost tower with equal probabilities until all the towers are destroyed.

After being attacked, the tower will fall left with probability p or fall right with probability 1 - p. For a tower at position xi, the [xi - hi, xi] will be covered by stones if it falls left and cannot build the tower anymore. Similar to this, the [xi, xi + hi] will be covered if it falls right. What's more, if there's another tower strictly in the covered range, it will be hit and fall in the same direction of the falling tower as domino. Note that a tower will not be hit when it is located at position [xi - hi] or [xi + hi].

Unfortunately, it seems the boss in one of the levels is impossible to defeat. After wasting several hours in challenging this level, Bob started to do something to escape from this cruel reality. He wanted to know the expected length of the ground covered with stones.


There are multiple cases.
The first line of input is an integer T (1 ≤ T ≤ 20) which indicates the cases of test data.
The first line of each case contains a positive integer n (1 ≤ n ≤ 200) and a float p (0 ≤ p ≤ 1). The second line contains exactly n integers hi (1 ≤ hi ≤ 20). The third line contains exactly n integers xi (1 ≤ xi ≤ 106). xixj for every ij.


For each case, please print the answer in a single line. Your answer will be accepted if its absolute error or relative error is less than 10-6.

Sample Input Copy

2 0.5 
3 1 
1 3 
3 1 
3 3 3 
1 3 5 

Sample Output Copy