Problem:
 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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
N = int(input())

sushi = np.bincount(np.array(input().split(), dtype=np.int8),minlength=4)
total = (sushi * np.arange(4)).sum()






b = np.arange(N+1)[:,None]
c = np.arange(N+1)[None,:]
S_bc = 2 * b + 3 * c
dp = np.zeros((N+1,N+1))
for S in range(1,total+1):
    prev = dp
    a = S - S_bc
    dp = prev * a + N
    dp[1:] += prev[:-1] * b[1:]
    dp[:-1,1:] += prev[1:,:-1] * c[:,1:]
    dp /= (a+b+c)
    dp[a < 0] = 0

answer = dp[sushi[2],sushi[3]]
print(answer)

Solution (Python):
n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])

Solution (Python):
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    count_1 = a.count(1)
    count_2 = a.count(2)
    count_3 = a.count(3)

    
    expectation_of_attempts = [[[0.0 for num_dishes_3 in range(n + 1)] for num_dishes_2 in range(n + 1)] for num_dishes_1 in range(n + 1)]

    for k in range(count_3 + 1):
        for j in range(count_2 + count_3 + 1):
            if j + k > n:
                continue
            for i in range(n + 1):
                if i + j + k > n:
                    continue
                if i == 0 and j == 0 and k == 0:
                    continue
                if expectation_of_attempts[i][j][k] > 0.0:
                    return expectation_of_attempts[i][j][k]
                a = 0.0 if i == 0 else expectation_of_attempts[i - 1][j][k]
                b = 0.0 if j == 0 else expectation_of_attempts[i + 1][j - 1][k]
                c = 0.0 if k == 0 else expectation_of_attempts[i][j + 1][k - 1]

                expectation_of_attempts[i][j][k] = (i * a + j * b + k * c + n) / (i + j + k)

    return expectation_of_attempts[count_1][count_2][count_3]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):
n=int(input())
dp=[[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

l=[1]
for i in range(1,1000):
    l.append(1.0/i)

for k in range(r+1):
    for j in range(q+r-k+1):
        for i in range(n-k-j+1):
            if i==j==k==0:
                continue
            res=n
            if i>0:
                res+=i*dp[i-1][j][k]
            if j>0:
                res+=j*dp[i+1][j-1][k]
            if k>0:
                res+=k*dp[i][j+1][k-1]
            res*=1/(i+j+k)
            dp[i][j][k]=res

print(dp[p][q][r])

Solution (Python):
import sys

def tami(i,j,k):
  if (i == j == k == 0):
    return 0
  else:
    res = N
    if (i > 0):
      res += dp[i-1][j][k] * i
    if (j > 0):
      res += dp[i+1][j-1][k] * j
    if (k > 0):
      res += dp[i][j+1][k-1] * k
    res *= divTable[i + j + k]
    dp[i][j][k] = res
    return res
  
N = int(input())
a = list(map(float,input().split()))

one = a.count(1)
two = a.count(2)
three = a.count(3)

num = max(one,two,three)

dp = [[[-1]*(N+1) for i in range(N+1)] for i in range(N+1)]

divTable = [1]
for i in range(1, 10000):
  divTable.append(1.0 / i)

for k in range(0, N + 1):
  for j in range(0, N - k + 1):
    for i in range(0, N - k - j + 1):
      tami(i, j, k)

print(dp[one][two][three]+1)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1
    
M = t + d + m
D = [[[0] * (M + 1) for i in range(d + t + 1)] for j in range(t + 1)]

su = 0
D[t][d][m] = 1

divTable = [1]
for i in range(1, 10000):
  divTable.append(1.0 / i)


for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(M - i - j, -1, -1):
      y = D[i][j][k]
      if y != 0:
        div = y * divTable[i + j + k]
        if i + j + k != 0:
          su += N * div
        if i >= 1:
          D[i - 1][j + 1][k] += i * div
        if j >= 1: 
          D[i][j - 1][k + 1] += j * div
        if k >= 1:
          D[i][j][k - 1] += k * div

print(su)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(N - i - j, -1, -1):
      y = D[i][j][k]
      if i + j + k != 0:
        su += y * N /(i + j + k)
      if i >= 1:
        D[i - 1][j + 1][k] += y * i / (i + j + k)
      if j >= 1: 
        D[i][j - 1][k + 1] += y * j / (i + j + k)
      if k >= 1:
        D[i][j][k - 1] += y * k / (i + j + k)

print(su)

Solution (Python):



import sys
import bisect
input = sys.stdin.readline
def LI(): return list(map(int,input().split()))
def LIR(n): return [LI() for _ in range(n)]

def J():
    n = int(input())
    a = LI()
    a.sort()
    one = bisect.bisect_right(a,1)
    two = bisect.bisect_right(a,2) - one
    three = n - one - two

    
    
    dp = [[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(three+1):
        for j in range(two+three+1 - k):
            for i in range(one+two+three+1-k-j):
                if i == 0 and j == 0 and k == 0:
                    continue
                tmp = n*1.0
                if i > 0:
                    tmp += i*dp[i-1][j][k]
                if j > 0:
                    tmp += j*dp[i+1][j-1][k]
                if k > 0:
                    tmp += k*dp[i][j+1][k-1]
                dp[i][j][k] = tmp/(i+j+k)
    print(dp[one][two][three])
if __name__ == '__main__':
    J()

Solution (Python):
import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))



def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (not i|j) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for j in range(E+1-k):
            for i in range(N+1-k-j):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0)&(j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0)&(k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

if __name__ == "__main__":
    main()

Solution (Python):
import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))



