공의 충돌

시간 제한2초메모리 제한512 MB

요약

직선 위에 놓인 N개의 공이 각각 무작위로 방향을 정할 때, 시간 T 안에 일어나는 충돌 횟수의 기댓값을 구한다.

난이도: 보통10점 중 4점
유형: 확률, 완전 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

무게가 같고 크기가 0인 공 $N$ 개가 일직선 위에 놓여 있다.

오른쪽으로 굴러가는 공과 왼쪽으로 굴러가는 공이 같은 속도로 부딪히면 속도는 그대로이고 진행 방향만 서로 바뀐다.

공 $N$ 개의 위치가 주어진다. 효빈이는 공마다 진행 방향을 오른쪽 또는 왼쪽으로 각각 $1/2$ 의 확률로 독립적으로 정한다. 시간 0에 모든 공을 정해진 방향으로 동시에 굴리고, 공은 1초에 1만큼 움직인다.

$T$ 초 이내에 일어나는 충돌 횟수의 기댓값을 구한다. 정확히 $T$ 초에 일어난 충돌도 센다.

입력

첫째 줄에 공의 개수 $N$ 이 주어진다. ( $1 \le N \le 12$ )

둘째 줄에 공의 위치가 $N$ 개 주어진다. 위치는 0 이상 100,000,000 이하의 정수이고 서로 다르다. 오름차순으로 주어진다는 보장은 없다.

셋째 줄에 시간 $T$ 가 주어진다. $T$ 는 1 이상 100,000,000 이하의 정수다.

출력

$T$ 초 이내에 일어난 충돌 횟수의 기댓값을 한 줄에 출력한다.

기댓값은 항상 $0.25$ 의 배수다. 소수점 아래는 필요한 자리까지만 쓰고 최소 한 자리는 남긴다. 즉 소수점 아래는 0, 25, 5, 75 중 하나다. 기댓값이 $0$ 이면 0.0, $16.5$ 이면 16.5, $12.75$ 이면 12.75로 출력한다.

예제3

예제 1
입력
```
2
5 8
2
```
예상 출력
```
0.25
```
예제 2
입력
```
2
5 8
1
```
예상 출력
```
0.0
```
예제 3
입력
```
12
1 2 3 4 5 6 7 8 9 10 11 12
3
```
예상 출력
```
12.75
```