BouncingBalls
Member SRM 458 · 2009-12-03 · by rng_58
Member SRM 458 · 2009-12-03 · by rng_58 · Math
Problem Statement
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 givenint[] 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).
You are given
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
0)
{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.
1)
{5, 8}
1
Returns: 0.0
x is the same as in example 0, but T is too small.
2)
{87, 356, 42, 865, 82, 482, 676}
200
Returns: 3.25
3)
{91, 857, 692, 54, 8679, 83, 792, 86, 9537, 913, 64, 592}
458
Returns: 11.5
4)
{75432}
386
Returns: 0.0
Submissions are judged against all 47 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BouncingBalls with a public method double expectedBounces(vector<int> x, int T) · 47 test cases · 2 s / 256 MB per case