BouncingBalls | Topcoder Archive

Problem Statement

John is playing with balls. All of the balls are identical in weight and considered to have a zero radius. All balls are located on the same straight line and can move only along this line. If a ball rolling to the right and a ball rolling to the left at the same speed collide, they do not change speed, but they change direction.

You are given int[] x. x[i] is the initial position of the i-th ball. John decides the direction for each ball (right or left) with equal probability. At time 0, he rolls the balls in the chosen directions simultaneously at a speed of one unit per second. Return the expected number of bounces between all balls during T seconds (including those collisions that happen exactly at T seconds).

Definition

Class:: BouncingBalls
Method:: expectedBounces
Parameters:: int[], int
Returns:: double
Method signature:: double expectedBounces(int[] x, int T)
(be sure your method is public)

Notes

There is no friction. Each ball continues rolling at the same speed forever.
Your return value must have an absolute or relative error less than 1e-9.

Constraints

x will contain between 1 and 12 elements, inclusive.
Each element of x will be between 0 and 100,000,000, inclusive.
All elements of x will be distinct.
T will be between 1 and 100,000,000, inclusive.

Examples

```
{5, 8}
```
```
2
```
```
Returns: 0.25
```
If he rolls the left ball to the right and right ball to the left, they collide at time 1.5. Otherwise, they don't collide.
```
{5, 8}
```
```
1
```
```
Returns: 0.0
```
x is the same as in example 0, but T is too small.

{91, 857, 692, 54, 8679, 83, 792, 86, 9537, 913, 64, 592}

Returns: 11.5

```
{75432}
```
```
386
```
```
Returns: 0.0
```

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

Returns: 12.75

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.