Statistics

Problem Statement for "BouncingBalls"

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

  1. {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.

  2. {5, 8}

    1

    Returns: 0.0

    x is the same as in example 0, but T is too small.

  3. {87, 356, 42, 865, 82, 482, 676}

    200

    Returns: 3.25

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

    458

    Returns: 11.5

  5. {75432}

    386

    Returns: 0.0

  6. {81765919}

    74927847

    Returns: 0.0

  7. {91391518}

    8678366

    Returns: 0.0

  8. {45349748,44887243}

    1802272

    Returns: 0.25

  9. {80268343,89772825}

    4169015

    Returns: 0.0

  10. {49118311,79932150,20137364}

    13972261

    Returns: 0.0

  11. {96032857,77206973,68706223}

    46406355

    Returns: 0.75

  12. {92516171,26542610,28126542,1950414}

    49164332

    Returns: 1.5

  13. {59998478,80937351,25914703,81643285}

    28983968

    Returns: 1.5

  14. {56224172,18458117,83059335,10500656,70970480}

    9137855

    Returns: 0.75

  15. {63674747,4629740,47965600,93687325,15934104}

    18477289

    Returns: 1.0

  16. {51656710,36430313,83337399,14127113,82875682,43654031}

    13380804

    Returns: 1.25

  17. {5099291,53580334,35222225,17442741,88580989,7426501}

    10691471

    Returns: 1.25

  18. {52299416,39228182,82095952,31636655,23840040,11081999,87487094}

    7596

    Returns: 0.0

  19. {30103618,1013189,61784834,76460916,5748438,86000794,61170557}

    6672899

    Returns: 0.75

  20. {99304824,59931119,53962267,68295553,6364913,11243527,94411731,41418519}

    19703123

    Returns: 3.5

  21. {25440078,33958741,12677186,71339218,84742706,65117066,83332382,52483193}

    11460881

    Returns: 3.0

  22. {96796182,76151768,6140945,78512105,9984370,3305397,19159289,42727406,32021903}

    38430576

    Returns: 8.0

  23. {53189263,48283583,54969874,57114987,14316389,59481676,68043415,72004048,80643046}

    890829

    Returns: 0.25

  24. {82559963,20256093,3823673,41127585,99845036,85293988,16688793,98508730,558229,47030698}

    19791905

    Returns: 5.0

  25. {4255253,63821518,46953781,98427199,47176132,34901140,2183717,70386587,5284670,3224407}

    564704

    Returns: 1.0

  26. {31622996,21792716,57482152,19515391,99333059,26846005,53909171,97905445,1708865,81350648,14238776}

    17021783

    Returns: 6.5

  27. {58703724,72439826,4108454,85894557,85983573,41274446,27723012,9435094,22814898,34168418,58421357}

    19293331

    Returns: 8.75

  28. {84695038,74726696,69580809,12835713,10483393,74846502,64873464,79011686,40931190,6947919,70258288,65332131}

    46820309

    Returns: 16.5

  29. {27166037,99374289,41680381,83555933,60692725,33654394,33644384,74341720,78883766,45357074,53542738,75831903}

    34469051

    Returns: 16.25

  30. {0, 100000000}

    50000000

    Returns: 0.25

  31. {1, 100000000}

    49999999

    Returns: 0.0

  32. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

    6

    Returns: 16.5

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

    3

    Returns: 12.75

  34. {4, 50, 77, 2323 }

    1000

    Returns: 0.75

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

    458

    Returns: 11.5

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

    3

    Returns: 12.75

  37. {1, 2, 30000000, 100000000, 5, 6, 7, 8, 9, 10, 11, 12 }

    100000000

    Returns: 16.5

  38. {91, 857, 692, 54, 8679, 83, 792, 86, 9537, 592, 100000000 }

    2010

    Returns: 7.25

  39. {234, 235, 23487, 2839, 9237, 4987, 2, 928374, 98374, 345345 }

    7967293

    Returns: 11.25

  40. {1, 10, 1000, 10000, 20000, 12, 100, 10000000, 100001, 10000002, 10000004, 10000005 }

    100000000

    Returns: 16.5

  41. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

    100000000

    Returns: 16.5

  42. {432424, 5325, 6436, 23432, 342, 4234, 3422, 2333, 233, 22, 33333, 432422 }

    100000000

    Returns: 16.5

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

    100000000

    Returns: 16.5

  44. {89003176, 77514010, 72441260, 6514497, 79733773, 61035309, 37017339, 88108025, 75820271, 10647984, 26139400, 32984324 }

    100000000

    Returns: 16.5

  45. {1, 100000000, 50000000, 10000000, 20000000, 30000000, 40000000, 55000000, 8, 32432423, 324324, 99999999 }

    100000000

    Returns: 16.5

  46. {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 11, 12 }

    10000000

    Returns: 16.5

  47. {1, 2, 3, 4, 54, 6, 7, 8, 9, 10, 11 }

    500

    Returns: 13.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.
This problem was used for: