#P18621. Testing Subjects Usually Die

Testing Subjects Usually Die

Testing Subjects Usually Die

“你好,再次欢迎来到光圈科技拓展中心。”

你在一个陌生的房间里醒来,一个机械声音向你打招呼。你正在参与一系列不太符合伦理的实验。

本次实验中,人工智能从 11 到 nn 中选取一个整数。它选择整数 kk 的概率为

pkp1+⋯+pn.\frac{p_k}{p_1+\cdots+p_n}.

你需要猜出这个整数。如果猜错,你会再次被催眠,记忆被清除,然后重新接受同一个实验。此时,以 c%c\% 的概率,人工智能会按照上述分布重新选取一个整数;以 (100−c)%(100-c)\% 的概率,选中的整数保持不变。

你不知道自己已经参加过多少次实验,也不知道此前猜过哪些数。因此,你将选择一个固定的概率分布 q1,…,qnq_1,\ldots,q_n,并在每次猜测时以概率 qkq_k 回答整数 kk。

你希望尽早完成实验。求在最优选择该分布时,直到猜对为止所需猜测次数的最小期望。猜对的那一次也计入猜测次数。

概率分布要求 qk≥0q_k\ge0,且 q1+⋯+qn=1q_1+\cdots+q_n=1。允许某些 qk=0q_k=0。

输入格式

第一行包含两个整数 n,cn,c,其中 2≤n≤1052\le n\le10^5,0≤c≤1000\le c\le100。cc 是以百分数表示的整数。

第二行包含 nn 个整数 p1,…,pnp_1,\ldots,p_n,其中 1≤pi≤1031\le p_i\le10^3。

输入只有一组数据。

输出格式

输出一个浮点数,表示所求的最小期望猜测次数。

如果答案的绝对误差或相对误差不超过 10−610^{-6},则认为正确。等价地,设标准答案为 bb、提交答案为 aa,要求

∣a−b∣≤10−6max⁡(1,∣b∣).|a-b|\le10^{-6}\max(1,|b|).

样例输入 1

4 100
25 25 25 25

样例输出 1

4

样例输入 2

2 0
1 4

样例输出 2

1.800000000