def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (not i|j) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (not i|E|k) else N/(i+E+k)
        for j in range(E+1-k):
            for i in range(N+1-k-j):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0)&(j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0)&(k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

if __name__ == "__main__":
    main()

Solution (Python):
import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (i+j==0) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (i+E+k==0) else N/(i+E+k)
        for j in range(E+1):
            for i in range(N+1):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0) and (j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0) and (k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]

i3, i2, i1 = 0, 0, 0

for i in range(N):
	if a[i] == 3:
		i3 = i + 1
		i2 = i3
		i1 = i3
	elif a[i] == 2:
		i2 = i + 1
		i1 = i2
	elif a[i] == 1:
		i1 = i + 1
		
c1, c2, c3 = 0, 0, 0

for j3 in range(0, i3 + 1):
	for j2 in range(j3, i2 + 1):
		for j1 in range(j2, i1 + 1):
			
			if j3 > 0:
				c3 = dp[j3 - 1][j2][j1]
				p3 = j3 / N
			else:
				p3 = 0
			
			
			if j2 > j3:
				c2 = dp[j3][j2 - 1][j1] 
				p2 = (j2 - j3) / N
			else:
				p2 = 0
			
			
			if j1 > j2:
				c1 = dp[j3][j2][j1 - 1]
				p1 = (j1 - j2) / N
			else:
				p1 = 0
			
			p = p3 + p2 + p1
			if p > 0:
				dp[j3][j2][j1] = (c3 * p3 + c2 * p2 + c1 * p1) / p + 1 / p
			
print(dp[i3][i2][i1])

Solution (Python):
N = int(input())
a = list(map(int,input().split()))
I = 0
J = 0
K = 0
for i in range(N):
    if a[i] == 1:
        I += 1
    if a[i] == 2:
        J += 1
    if a[i] == 3:
        K += 1

dp = [[[0.0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
for k in range(K+1):
    for j in range(J+K+1):
        if j+k > N:
            break
        for i in range(N+1):
            S = i+j+k
            if S > N:
                break
            if S == 0:
                continue
            dp[i][j][k] = (i*dp[i-1][j][k]+j*dp[i+1][j-1][k]+k*dp[i][j+1][k-1]+N)/S
print(dp[I][J][K])

Solution (Python):
import fileinput


def num_turns(total, n_1, n_2, n_3):
    _n_1 = n_1 + n_2 + n_3 + 1
    _n_2 = n_2 + n_3 + 1
    _n_3 = n_3 + 1

    _arr = [0.0] * (_n_1 * _n_2 * _n_3)

    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3 - i_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3 - i_3 - i_2):
                with_sushi = i_1 + i_2 + i_3
                if with_sushi == 0:
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * _arr[(i_1 - 1) + i_2 * _n_1 + i_3 * _n_1 * _n_2]

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * _arr[i_1 + 1 + (i_2 - 1) * _n_1 + i_3 * _n_1 * _n_2]

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * _arr[i_1 + (i_2 + 1) * _n_1 + (i_3 - 1) * _n_1 * _n_2]
                _arr[i_1 + i_2 * _n_1 + i_3 * _n_1 * _n_2] = expectation

    return _arr[n_1 + n_2 * _n_1 + n_3 * _n_1 * _n_2]


inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3))

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

