分数: 100 点
问题陈述
有 N 菜肴,已编号 1, 2, \ldots, N。 最初,对于每个 i (1 \leq i \leq N),菜 i 有 a_i (1 \leq a_i \leq 3)上面有几块寿司。
太郎会重复执行以下操作,直到吃完所有的寿司:
- 掷骰子显示数字 1, 2, \ldots, N 具有相同的概率,并让 i 是结果。如果盘子里有一些寿司 i,吃其中一个;如果没有,则什么都不做。
求在吃完所有寿司之前该操作执行的预期次数。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 300
- 1 \leq a_i \leq 3
输入
输入由标准输入按以下格式给出:
N a_1 a_2 \ldots a_N
输出
打印在吃完所有寿司之前执行该操作的预期次数。 当相对差异不大于时,输出被认为是正确的 10^{-9}.
示例输入 1
3 1 1 1
示例输出 1
5.5
吃第一块寿司之前的预期操作次数是 1。 之后,在吃第二个寿司之前的预期操作次数为 1.5。 之后,在吃第三个寿司之前的预期操作次数为 3。 因此,预期操作总数为 1 + 1.5 + 3 = 5.5.
示例输入 2
1 3
示例输出 2
3
输出如 3.00, 3.000000003 和 2.999999997 也将被接受。
示例输入 3
2 1 2
示例输出 3
4.5
示例输入 4
10 1 3 2 3 3 2 3 2 1 3
示例输出 4
54.48064457488221