取球
题目描述
你有一个袋子，里面有 $n$ 个球，球有红球和黑球两种。袋子里面恰好有 $k$ 个红球的概率为 $p_i$，你需要开始从袋子里面取球。
每次你可以花费 $c(0\leq c\leq 1)$ 的代价取出一个球，如果取出的是红球你将获得 $1$ 的价值，否则你什么都得不到。
求最大的期望收益。
输入格式
从文件 ball.in 中读取数据。
第一行两个整数 $n,s$，$c=\dfrac{s}{10^6}$。
第二行 $n$ 个整数 $a_1,a_2\dots,a_n$，$p_i=\dfrac{a_i}{10^6}$。
输出格式
输出到文件 ball.out 中。
一行一个实数，表示最大收益。
你的答案和正确答案的相对误差不超过 $10^{-9}$ 时将被判为正确。
具体来说，设 $a$ 表示你的答案，$b$ 表示正确答案，则 $\dfrac{|a-b|}{\max(1,b)}\leq 10^{-9}$ 时你将获得该测试点的分数。
样例输入 #1
3 200000
250000 250000 250000 250000样例输出 #1
0.9000000000样例 #2
见选手目录下的 ball/ball2.in 与 ball/ball2.ans。
该样例满足测试点 2 的限制。
样例 #3
见选手目录下的 ball/ball3.in 与 ball/ball5.ans。
该样例满足测试点 7 的限制。
样例 #4
见选手目录下的 ball/ball4.in 与 ball/ball5.ans。
该样例满足测试点 9 的限制。
样例 #5
见选手目录下的 ball/ball5.in 与 ball/ball5.ans。
该样例满足测试点 10 的限制。
样例 #6
见选手目录下的 ball/ball5.in 与 ball/ball5.ans。
该样例满足测试点 17 的限制。
样例 #7
见选手目录下的 ball/ball5.in 与 ball/ball5.ans。
该样例满足测试点 20 的限制。
数据范围
| 测试点编号 | $n\leq$ | 特殊性质 |
|---|---|---|
| 1 | $5$ | / |
| 2 | $10$ | / |
| 3 | $15$ | / |
| 4 | $20$ | A |
| 5 | $20$ | B |
| 6 | $50$ | / |
| 7 | $100$ | / |
| 8 | $100$ | / |
| 9 | $10^3$ | A |
| 10 | $10^3$ | B |
| 11 | $10^3$ | / |
| 12 | $10^3$ | / |
| 13 | $10^4$ | A |
| 14 | $10^4$ | A |
| 15 | $10^4$ | B |
| 16 | $10^4$ | B |
| 17 | $10^4$ | C |
| 18 | $10^4$ | / |
| 19 | $10^4$ | / |
| 20 | $10^4$ | / |
特殊性质 A：$\sum_{i=1}^n [a_i>0]=1$。
特殊性质 B：$\sum_{i=1}^n [a_i>0]\leq 2$。
特殊性质 C：$s=0,a_n=10^6$。
对于 $100\%$ 的数据，$1\leq n\leq 10^4,0\leq s,a_i\leq 10^6,\sum_{i=1}^n a_i= 10^6$。