水母面前有$$$n$$$个怪物,编号从$$$1$$$到$$$n$$$。第$$$i$$$个怪物的HP为$$$h_i$$$。
水母不想杀死它们,但她想让这些怪物不再对她构成威胁。所以她想把所有怪物的生命值减少到$$$1$$$。
现在,水母带着泪磨剑,将攻击怪物$$$m$$$轮。每轮:
- 含泪磨剑的概率为$$$p$$$。
- 水母可以选择是否攻击:
- 如果水母不攻击,则不会发生任何事情。
- 如果水母选择攻击且泪磨剑发光,所有怪物的生命值将减少$$$1$$$。
- 如果水母选择攻击且泪磨剑没有发光,水母可以选择其中一只怪物并使其生命值减少$$$1$$$。
请注意,水母决定是否攻击之前,她会知道剑是否发光。而且,当剑发光时,水母只能攻击所有怪物,而不能只攻击一只怪物。
现在,水母想知道如果她在战斗中做出最佳选择,她实现目标的概率是多少。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$p'$$$ ($$$1 \leq n \leq 20$$$, $$$1 \leq m \leq 4000$$$, $$$0 \leq p' \leq 100$$$) — 怪物数量,怪物数量攻击轮数,以及代表泪磨剑发光的概率 $$$p = \frac {p'} {100}$$$ 的整数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1,h_2,\ldots,h_n$$$ ($$$1 \leq h_i \leq 400$$$) — 怪物的生命值。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$100$$$。
输出
对于每个测试用例,输出一个代表 Gellyfish 达到目标的概率的实数。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入复制
42 2 102 25 5 202 2 2 2 26 20 501 1 4 5 1 49 50 339 9 8 2 4 4 3 5 3
输出复制
0.910000 0.672320 0.588099 0.931474
注意
在第一个测试用例中,无论第一轮剑是否发光,水母都会攻击。
如果第一回合剑发光,那么水母在第一回合攻击后就能达到目标。
否则,如果第一轮剑没有发光,她将在第一轮攻击怪物$$$1$$$。对于第二轮:
- 如果剑发光,由于怪物$$$1$$$在第一轮被攻击,水母无法到达目标。
- 否则,水母可以攻击怪物$$$2$$$,让她达到目标。
因此,水母达到目标的概率为$$$10\% + (90\% \cdot 90\%) = 91\%$$$。
在第二个测试用例中,水母只会在剑光闪耀的第一回合中进行攻击。可以看出,水母无法达到目标的唯一方法是剑在所有 $$$5$$$ 回合中都不会发光。水母达到目标的概率为 $$$100\% - (80\%)^5 = 67.232\%$$$。