← 返回题目列表

AtCoder · code_thanks_festival_14_quala_g

G. 通勤列车和心情

中文机器翻译题面 查看原题

問題文

我是通勤电车的专家。今天也正站在车站月台上等电车。等的电车从这个车站发车,所以所有座位都是空的,但因为在我前面有 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