AT_code_thanks_festival_14_quala_g 通勤電車と気分

我是通勤电车的专家。今天我也在车站的站台上等着电车。我要等的电车是从这个车站发车的，所以所有座位都是空的，但因为在我前面有 $N$ 个人排队，所以我能否坐下还不确定。 车厢里有 $K$ 个座位，排成一排，分别编号为 $1$ 到 $K$ 的连续整数。虽然知道了座位数和排在我前面的人数，似乎就能判断我能否坐下，但事情并没有那么简单。 我知道，人们会根据当天的心情选择座位的方式。具体来说，某天的心情有以下两种： - **“无论如何都想坐的心情”**：这种心情的人，只要有空座位，就会选择编号最小的空座位坐下。 - **“有余裕才想坐的心情”**：这种心情的人，如果有空座位且左右相邻的座位也都是空的，就会选择编号最小的那一个坐下。注意，如果某个座位没有相邻的座位，也可以视为相邻的座位是空的。 无论是哪种心情，如果没有满足条件的座位，就会放弃坐下。 现在，将排在我前面的人依次编号为第 $1$ 个人、第 $2$ 个人，……，第 $N$ 个人。也就是说，首先第 $1$ 个人进入车厢，根据当天的心情选择座位。接着第 $2$ 个人进入车厢，根据当天的心情选择座位。如此反复，直到第 $N$ 个人进入车厢并选择完座位后，轮到我进入车厢。 据我估计，第 $i$ 个人有 $p_i$ 百分比的概率会变成“无论如何都想坐的心情”，有 $100-p_i$ 百分比的概率会变成“有余裕才想坐的心情”。在这个假设下，当第 $N$ 个人进入车厢并选择完座位后，也就是轮到我进入车厢时，空座位的个数的期望是多少？请计算出来。

- 第 $1$ 行包含两个整数 $N$（排在队列中的人数，$1 \leq N \leq 100$）和 $K$（车厢中的座位数，$1 \leq K \leq 200$）。 - 接下来的 $N$ 行，每行一个整数 $p_i$（第 $i$ 个人变成“无论如何都想坐的心情”的概率，$0 \leq p_i \leq 100$）。

请输出第 $N$ 个人进入车厢并选择完座位后，空座位的个数的期望值，输出一个实数。只要与真实值的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

## 部分分 本题设置了部分分。 - 对于 $N \leq 10$ 的数据集全部答对可得 $30$ 分。 - 对于所有数据集全部答对，除上述 $30$ 分外还可再得 $70$ 分，总计 $100$ 分。 ## 样例解释 1 第 $1$ 个人总是“无论如何都想坐的心情”，考虑第 $2$、$3$ 个人的心情： - 第 $2$、$3$ 个人都为“无论如何都想坐的心情”的概率是 $0.3 \times 0.6 = 0.18$，空座位数为 $1$。 - 第 $2$ 个人为“无论如何都想坐的心情”，第 $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$。 由 ChatGPT 4.1 翻译