/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 に寿司がある場合、皿 i の寿司を 1 個食べる。 皿 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 です。 その後、2 個目の寿司を食べるまでの操作回数の期待値は 1.5 です。 その後、3 個目の寿司を食べるまでの操作回数の期待値は 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
Score : 100 points
Problem Statement
There are N dishes, numbered 1, 2, \ldots, N. Initially, for each i (1 \leq i \leq N), Dish i has a_i (1 \leq a_i \leq 3) pieces of sushi on it.
Taro will perform the following operation repeatedly until all the pieces of sushi are eaten:
- Roll a die that shows the numbers 1, 2, \ldots, N with equal probabilities, and let i be the outcome. If there are some pieces of sushi on Dish i, eat one of them; if there is none, do nothing.
Find the expected number of times the operation is performed before all the pieces of sushi are eaten.
Constraints
- All values in input are integers.
- 1 \leq N \leq 300
- 1 \leq a_i \leq 3
Input
Input is given from Standard Input in the following format:
N a_1 a_2 \ldots a_N
Output
Print the expected number of times the operation is performed before all the pieces of sushi are eaten. The output is considered correct when the relative difference is not greater than 10^{-9}.
Sample Input 1
3 1 1 1
Sample Output 1
5.5
The expected number of operations before the first piece of sushi is eaten, is 1. After that, the expected number of operations before the second sushi is eaten, is 1.5. After that, the expected number of operations before the third sushi is eaten, is 3. Thus, the expected total number of operations is 1 + 1.5 + 3 = 5.5.
Sample Input 2
1 3
Sample Output 2
3
Outputs such as 3.00, 3.000000003 and 2.999999997 will also be accepted.
Sample Input 3
2 1 2
Sample Output 3
4.5
Sample Input 4
10 1 3 2 3 3 2 3 2 1 3
Sample Output 4
54.48064457488221