Your local grocery store has started an innovative promotion: for every purchase, they give you a random emoji sticker. The person who collects the most distinct types of emojis wins free shopping for a year (excluding alcohol and gift cards). To keep the competition interesting, they decided not to disclose the total number of distinct emojis.
Your friend already has a sizable collection thanks to their love for pizza. To assess their chances, you would like to help them estimate how many different emojis are there to collect.
The store uses d types of emoji. The type of each emoji given to a buyer is selected uniformly at random from the set of all emoji types – i.e., each type is selected with probability 1/d. All these random choices are mutually independent. The store has an unlimited supply of emojis of each type.
You know that before the promotion the store selected the value d at random, as described below.
You are given the multiset of emojis in your friend’s collection. You are also given a closed interval [a, b]. Compute and return the probability that the actual value of d lies in the given interval.
The distribution of d differs in the easy and hard subproblem.
The first line of the input file contains an integer t ≤ 100 specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of two lines. The first line contains four space-separated integers n, a, b, m with the following meaning:
The second line of each test case consists of n integers x1, …, xn: the number of collected emojis of each type.
Note that the emojis don’t have any serial numbers, so you should not interpret x1 as “the number of emojis of type 1”. The order of the xi does not matter. For example, if the second line of a test case is “1 1 2 1”, the whole information it contains is that your friend currently has 5 emojis: a pair of identical ones and three unique ones.
In the easy subproblem C1 we have 1 ≤ n ≤ 20, n ≤ m, and 1 ≤ a ≤ b ≤ m ≤ 104. All xi are positive and their sum does not exceed 40.
In the hard subproblem C2 we have 1 ≤ n ≤ 40, 1 ≤ a ≤ b ≤ 1018, and b − a ≤ 20 000. The value of m is always 0, indicating that there is no upper bound on the number of emoji types. All xi are positive and their sum does not exceed 120.
For each test case, output a single line with a floating-point number p: the probability of d being in the closed interval [a, b], given the known distribution of d and your observations.
Make sure that for non-zero p your output contains at least seven (preferably more) most significant decimal digits of p. Your p will be considered correct if it is within the interval [0, 1] and its relative error is at most 10−6.
The value of p may be printed in scientific notation (“1.2345678E-90”).
Note that (as opposed to many other problems that involve floating-point numbers) we are not looking at the absolute error of your answer.
Input:
5
1 1 1 2
2
10 10 100 10000
1 1 1 1 1 1 1 1 1 1
5 1 4 10000
4 6 5 2 1
15 150 5000 10000
1 1 2 2 1 1 1 2 2 1 3 1 1 1 1
5 10 200 0
1 2 2 1 3Output:
0.6666666666667
0.0034745158491
0.0000000000000
0.0027270798056
0.1182410425858The first four sample test cases (with positive values of m) can only appear in the easy subproblem. The last sample test case (with m = 0) can only appear in the hard subproblem.
In the first sample test case you know that the store flipped a fair coin to decide whether the number of emoji types is 1 or 2. Your friend has two emojis and both happen to be of the same type. While it is still possible that there is a second type, it is more likely that this collectors’ game is a bit boring – every emoji is the same.
In the second example you know that the actual number of emoji types was chosen from the range 1-10000. You are asked what is the probability that there are between 10 and 100 kinds of emojis, given that your friend has collected ten emojis so far and every one of them turned out to be distinct. Receiving ten distinct emojis is not so likely if the total number of emoji types is small, so you conclude that the probability of d being in the given interval is quite low.
In the third case you have already observed five different types of emoji. Thus, you can be absolutely certain that d does not lie in the interval [1,4].