dp = [[[0.0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
CA = Counter(A)
SA = CA[1]
SB = CA[2]
SC = CA[3]
for c in range(SC+1):
    for b in range(SB+SC+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            if S == 0:
                continue
            dp[a][b][c] = N/S + a/S*dp[a-1][b][c]\
            +b/S*dp[a+1][b-1][c]\
            +c/S*dp[a][b+1][c - 1]

print(dp[SA][SB][SC])

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
CA = Counter(A)
SA = CA[1]
SB = CA[2]
SC = CA[3]
for c in range(SC+1):
    for b in range(SB+SC+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            if S == 0:
                continue
            dp[a][b][c] = N/S + a/S*dp[a-1][b][c]\
            +b/S*dp[a+1][b-1][c]\
            +c/S*dp[a][b+1][c - 1]

print(dp[SA][SB][SC])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 0

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])

Solution (Python):


n=int(input())
a = [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**7)

ko = [0]*4
for i in a:
    ko[i] += 1

dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]

cc=ko[1]+ko[2]+ko[3]
ccc=ko[2]+ko[3]
for k in range(ko[3]+1):
    for j in range(ccc+1-k):
        for i in range(cc+1-k-j):
            t=i+j+k

            if i != 0:
                dp[i][j][k] += (dp[i-1][j][k] + n/t)*i/t
            if j != 0 and i < n:
                dp[i][j][k] += (dp[i+1][j-1][k] + n/t)*j/t
            if k != 0 and j < n:
                dp[i][j][k] += (dp[i][j+1][k-1] + n/t)*k/t

print(dp[ko[1]][ko[2]][ko[3]])

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))

    dp = [[[0.0 for k in range(N + 1)]for j in range(N + 1)]for i in range(N + 1)]


    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    for k in range(three + 1):
        for j in range(two + three + 1 - k):
            for i in range(one + two + three + 1 -k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                ret = N * 1.0
                if i > 0:
                    ret += dp[i - 1][j][k] * i
                if j > 0:
                    ret += dp[i + 1][j - 1][k] * j 
                if k > 0:
                    ret += dp[i][j + 1][k -1] * k

                dp[i][j][k] = ret / (i + j + k)

    print(dp[one][two][three])

main()

Solution (Python):
import sys


input = sys.stdin.readline

def main():
    N = int(input())
    lst_a = list(map(int, input().split()))
    one, two, three = lst_a.count(1), lst_a.count(2), lst_a.count(3)

    
    
    dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

    for k in range(three + 1):
        for j in range(two + three + 1  - k):
            for i in range(one + two + three + 1 - k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                tmp = N * 1.0
                if i > 0:
                    tmp += i * dp[i -1][j][k]
                if j > 0:
                    tmp += j * dp[i + 1][j - 1][k]
                if k > 0:
                    tmp += k * dp[i][j + 1][k -1]
                dp[i][j][k] = tmp / (i + j + k)

    print(dp[one][two][three])


main()

Solution (Python):
from collections import Counter

n = int(input())
a = list(map(int, input().split()))

c = Counter(a)

dp = [[[0.0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

for z in range(c[3] + 1):
    for y in range(c[2]+1 + c[3] - z):
        for x in range(n+1 - z - y):
            if x + y + z == 0:
                continue
            ret = 0.0
            if x > 0:
                ret += dp[x-1][y][z] * x
            if y > 0:
                ret += dp[x+1][y-1][z] * y
            if z > 0:
                ret += dp[x][y+1][z-1] * z
            dp[x][y][z] = (ret + n) / (x + y + z)

print(dp[c[1]][c[2]][c[3]])

Solution (Python):
import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(input().split())
C=Counter(A)
c1,c2,c3=[C[s] for s in ('1','2','3')]
DP=[[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i>0:
                tmp+=DP[k][j+1][i-1]*i
            if j>0:
                tmp+=DP[k+1][j-1][i]*j
            if k>0:
                tmp+=DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)


def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])

def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])


def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))


def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))

def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()


def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    i = len(s)
    j = len(t)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:i -= 1
        elif dp[i][j] == dp[i][j-1]:j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)

def G():
    def dfs(x):
        if dp[x] != None:
            return dp[x]
        if len(v[x]) == 0:
            dp[x] = 0
            return 0
        else:
            res = 0
            for y in v[x]:
                res = max(res,dfs(y)+1)
            dp[x] = res
            return dp[x]
    n,m = LI()
    dp = [None for i in range(n)]
    v = [[] for i in range(n)]
    for i in range(m):
        x,y = LI()
        v[x-1].append(y-1)
    for i in range(n):
        dfs(i)
    print(max(dp))


