Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21758. 【PR #9】比赛

统计

题目描述

有 $n$ 个人参加一场比赛,小多是其中之一。这里,$n$ 一定是 2 的正整数次幂。

参加比赛的 $n$ 个人排成一队,从左到右分别编号为 $1,2,\dots,n$。第 $i$ 个人有自己的能力值 $a_i$。能力值为 $x$ 的人和能力值为 $y$ 的人决斗,胜者为前者的概率是 $x/(x+y)$,为后者的概率是 $y/(x+y)$。

比赛的过程如下:

  • 若现在只剩下一个人,这个人就是最终赢家。
  • 否则,让现在队列里排在最左边的两个人,不妨设为 A 和 B,进行决斗。A 和 B 中的败者离开比赛,胜者回到队列的最右边。

现在,小多已经摸清了所有人的能力值(包括自己),也知道了除了自己以外其它人在队列中的顺序,但他不知道自己在队列中的位置。把自己插进剩下 $n-1$ 个人的队列中,共有 $n$ 种可能。对于每种可能,请你求出小多成为最终赢家的概率。

输入格式

第一行两个正整数 $n,x$,分别为人数和小多的能力值。

第二行 $n-1$ 个正整数 $a_1\sim a_{n-1}$,从左到右地描述队列中除了小多外的选手的能力值。

输出格式

输出 $n$ 个实数,第 $i$ 个表示:如果把小多插在队列第 $i-1$ 个人和第 $i$ 个人之间($i=1$ 时插在第一个人前面,$i=n$ 时插在第 $n-1$ 个人后面),小多的胜率是多少。

只要你的输出与标准答案的绝对误差在 $10^{-9}$ 以内就算对。

样例

样例输入 1

4 2
1 1 1

样例输出 1

0.444444444444
0.444444444444
0.444444444444
0.444444444444

样例 1 解释

无论小多在哪个位置,要赢得比赛,他都需要连胜两局,而这两局中对手的能力值为 1,他的能力值为 2,胜率为 $2/3$,故最终胜率为 $(2/3)^2=4/9$。

样例输入 2

8 4
1 2 3 4 5 6 7

样例输出 2

0.202724628508
0.202724628508
0.168937190423
0.168937190423
0.098444548984
0.098444548984
0.088968603093
0.088968603093

数据范围

本题共 10 个测试点,每个测试点 10 分。所有数据满足 $2\le n\le 4096$,$1\le x,a_i\le 10^4$,存在正整数 $k$ 使得 $n=2^k$。

  • 测试点 1,2 满足 $a_i$ 全部相同。
  • 测试点 3 满足 $n=4$。
  • 测试点 4 满足 $n=8$。
  • 测试点 5 满足 $n=32$。
  • 测试点 6 满足 $n=256$。
  • 测试点 7,8,9,10 无特殊性质。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$