Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4038
Boring Game

Time Limit: 3 Seconds      Memory Limit: 262144 KB      Special Judge

There are $n$ players (numbered from 1 to $n$) playing PUBG (PlayerUnknown's Battlegrounds). The $i$-th player has an accuracy of $a_i$, which indicates the probability that he hits the target if he gives a shoot. As they are bored, they come up with an even more boring playing rule which is as follows:

  • In each round, the players shoot one by one in the order of player 1, player 2, ..., player $n$. Each player can shoot at most once in each round.

  • If one gets shot, he loses and quits the game immediately.

  • The game will continue until there is only one survivor, otherwise a new round begins.

By coincidence, every two people have different shooting accuracys. If you are smart enough, you may choose not to shoot anyone in some occasions. But these $n$ players are just simple-minded. If it's their turn, they are certain to shoot the person with the highest accuracy who still remains in the game (and the one with the highest accuracy will shoot the person with the second highest accuracy who still remains in the game).

It's your task to calculate the winning probability of each player.


There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 200$), indicating the number of players.

The second line contains $n$ numbers $a_1, a_2, \dots, a_n$ ($0 < a_i < 1$), indicating the shooting accuracy of each player.

The distribution of $n$ in the test cases are listed as follows:

range of n number of cases
(0, 20] 9390
(20, 50] 500
(50, 100] 100
(100, 200] 10


For each test case, output $n$ integers in one line, where the $i$-th integer indicates the winning probability of the $i$-th player.

Your answer will be considered correct if its absolute error or relative error is not larger than $10^{-6}$

Sample Input

0.4 0.6
0.4 0.5 0.6

Sample Output

0.526315789 0.473684211
0.432330827 0.470779221 0.096889952


In the first sample test case, the first person wins with possibility 0.4 at each round.

The game processes to round $k$ with probability $(0.6 \times 0.4) ^ {k - 1}$.

So possiblity to win for the first person is $0.4 + 0.4 \times 0.6 \times 0.4 + \dots \approx 0.526315789$

Author: ZHANG, Yuan
Source: ZOJ Monthly, June 2018
Submit    Status