def H():
    h,w = LI()
    s = SR(h)
    dp = [[0 for i in range(w)] for j in range(h)]
    dp[0][0] = 1
    for i in range(h-1):
        for j in range(w-1):
            if s[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
            if s[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
    for j in range(w-1):
        if s[h-1][j+1] == ".":
            dp[h-1][j+1] += dp[h-1][j]
            dp[h-1][j+1] %= mod
    for i in range(h-1):
        if s[i+1][w-1] == ".":
            dp[i+1][w-1] += dp[i][w-1]
            dp[i+1][w-1] %= mod
    print(dp[h-1][w-1])


def J():
    n = I()
    p = list(map(float, input().split()))
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(n+1):
            dp[i+1][j] = p[i]*dp[i][j-1]+(1-p[i])*dp[i][j]

    ans = 0
    m = math.floor(n/2)
    for i in range(m+1,n+1):
        ans += dp[n][i]
    print(ans)


def K():
    n = I()
    a = LI()
    d1 = a.count(1)
    d2 = a.count(2)
    d3 = a.count(3)
    dp = [[[0.0 for i in range(d3+1)] for j in range(d2+d3+1)] for k in range(n+1)]
    for k in range(d3+1):
        for j in range(d2+d3+1-k):
            for i in range(n+1-k-j):
                l = i+j+k
                if l == 0:continue
                res = n
                if i:
                    res += i*dp[i-1][j][k]
                if j:
                    res += j*dp[i+1][j-1][k]
                if k:
                    res += k*dp[i][j+1][k-1]
                dp[i][j][k] = res/l
    print(dp[d1][d2][d3])

if __name__ == "__main__":
    K()

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = tuple(map(int,input().split()))
c1 = a.count(1)
c2 = a.count(2)
c3 = a.count(3)

dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)] 
dp[0][0][0] = 0
for i in range(c3+1):
    for j in range(c2+c3-i+1):
        for k in range(n-i-j+1):
            if i == j == k == 0:
                continue
            tmp = n
            if k != 0:
                tmp += k*dp[k-1][j][i]
            if j != 0:
                tmp += j*dp[k+1][j-1][i]
            if i != 0:
                tmp += i*dp[k][j+1][i-1]
            dp[k][j][i] = tmp/(i+j+k)

print(dp[c1][c2][c3])

Solution (Python):
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[0] * (a + b + c - i - j + 1) for j in range(a + b - i + 1)] for i in range(a + 1)]

for i in range(a + 1):
    for j in range(a + b - i + 1):
        for k in range(a + b + c - i - j + 1):
            if i == j == k == 0:
                continue
            DP[i][j][k] = 1
            if i > 0: DP[i][j][k] += i / n * DP[i - 1][j + 1][k]
            if j > 0: DP[i][j][k] += j / n * DP[i][j - 1][k + 1]
            if k > 0: DP[i][j][k] += k / n * DP[i][j][k - 1]
            DP[i][j][k] *= n / (i + j + k)

print(DP[a][b][c])

Solution (Python):
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

for i in range(a + 1):
    for j in range(a + b - i + 1):
        for k in range(a + b + c - i - j + 1):
            if i == j == k == 0:
                continue
            DP[i][j][k] = 1
            if i > 0: DP[i][j][k] += i / n * DP[i - 1][j + 1][k]
            if j > 0: DP[i][j][k] += j / n * DP[i][j - 1][k + 1]
            if k > 0: DP[i][j][k] += k / n * DP[i][j][k - 1]
            DP[i][j][k] *= n / (i + j + k)

print(DP[a][b][c])

Solution (Python):
N = int(input())
b = [0, 0, 0]
for i in map(int, input().split()):
    b[i - 1] += 1
k1, k2, k3 = b
dp = [[[0] * (k3 + 1) for _ in range(k2 + k3 + 1)] for _ in range(k1 + k2 + k3 + 1)]
dp[0][0][0] = 0

for k in range(k3 + 1):
    for j in range(k2 + k3 + 1 - k):
        for i in range(k1 + k2 + k3 + 1 - j - k):
            if not i + j + k:
                continue
            dp[i][j][k] = ((dp[i - 1][j][k] * i if i else 0) + (dp[i + 1][j - 1][k] * j if j else 0) + (
                dp[i][j + 1][k - 1] * k if k else 0) + N) / (i + j + k)


print(dp[k1][k2][k3])

