AT_dp_j Sushi

题目描述

有 $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$ 个盘子上还有寿司，则吃掉一个寿司；如果没有寿司，则什么也不做。

请你求出吃完所有寿司所需操作次数的期望值。

输入格式

输入从标准输入按以下格式给出。

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出吃完所有寿司所需操作次数的期望值。如果相对误差不超过 $10^{-9}$，则视为正确。

输入输出样例 #1

输入 #1

3
1 1 1

输出 #1

5.5

输入输出样例 #2

输入 #2

1
3

输出 #2

3

输入输出样例 #3

输入 #3

2
1 2

输出 #3

4.5

输入输出样例 #4

输入 #4

10
1 3 2 3 3 2 3 2 1 3

输出 #4

54.48064457488221

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 300$
• $1 \leq a_i \leq 3$

样例解释 1

吃掉第一个寿司所需操作次数的期望为 $1$。之后，吃掉第二个寿司所需操作次数的期望为 $1.5$。再之后，吃掉第三个寿司所需操作次数的期望为 $3$。因此，总的操作次数期望为 $1 + 1.5 + 3 = 5.5$。

样例解释 2

例如，输出 3.00、3.000000003、2.999999997 等也可以被判定为正确。

由 ChatGPT 4.1 翻译