Game of Chance

题意翻译

国王想要嫁某一个女儿，并且她希望女儿的丈夫天生就是最幸运的。为了找到这样的人，他决定举办一次猜硬币正反面比赛。 如果一个人 $A$ 的幸运值为 $x$，另一个人 $B$ 的幸运值为 $y$，那么 $A$ 获胜的概率为 $\dfrac{x}{x+y}$。 比赛有几轮。每轮一些参与者被分为一些对。每对参与者互相比拼，输者被淘汰出这个比赛。 玩家从 $1$ 到 $n$ 编号。第一轮，一个数 $k\ (1\le k\le n)$ 被选出，并满足 $n-\dfrac{k}{2}$ 是 $2$ 的幂（这样的 $k$ 总是存在的并且是唯一的）。只有编号从 $1$ 到 $k$ 的参与者进行第一轮比赛。这保证了其他轮比赛中参与者数总是 $2$ 的幂次。 在其他轮次中，所有没被淘汰的参与者都要参加。如果在某轮比赛中，参与者 $p_1<\ldots<p_{2m}$ 参加了，那么他们按如下方式分组：对于所有 $i$ 从 $1$ 到 $m$，参与者 $p_{2i-1}$ 和 $p_{2i}$ 进行比赛。 比赛举行到只有一个参与者时停止。他就成为了这次比赛的冠军，并且将迎娶国王的女儿。公主已经迫不及待地想知道谁是她未来的丈夫了。她向所有参与者询问了他们的幸运值。假设他们不会说谎，她想知道每个参与者赢得比赛的概率。你作为公主最好的朋友，她要求你帮帮她。 输入的第一行包含一个整数 $n\ (2\le n\le 3\cdot 10^5)$ 表示参与者总数。第二行包含 $n$ 个整数 $a_1,\ldots ,a_n\ (1\le a_i\le 10^9)$。第 $i$ 个参与者的幸运值等于 $a_i$。 输出 $n$ 个数 $p_i$。第 $i$ 个数表示第 $i$ 个参与者获胜的概率。你的答案与标准答案的绝对误差不能超过 $10^{-9}$。 这里是一次比赛的结果的例子，展示了每对参与者获胜的概率。

题目描述

The King wants to marry off his daughter, and he wants her husband to have the greatest innate luckiness possible. To find such a person he decided to hold a heads-or-tails tournament. If person $ A $ with luckiness $ x $ and person $ B $ with luckiness $ y $ play heads-or-tails against each other, person $ A $ wins with probability $ x/(x+y) $ . The tournament has several rounds. Each round some participants are split into pairs. Each pair plays against each other, and the loser leaves the tournament. The participants are numbered from $ 1 $ to $ n $ . During the first round, a number $ k $ ( $ 1 \le k \le n $ ) is selected such that $ n-k/2 $ is a power of $ 2 $ (such $ k $ always exists and is unique). Only participants numbered from $ 1 $ to $ k $ take part in the first round. It ensures that in all other rounds the number of participants is the power of $ 2 $ . During other rounds, all the participants who still have not left the tournament take part. If during some round, participants numbered $ p_1 < \ldots < p_{2m} $ take part, then they are split into pairs in the following manner: participant $ p_{2i-1} $ plays against participant $ p_{2i} $ for each $ i $ from $ 1 $ to $ m $ . The rounds are held until only one participant is left. He is declared the winner of the tournament and he will marry the King's daughter. The princess can't wait to find out who is her future husband. She asked every participant to tell her his luckiness. Assuming they did not lie, she wants to know the probability of each participant winning the tournament. As you are the best friend of the princess, she asks you to help her.

输入输出格式

输入格式

The first line of the input contains the number of participants, $ n $ ( $ 2 \le n \le 3 \cdot 10^5 $ ). The second line of the input contains $ n $ integer numbers, $ a_1, \ldots, a_{n} $ ( $ 1 \le a_i \le 10^9 $ ). The luckiness of the $ i $ -th participant equals to $ a_i $ .

输出格式

Print $ n $ numbers $ p_i $ . The $ i $ -th number should be the probability of the $ i $ -th participant winning the tournament. The absolute error of your answer must not exceed $ 10^{-9} $ .

输入输出样例

输入样例 #1

5
1 4 1 1 4

输出样例 #1

0.026 0.3584 0.0676 0.0616 0.4864

说明

Here is an example of a tournament bracket, showing the winning probability in each pair.