Solution (Python):
def main():
    N = int(input())
    c = [0] * 4
    for num in map(int, input().split()):
        c[num] += 1
    dp = [[[0] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
    for i3 in range(c[3]+1):
        for i2 in range(c[2]+c[3]-i3+1):
            for i1 in range(c[1]+c[2]+c[3]-i2-i3+1):
                try:
                    dp[i1][i2][i3] = (i1 * dp[i1-1][i2][i3] +
                                      i2 * dp[i1+1][i2-1][i3] +
                                      i3 * dp[i1][i2+1][i3-1] +
                                      N) / (i1+i2+i3)
                except IndexError:
                    continue
                except ZeroDivisionError:
                    continue

    print(dp[c[1]][c[2]][c[3]])


if __name__ == "__main__":
    main()

Solution (Python):


n = input()
a = map(int, raw_input().split())

n1 = 0
n2 = 0
n3 = 0
for ai in a:
    if ai == 1:
        n1 += 1
    elif ai == 2:
        n2 += 1
    else:
        n3 += 1

dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            if i + j + k > n:
                continue
            if i + j + k == 0:
                continue

            nr = float(n - i - j - k)
            dp[i][j][k] = nr / n
            if i > 0:
                dp[i][j][k] += (1.0 + dp[i - 1][j + 1][k]) * i / n
            if j > 0:
                dp[i][j][k] += (1.0 + dp[i][j - 1][k + 1]) * j / n
            if k > 0:
                dp[i][j][k] += (1.0 + dp[i][j][k - 1]) * k / n
            if n > i + j + k:
                dp[i][j][k] /= (1 - nr / n)
print(dp[n3][n2][n1])

Solution (Python):
N = int(input())
a_list = list(map(int, input().split()))

one, two, three = 0, 0, 0
for a in a_list:
    if a == 1:
        one += 1
    if a == 2:
        two += 1
    if a == 3:
        three += 1

dp = [[[0.0] * 301 for _ in range(301)] for _ in range(301)]
for k in range(three+1):
    for j in range(two+three+1-k):
        for i in range(one+two+three+1-k-j):
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = N * 1.0
            if i != 0:
                tmp += i * dp[i - 1][j][k]
            if j != 0:
                tmp += j * dp[i + 1][j - 1][k]
            if k != 0:
                tmp += k * dp[i][j + 1][k - 1]

            dp[i][j][k] = tmp / (i + j + k)
print(dp[one][two][three])

Solution (Python):
from __future__ import division

n = input()
a = map(int, raw_input().strip().split())

dp = [[[0 for i in xrange(n + 1)] for j in xrange(n + 1)] for k in xrange(n + 1)]

r = [0, 0, 0, 0]
for ai in a: r[ai] += 1

for r3 in xrange(n + 1):
    for r2 in xrange(n + 1):
        for r1 in xrange(n + 1):
            if r1 == r2 and r2 == r3 and r3 == 0: continue
            if r1 + r2 + r3 > n: break
            s = r1 + r2 + r3
            dp[r1][r2][r3] = n / s
            if r1 >= 1: dp[r1][r2][r3] += ((r1 * dp[r1 - 1][r2][r3]) / s)
            if r2 >= 1: dp[r1][r2][r3] += ((r2 * dp[r1 + 1][r2 - 1][r3]) / (s))
            if r3 >= 1: dp[r1][r2][r3] += ((r3 * dp[r1][r2 + 1][r3 - 1]) / (s))
            
ans = dp[r[1]][r[2]][r[3]]
print "{0:.10f}".format(ans)

Solution (Python):
"""
https://atcoder.jp/contests/dp/tasks/dp_j
"""
from sys import stdin
input = stdin.readline

n = int(input())
c = [0] * 4
l = list(map(int, input().split()))

for i in l:
    c[i] += 1

dp = [[[0.0] * (n + 1) for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 0
for n3 in range(0, c[3] + 1):
    for n2 in range(0, c[2] + c[3] - n3 + 1):
        for n1 in range(0, n-c[0]- n3 - n2 + 1):
            if n1 == n2 == n3 == 0:
                continue
            temp = n
            if n1 != 0:
                
                temp += n1*dp[n1 - 1][n2][n3]
            if n2 != 0:
                
                temp += n2*dp[n1 + 1][n2 - 1][n3]
            if n3 != 0:
                
                temp += n3*dp[n1][n2 + 1][n3 - 1]
            dp[n1][n2][n3] = temp / (n1 + n2 + n3)

print(dp[c[1]][c[2]][c[3]])

Solution (Python):



N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))



A,B,C = (a[i] for i in range(1,4))









dp = [ [ [0]*(A+B+C+1) for _ in range(B+C+1)]
        for _ in range(C+1) ] 

for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            
            

            try: 
                dp[c][b][a] = (
                        ( a * ( dp[c][b][a-1]   if a else 0)  ) + 
                        ( b * ( dp[c][b-1][a+1] if b else 0)  ) +
                        ( c * ( dp[c-1][b+1][a] if c else 0)  ) + N 
                       ) / ( a+b+c ) 
                
                
                
                
                
            except:
                continue

print(dp[C][B][A])