Algorithm

 Problem Statement for BouncingBalls

Problem link- https://community.topcoder.com/stat?c=problem_statement&pm=10726&rd=14180&rm=&cr=14970299

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
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)  
     
{91, 857, 692, 54, 8679, 83, 792, 86, 9537, 913, 64, 592}
 
458
 
Returns: 11.5
 
3)  
     
{75432}
 
386
 
Returns: 0.0
 
4)  
     
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
 
3
 
Returns: 12.75

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

class BouncingBalls {
public:
  double expectedBounces(vector<int> x, int T) {
    sort(x.begin(), x.end());

    double res = 0;
    for(int i = 0; i < x.size(); ++i)
      for(int j = i + 1; j < x.size(); ++j)
        if(abs(x[i] - x[j]) <= 2 * T)
          res += 0.25;

    return res;
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
{5, 8}
2

Output

x
–
+
cmd
0.25
Advertisements

Demonstration

TopCoder Solution SRM458-D2-500 Statement for BouncingBalls C,C++, Java, Js and Python ,SRM458-D2-500,TopCoder Solution