問題文
我是通勤电车的专家。今天也正站在车站月台上等电车。等的电车从这个车站发车,所以所有座位都是空的,但因为在我前面有 N 人排队,所以能否坐到座位还不确定。
车厢里有 K 个座位排成一排,每个座位从 1 到 K 的连续整数编号。可能有人会认为,只要知道座位数和自己前面排队的年轻人数,就可以知道能否坐到座位,但事情并不是那么简单。
我知道,人们根据当天的心情选择座位的方式会有所不同。具体来说,某天的心情有以下 2 种情况。
- “无论如何都想坐的心情” :这种心情的人,如果还有空座,会坐在编号最小的空座上。
- “如果有余地就想坐下的心情” :这种心情的人,如果在空座里有邻座也空着的座位,会选择编号最小的那一座。邻座不存在的情况下,也可以视为邻座空着。
无论哪种心情,如果没有符合条件的座位,就会放弃坐下。
现在,我打算给排在我前面的人依次编号为人 1, 人 2, ……, 人 N 。也就是说,首先人 1 上车,并根据当天的心情选择座位。接着人 2 上车,也根据当天的心情选择座位。这样重复,直到人 N 上车并选择完座位后,轮到我上车。
在我看来,人 i 是 p_i 以百分之__的正确率会产生“无论如何都想坐下”的心情,100 - p_i 以百分之__的正确率会产生“有机会就想坐下”的心情。在这个假设下,当第__个人 N 进入车厢并选择好座位时,也就是说,当我进入车厢时空着的座位的期望数量是多少,希望进行计算。
入力
N K p_1 p_2 : p_N
- 1 行列中排列的××用整数表示 N (1 ≦ N ≦ 100) ,车厢中座位的数量用整数表示 K (1 ≦ K ≦ 200) 。
- 2 从行 N 每行提供每个人的情报。其中 i 行表示,第几个人 i 表示该人“总之想坐下”的正确率的整数 p_i (0 ≦ p_i ≦ 100) 。
部分点
这个问题设置了部分得分。
- N ≦ 10 如果满足条件的数据集全部答对 30 分可以获得。
- 如果对所有数据集都答对,除了上面之外还能获得 70 分,总共 100 分可以获得。
出力
人 N 表示车辆中人坐好座位时,空座的期望数量的实数 1 行输出。如果与真实值的绝对误差或相对误差 10^{-6} 以下,则视为正确答案。
入力例1
3 4 100 30 60
出力例1
1.28
人 1 总是“无论如何都想坐”,所以考虑人的 2, 3 情绪时
- 人 2, 3 双方都“无论如何都想坐”的正确率为 0.3 \times 0.6 = 0.18 ,空座为 1 个。
- 人 2 是“无论如何都想坐”,但dwango公司的nisan君 3 是您在有时间的情况下想坐下来的概率。 0.3 \times 0.4 = 0.12 ,空座为 1 个。
- 人 2 “如果有空间的话我想坐下来”,但是人们 3 “只是想坐下来”的概率是 如果有时间, 0.7 \times 0.6 = 0.42 ,空座为 1 个。
- 人 2, 3 都想坐下来的概率是 0.7 \times 0.4 = 0.28 ,空座为 2 个。
因此,空缺席位数的期望值为 1 \times 0.18 + 1 \times 0.12 + 1 \times 0.42 + 2 \times 0.28 = 1.28 。
入力例2
5 7 28 31 59 61 30
出力例2
2.11193
入力例3
10 10 97 98 99 98 97 96 97 98 99 98
出力例3
0.020237732