DrawingMarbles
SRM 370 · 2007-10-09 · by mateuszek
Problem Statement
Notes
- Every time we draw a marble, all marbles in the box are equally likely to be chosen.
- A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
- colors will contain between 1 and 50 elements, inclusive.
- Each element of colors will be between 1 and 50, inclusive.
- n will be between 1 and the sum of all elements of colors, inclusive.
{ 13 }
8
Returns: 1.0
All the marbles are the same color, so obviously all drawn marbles will be the same color too.
{ 5, 7 }
1
Returns: 1.0
{ 5, 6, 7 }
2
Returns: 0.3006535947712418
The probability that the first drawn marble will be of the color 0 is 5 / 18 (there are 5 marbles of color 0 out of 18). If the first drawn marble is of the color 0, then the probability that the second drawn marble will be of the color 0 is 4 / 17 (there are 4 marbles of color 0 left out of 17). So the probability that both drawn marbles will be of the color 0 is (5 / 18) * (4 / 17) = 0.0653594771... . Similarly, the probability that both drawn marbles will be of the color 1 is (6 / 18) * (5 / 17) = 0.0980392156..., and that both drawn marbles will be of the color 2 is (7 / 18) * (6 / 17) = 0.1372549019... . The answer is the sum of these 3 probabilities.
{ 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }
500
Returns: 0.0
{ 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }
10
Returns: 4.178940467970992E-10
Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DrawingMarbles with a public method double sameColor(vector<int> colors, int n) · 94 test cases · 2 s / 256 MB per case