Connection Status:
Competition Arena > TripleJump

TripleJump

SRM 417 · 2008-09-10 · by Pawa

SRM 417 · 2008-09-10 · by Pawa · Math
Class Name: TripleJump
Return Type: double[]
Method Name: getProbabilities
Arg Types: (int, int, int, vector<int>)
Problem Statement

Problem Statement

The triple jump works as follows. The athlete runs down a runway until he reaches a designated mark. He then makes three consecutive jumps and lands in a sand-filled box. The length of the triple jump is the sum of the lengths of the three consecutive jumps. The winner of the competition is the athlete with the longest triple jump.


You are taking part in the competition and jumping after all your opponents. Since you are the last to jump, you already know all your opponents' results. They are given in the int[] opponents, where opponents[i] is the length of the i-th opponent's triple jump in centimeters.


You have already made the first of your three jumps, and it was first centimeters long. You ask yourself a question: "What is the probability that I will take first place? Second place? And all the other places?". You know that each of your two remaining jumps will be between lower and upper centimeters, inclusive, in length. The lengths will not necessarily be integers, and all possible lengths between lower and upper will be equally likely. Return a double[] containing exactly N + 1 elements (N is the number of opponents you have) such that the i-th element (0-indexed) is the probability of you taking (i+1)-th place. Note that your place number is equal to one plus the number of opponents who had longer triple jumps than you.

Notes

  • Each element of your return value must have an absolute or relative error less than 1e-9.

Constraints

  • lower will be between 1 and 1000, inclusive.
  • upper will be between lower and 1000, inclusive.
  • first will be between lower and upper, inclusive.
  • opponents will contain between 1 and 50 elements, inclusive.
  • Each element of opponents will be between 1 and 3000, inclusive.
Examples
0)
1
2
1
{1,2,3,4}
Returns: {0.5, 0.5, 0.0, 0.0, 0.0 }

Your first jump has length 1, and the two subsequent jumps - any lengths between 1 and 2. So your triple jump will have a total length between 3 and 5. This guarantees you at least the second place with an equal chance of getting the first one.

1)
10
10
10
{1000}
Returns: {0.0, 1.0 }
2)
1
1000
666
{1000,2000,3000,2000,500,100,700,666,667,668,669}
Returns: {0.0, 0.22222222222222227, 0.0, 0.7225553882210538, 0.05470936401867332, 5.125245365485975E-4, 5.010015019513148E-7, 0.0, 0.0, 0.0, 0.0, 0.0 }
3)
3
7
5
{9,9,19,19,19}
Returns: {0.0, 0.0, 0.0, 1.0, 0.0, 0.0 }

Now the length of your triple jump will be between 11 and 19, and thus you are inevitably fourth. Note that the probability to have a triple jump with length exactly 19 in this case is zero.

4)
1
10
1
{5}
Returns: {0.9753086419753086, 0.024691358024691357 }

Submissions are judged against all 91 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TripleJump with a public method vector<double> getProbabilities(int lower, int upper, int first, vector<int> opponents) · 91 test cases · 2 s / 256 MB per case

Submitting as anonymous