ExpectedMinimumPowerDiv2
SRM 730 · 2018-02-19 · by lg5293
Problem Statement
You are given two positive
You are going to choose x distinct integers, each between 1 and n, inclusive. The choice will be made uniformly at random. That is, each of the possible x-element subsets of the integers 1 to n is equally likely to be chosen.
Let S be the smallest integer among the x chosen ones. Compute and return the expected value of 2^S. In other words, determine the average value of 2 to the power of S, where the average is taken over all possible choices of the x distinct integers.
Notes
- Your answer will be accepted if the absolute or relative error is at most 1e-9.
Constraints
- n will be between 1 and 50, inclusive.
- x will be between 1 and n, inclusive.
4 4 Returns: 2.0
The only possible situation is that you will choose (1, 2, 3, 4). In this case, the minimum is 1, and the expected value is 2^1 = 2.
3 2 Returns: 2.6666666666666665
There are three equally likely scenarios: you will select either {1,2} or {1,3} or {2,3}. The corresponding values of S are 1, 1, and 2, respectively. Thus, the average value of 2^S is (2^1 + 2^1 + 2^2) / 3 = 8 / 3 = 2.6666666
3 1 Returns: 4.666666666666667
10 4 Returns: 8.076190476190476
50 25 Returns: 9.906688596554163
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ExpectedMinimumPowerDiv2 with a public method double findExp(int n, int x) · 57 test cases · 2 s / 256 MB per case