Fair Lottery

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

There is a lottery going to happen among $N$ groups of people. Group $i$ consists of $a_i$ persons. In the end, at most $M$ persons will be the winner of this lottery.
There is one extra restriction for this lottery: for each group, either all or none of the person in this group
are winners. In other words, no partial winners allowed for each group.
A lottery program is defined as a set of outcomes. The outcome announces the winners of the lottery. Each outcome has it’s own probability to happen, and the sum of probabilities among all outcomes equals to 1.0.
A fair lottery program is a lottery program that makes each person having the same probability $p$ of winning the lottery. Find the maximum probability $p$ over all fair lottery programs.
For example, suppose there are 3 groups: $A$, $B$, and $C$, each consists of 1, 2, and 2 persons. At most 3 persons will be the winner of the lottery.
One possible fair lottery program is: it consists of only one outcome that no one wins. So each person has the same probability of 0% winning the lottery.
A better fair lottery program is: there are two outcomes, each happening with probability of 50%. Outcome 1 announces person in group A and B as winners; and outcome 2 announces person in group C as winners.
Hence each person having the winning probability of 50%. It’s easy to verify that 50% is the maximum probability over all lottery programs.

Input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case contains 2 lines, the first line consists of 2 numbers $N$, $M$ indicating the number of groups and the max number of lottery winners.
The second line consists of $N$ numbers $a_1, a_2, . . . , a_N$ indicating the number of persons in each group.
$1 \leq T \leq 100$
$1 \leq N \leq 10$
$1 \leq M \leq 100$
$1 \leq a_i \leq 100$

Output

For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the maximum probability $p$ for each one to be the winner over all fair lottery programs. $y$ will be considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer.

Sample Input

2 3 3 1 2 2 4 2 1 1 1 2

Sample Output

Case #1: 0.5000000000 Case #2: 0.4000000000
Hint
The first test case is the sample in the problem. In the second test case, the best lottery program is: Assume groups are A(1), B(1), C(1), D(2), For [0, 0.2) persons in A, B are the winners. For [0.2, 0.4) persons in B, C are the winners. For [0.4, 0.6) persons in A, C are the winners. For [0.6, 1) persons in D are the winners.

Hint

liuyiding

Source

2017中国大学生程序设计竞赛-总决赛-重现赛(感谢哈工大)

提交代码