2004. cats 的随机化做题策略

时间限制 1000 ms   内存限制 256 MB

cats 正在参加一场有 $n$ 道题的算法竞赛,因为 cats 非常喜欢随机化算法,所以 cats 在每一道题中都使用了随机化。

然而,随机化算法不一定能保证 $100\%$ 通过题目,cats 第 $i$ 道题提交一次只有 $p_i\%$ 的概率获得Accepted。如果一次提交没有获得Accepted,cats 将获得 $20$ 分钟的额外罚时。

因为 cats 非常喜欢随机,所以 cats 每次会随机在所有没有获得Accepted的题中等可能的选择一道题进行提交,直到所有题都获得Accepted

你能帮 cats 算算他在完成所有题目后获得的额外罚时的期望值是多少吗?

输入数据

第一行为一个整数 $n$。表示题目的总数。$1\le n\le 10^5$

第二行为 $n$ 个整数 $p_1,p_2,\dots ,p_n$。表示第 $i$ 道题提交一次cats获得Accepted的概率的百分比。$1\le p_i\le 100$

输出数据

输出共一行,第一行输出一个实数 $x$ ,表示 cats 获得额外罚时的期望值,绝对误差或相对误差小于 $10^{-6}$ 视为正确。

注:如果你输出的答案为 $x$ ,标准答案为 $y$ ,那么当且仅当 $\frac{|x-y|}{max(1,|y|)}\le 10^{-6}$ 时,答案视为正确。

样例输入

复制
2
100 50 \n
   ·  \n

样例输出 special judge

复制
20.000000         \n

样例说明

无论 cats 何时提交第一道题,他都能一次获得Accepted,所以第一道题不会产生额外罚时。cats 平均提交 $2$ 次才能通过第二道题,产生 $20$ 分钟的罚时。

提交

请先 登录

© 2024 FAQs Contact About