← 返回题目列表

AtCoder · dp_j

J. 寿司

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

分数: 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