题目描述

There are $N$ contestants in a reality TV show. Each contestant is assigned a point value by the judges and receives votes from the audience. The point value given by the judges and the audience's votes are combined to form a final score for the contestant, in the following way:

Let $x$ be the sum of the judge-assigned point values of all contestants. Now suppose a contestant got $j$ points from the judges, and that she received a fraction $y$ (between 0 and 1, inclusive) of the audience's votes ($y$ might be, for example, 0.3). Then that contestant's final score is $j + x \cdot y$. Note that the sum of all contestants' audience vote fractions must be 1.

The contestant with the lowest score is eliminated.

Given the points contestants got from judges, your job is to find out, for each contestant, the minimum percentage of audience votes he/she must receive in order for him/her to be guaranteed not to be eliminated, no matter how the rest of the audience's votes are distributed.

If the lowest score is shared by multiple contestants, no contestants will be eliminated.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow, one per line. Each line starts with an integer $N$, the number of contestants, followed by a space, followed by $N$ integers $s_0, s_1, ..., s_{N-1}$, separated by single spaces. The integer $s_i$ is the point value assigned to contestant $i$ by the judges.

输出格式

For each test case, output one line containing "Case #x: " followed by $N$ real numbers: $m_i$s. The value $x$ is the case number (starting from 1). The value $m_i$ is the smallest percentage of audience votes required for contestant $i$ to definitely avoid elimination.

Answers within an absolute or relative error of $10^{-5}$ of the correct answer will be accepted.

4
2 20 10
2 10 0
4 25 25 25 25
3 24 30 21

Case #1: 33.333333 66.666667
Case #2: 0.000000 100.000000
Case #3: 25.0 25.0 25.0 25.0
Case #4: 34.666667 26.666667 38.666667

提示

Limits

• $0 \leq s_i \leq 100$.
• $s_i > 0$ for some $i$. This means at least one contestant will have a point value greater than $0$.

Test set 1 (10 Pts, Visible Verdict)

• $1 \leq T \leq 20$.
• $2 \leq N \leq 10$.

Test set 2 (11 Pts, Hidden Verdict)

• $1 \leq T \leq 50$.
• $2 \leq N \leq 200$.