Ball collisions

Time limit2sMemory limit512 MB

Summary

Given N balls on a line, each picking a direction at random, find the expected number of collisions within time T.

Level: Medium4 of 10
Topics: Probability, Brute force, Math, Implementation
Solved: No attempts yet

Problem

$N$ balls of equal weight and zero size sit on a straight line.

When a ball rolling right and a ball rolling left meet at the same speed, neither speed changes and the two balls only swap directions.

You are given the positions of the $N$ balls. Hyobin picks the direction of each ball independently, right or left, each with probability $1/2$ . At time 0 every ball starts rolling in its chosen direction, and every ball moves 1 unit per second.

Find the expected number of collisions that happen within $T$ seconds. A collision at exactly $T$ seconds counts.

Input

The first line contains the number of balls $N$ ( $1 \le N \le 12$ ).

The second line contains the $N$ ball positions. Each position is an integer between 0 and 100,000,000, and no two positions are equal. The positions are not necessarily sorted.

The third line contains the time $T$ , an integer between 1 and 100,000,000.

Output

Print the expected number of collisions within $T$ seconds on one line.

The expected value is always a multiple of $0.25$ . Write only as many digits after the decimal point as needed, keeping at least one, so the digits after the point are 0, 25, 5, or 75. Print 0.0 for an expected value of $0$ , 16.5 for $16.5$ , and 12.75 for $12.75$ .

Examples3

Example 1
Input
```
2
5 8
2
```
Expected output
```
0.25
```
Example 2
Input
```
2
5 8
1
```
Expected output
```
0.0
```
Example 3
Input
```
12
1 2 3 4 5 6 7 8 9 10 11 12
3
```
Expected output
```
12.75
```