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):
from collections import deque
from itertools import product
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    A = map(int, input().strip().split())
    return N, A


def dfs(I, J, K, N, dp):
    for k in range(0, K+1):
        for j in range(0, J+K+1):
            for i in range(0, N+1):
                x = 0.0
                if not(i + j + k > N or i == 0 and j == 0 and k == 0):
                    x += dp[i-1][j] * (i / N) if i > 0 else 0.0
                    x += dp[i+1][j-1] * (j / N) if j > 0 else 0.0
                    x += dp[i][j+1] * (k / N) if k > 0 else 0.0
                    x += 1.0
                    x *= N / (i + j + k)
                dp[i][j] = x
    return dp[I][J]


def solve(N, A):
    dp = [[0.0 for j in range(N + 2)] for i in range(N + 2)]
    C = [0 for i in range(4)]
    for a in A:
        C[a] += 1
    return dfs(C[1], C[2], C[3], N, dp)


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
import collections
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = [int(x) for x in readline().split()]
ac = collections.Counter(A)
assert set(ac.keys()).issubset({1, 2, 3})


def solve(c1, c2, c3):
    K = c1 + c2 + c3
    L = K + 1
    L2 = L ** 2
    dp = [0.0] * L ** 3
    for i3 in range(c3 + 1):
        for i2 in range(c2 + c3 + 1):
            for i1 in range(N - i2 - i3 + 1):
                isum = i1 + i2 + i3
                if isum == 0:
                    continue
                i0 = N - i1 - i2 - i3
                if i0 < 0:
                    continue
                e = i0
                if i1 > 0:
                    e += i1 * (1.0 + dp[(i1 - 1) * L2 + i2 * L + i3])
                if i2 > 0 and i1 <= K:
                    e += i2 * (1.0 + dp[(i1 + 1) * L2 + (i2 - 1) * L + i3])
                if i3 > 0 and i2 + 1 <= c2 + c3:
                    e += i3 * (1.0 + dp[i1 * L2 + (i2 + 1) * L + i3 - 1])
                dp[i1 * L2 + i2 * L + i3] = e / isum
    return dp[c1 * L2 + c2 * L + c3]


if __name__ == "__main__":
    print(solve(ac[1], ac[2], ac[3]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
uno = a.count(1)
dos = a.count(2)
tres = n - uno - dos
dp = [[[.0]*(n+1) for _ in range(dos+tres+1)] for j in range(tres+1)]
for k in range(tres+1):
  for j in range(dos+tres-k+1):
    for i in range(n+1-j-k):
      if i+j+k == 0: continue
      v = i+j+k
      res = n
      if i: res += i * dp[k][j][i-1]
      if j: res += j * dp[k][j-1][i+1]
      if k: res += k * dp[k-1][j+1][i]
      dp[k][j][i] = res / v
print(dp[tres][dos][uno])

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    m = float(n)
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = m
                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[a[1]][a[2]][a[3]])

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

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


main()

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                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[a[1]][a[2]][a[3]])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

N, *A = map(int, open(0).read().split())

C = Counter(A)
dp = [[[.0] * (N + 2) for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(C[3] + 1):
    for j in range(N - C[1] - i + 1):
        for k in range(N - i - j + 1):
            if i + j + k != 0:
                dp[i][j][k] = (
                    N +
                    i * dp[i - 1][j + 1][k] +
                    j * dp[i][j - 1][k + 1] +
                    k * dp[i][j][k - 1]
                ) / (i + j + k)

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

Solution (Python):
from collections import Counter

N = int(input())
A = Counter(map(int, input().split()))
S = [None, A[3] + A[2] + A[1], A[3] + A[2], A[3]]

dp = [[[0] * (S[3] + 1) for _ in range(S[2] + 1)] for __ in range(S[1] + 1)]

for l in range(1, S[1] + 1):
    for m in range(S[2] + 1):
        if l < m:
            break
        for k in range(S[3] + 1):
            if m < k:
                break
            dp[l][m][k] = (dp[l - 1][m][k] * (l - m) + dp[l][m - 1][k] * (m - k) + dp[l][m][k - 1] * k + N) / l
print(dp[S[1]][S[2]][S[3]])

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

x=[0,0,0]
for i in range(n):
    x[a[i]-1]+=1


dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]

for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            v=k+i+j
            if 0<v<=n:
                dp[k][i][j]+=(dp[k][i][j-1]*j+dp[k][i-1][j+1]*i+dp[k-1][i+1][j]*k+n)/v

print(dp[x[2]][x[1]][x[0]])

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

x=[0,0,0]
for i in range(n):
    x[a[i]-1]+=1


dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]

for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            v=k+i+j
            if 0<v<=n:
                dp[k][i][j]+=dp[k][i][j-1]*(j/v)+dp[k][i-1][j+1]*(i/v)+dp[k-1][i+1][j]*(k/v)+n/v

print(dp[x[2]][x[1]][x[0]])

Solution (Python):

"""
Created on Fri Apr 24 22:56:49 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
def input():
    return sys.stdin.readline()[:-1]
mod = 10**9+7

N = int(input())

A = list(map(int,input().split()))



count = np.bincount(A, minlength=4)
total = np.sum(count * np.arange(4, dtype=int))

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


ans = dp[count[2],count[3]]
print(ans)

Solution (Python):

"""
Created on Fri Apr 24 22:56:49 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)


mod = 10**9+7





N, *A = map(int, open(0).read().split())

count = np.bincount(A, minlength=4)
total = np.sum(count * np.arange(4, dtype=int))

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


ans = dp[count[2],count[3]]
print(ans)

Solution (Python):
n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(3), A.count(2), A.count(1)
DP = [[[0.0 for k in range(a+b+c+1)] for j in range(a+b+1)] for i in range(a+1)]
for i in range(a+1):
    for j in range(a-i+b+1):
        for k in range(a-i+b-j+c+1):
            if i+j+k == 0:
                continue
            DP[i][j][k] = n
            if i > 0:
                DP[i][j][k] += i*DP[i-1][j+1][k]
            if j > 0:
                DP[i][j][k] += j*DP[i][j-1][k+1]
            if k > 0:
                DP[i][j][k] += k*DP[i][j][k-1]
            DP[i][j][k] /= i+j+k
print(DP[a][b][c])

Solution (Python):
n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(a+b+c-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])

Solution (Python):
N = int(input())
A = list(map(float, input().split()))
def solve():
    dp = [[[0]*(N+1-i-j) for j in range(N+1-i)] for i in range(N+1)]
    dp[N][0][0] = 0
    for i in range(N-1,-1,-1):
        for j in range(N-i,-1,-1):
            for k in range(N-i-j,-1,-1):
                dp[i][j][k] = 1/(1-i/N)
                if j != 0:
                    dp[i][j][k] += dp[i+1][j-1][k]*(j/(N-i))
                if k != 0:
                    dp[i][j][k] += dp[i][j+1][k-1]*(k/(N-i))
                if i+j+k != N:
                    dp[i][j][k] += dp[i][j][k+1]*(1-(j+k)/(N-i))
    c = {}
    for i in range(1,3):
        c[i] = A.count(i)
    ans = dp[0][c[1]][c[2]]
    
    return ans
print(solve())

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)


mod = 10**9+7

N = int(input())

A = list(map(int,input().split()))

count = np.bincount(A, minlength=4)
total = np.sum(count * np.arange(4, dtype=int))

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


ans = dp[count[2],count[3]]
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**5+10)

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
a = list(map(float, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)


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

def rec(i, j, k):
    if dp[i][j][k] > -1:
        return dp[i][j][k]

    res = 0
    if i > 0:
        res += rec(i - 1, j, k) * i / (i + j + k)
    if j > 0:
        res += rec(i + 1, j - 1, k) * j / (i + j + k)
    if k > 0:
        res += rec(i, j + 1, k - 1) * k / (i + j + k)
    res += N / (i + j + k)
    dp[i][j][k] = res
    return dp[i][j][k]

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 + j + k == 0:
                continue

            res = 0
            if i > 0:
                res += dp[i - 1][j][k] * i / (i + j + k)
            if j > 0:
                res += dp[i + 1][j - 1][k] * j / (i + j + k)
            if k > 0:
                res += dp[i][j + 1][k - 1] * k / (i + j + k)
            res += N / (i + j + k)
            dp[i][j][k] = res

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

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

dp = [[[0 for _ in range(301)]for __ in range(301)]for ___ in range(301)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            cnt = i + j + k
            if cnt == 0 or cnt > n :continue
            if i == 0 and j ==0 and k ==1:
                dp[i][j][k] = 1
                continue
            if k > 0:
                dp[i][j][k] += (1+dp[i][j][k-1] * cnt/(cnt-1))*k/cnt
            if j > 0:
                dp[i][j][k] += (1+dp[i][j-1][k+1])*j/cnt
            if i > 0:
                dp[i][j][k] += (1+dp[i-1][j+1][k])*i/cnt 
            
print(dp[a.count(3)][a.count(2)][a.count(1)])

Solution (Python):
n=int(input())
k=[0,0,0]
a,s,d=0,0,0
for i in input().split():
  if i=="1":a+=1
  elif i=="2":s+=1
  else:d+=1
dp=[[ [0]*(n+1) for j in range(n+1)] for i in range(n+1)]
for i in range(d+1):
  for j in range(d+s+1):
    for k in range(n+1-i-j):
      su=i+j+k
      ret=0
      if su:
        ret+=n/su
        if i>=1:
          ret+=dp[i-1][j+1][k]*i/su
        if j>=1 :
          ret+=dp[i][j-1][k+1]*j/su
        if k>=1:
          ret+=dp[i][j][k-1]*k/su
      dp[i][j][k]=ret
print(dp[d][s][a])

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
a = A.count(1)
b = A.count(2)
c = A.count(3)
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(c + 1):
    for j in range(b + c + 1 - k): 
        for i in range(a + b + c + 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[i][j][k])

Solution (Python):
from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
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-i):
        for k in range(n+1-i-j):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n/non_zero
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i/non_zero
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j/non_zero
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k/non_zero

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

Solution (Python):
from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
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-i):
        for k in range(n+1-i-j):
            non_zero = i+j+k
            if non_zero == 0:
                continue
            dp[i][j][k] = n
            if 0 <= i-1 and j+1 <= n:
                dp[i][j][k] += dp[i-1][j+1][k]*i
            if 0 <= j-1 and k+1 <= n:
                dp[i][j][k] += dp[i][j-1][k+1]*j
            if 0 <= k-1:
                dp[i][j][k] += dp[i][j][k-1]*k
            dp[i][j][k] /= non_zero

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

Solution (Python):
n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])

Solution (Python):
n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



N = ii()
N_f = float(N)
A = li()

cnt = [0, 0, 0]
for a in A:
    cnt[a-1] += 1



dp = dp3(0.0, 301, 301, 301)
dp[0][0][0] = 0

for k in range(cnt[2]+1):
    for j in range(cnt[1]+cnt[2]+1-k):
        for i in range(N+1-j-k):
            if i+j+k == 0:
                continue
            num = i+j+k
            dp[i][j][k] = N_f
            if i > 0:
                dp[i][j][k] += dp[i-1][j][k] * i
            if j > 0:
                dp[i][j][k] += dp[i+1][j-1][k] * j
            if k > 0:
                dp[i][j][k] += dp[i][j+1][k-1] * k
            dp[i][j][k] /= num

print(dp[cnt[0]][cnt[1]][cnt[2]])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



N = ii()
N_f = float(N)
A = li()

cnt = [0, 0, 0]
for a in A:
    cnt[a-1] += 1

dp = dp3(0.0, cnt[2]+1, cnt[1]+cnt[2]+1, N+1)
dp[0][0][0] = 0

for k in range(cnt[2]+1):
    for j in range(cnt[1]+cnt[2]+1-k):
        for i in range(N+1-j-k):
            if i+j+k == 0:
                continue
            num = i+j+k
            dp[i][j][k] = N_f
            if i > 0:
                dp[i][j][k] += dp[i-1][j][k] * i
            if j > 0:
                dp[i][j][k] += dp[i+1][j-1][k] * j
            if k > 0:
                dp[i][j][k] += dp[i][j+1][k-1] * k
            dp[i][j][k] /= num

print(dp[cnt[0]][cnt[1]][cnt[2]])

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



N = ii()
N_f = float(N)
A = li()

cnt = [0, 0, 0]
for a in A:
    cnt[a-1] += 1


dp = dp3(0.0, N+1, N+1, N+1)

dp[0][0][0] = 0

for k in range(cnt[2]+1):

    for j in range(cnt[1]+cnt[2]+1-k):
    
        
        
        for i in range(N+1-j-k):
            
            if i+j+k == 0:
                continue
            num = i+j+k
            dp[i][j][k] = N_f
            if i > 0:
                dp[i][j][k] += dp[i-1][j][k] * i
            if j > 0:
                dp[i][j][k] += dp[i+1][j-1][k] * j
            if k > 0:
                dp[i][j][k] += dp[i][j+1][k-1] * k
            dp[i][j][k] /= num

print(dp[cnt[0]][cnt[1]][cnt[2]])

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
c1 = 0
c2 = 0 
c3 = 0
for i in range(N):
    if a[i] == 1:
        c1 += 1
    if a[i] == 2:
        c2 += 1
    if a[i] == 3:
        c3 += 1
dp= [[[0] * (N+1) for i in range(N+1)] for j in range(N+1)]
for k in range(c3+1):
    for j in range(c3+c2-k+1):
        for i in range(N-j-k+1):
            if i == j == k == 0:
                continue
            else:
                res = N
                if i > 0:
                    res += dp[k][j][i-1]*i
                if j > 0:
                    res += dp[k][j-1][i+1]*j
                if k > 0:
                    res += dp[k-1][j+1][i]*k
                dp[k][j][i] = res/(i+j+k)
print(dp[c3][c2][c1])

Solution (Python):
from collections import Counter

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

c = Counter(a)

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




for k in range(c[3]+1):
    for j in range(c[3]+c[2]-k+1):
        for i in range(N-j-k+1):
            if i == j == k == 0:
                continue
            else:
                tmp = N
                if i > 0: 
                    tmp += dp[k][j][i-1]*i
                if j > 0:
                    tmp += dp[k][j-1][i+1]*j
                if k > 0:
                    tmp += dp[k-1][j+1][i]*k
                dp[k][j][i] = tmp/(i+j+k) 

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

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

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

    c1, c2, c3 = 0, 0, 0
    for aa in a:
        if aa == 1:
            c1 += 1
        elif aa == 2:
            c2 += 1
        else:
            c3 += 1

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = tuple(map(int, input().split()))

    
    
    

    I = 0
    J = 0
    K = 0
    for a in A:
        if a == 1:
            I += 1
        elif a == 2:
            J += 1
        else:
            K += 1

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

    
    
    

    for k in range(K + 1):
        for j in range(K + J + 1 - k):
            for i in range(N + 1 - k  - j):
                if i == j == k == 0:
                    continue
                tmp = N
                if i > 0:
                    tmp += i * dp[k][j][i - 1]
                if j > 0:
                    tmp += j * dp[k][j - 1][i + 1]
                if k > 0:
                    tmp += k * dp[k - 1][j + 1][i]
                dp[k][j][i] = tmp / (i + j + k)

    print (dp[K][J][I])

    

if __name__ == '__main__':
    main()

Solution (Python):
def main():

    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    
    
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i == j == k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: 
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) 

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():

    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    
    
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: 
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) 

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():

    from collections import Counter

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

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    
    
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: 
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) 

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter

    N = int(input())
    a = list(map(float, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    
    
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: 
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) 

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = LIST()

a_cnt = Counter(a)
num_1 = a_cnt[1]
num_2 = a_cnt[2]
num_3 = a_cnt[3]

dp = [[[0.0]*(301) for i in range(301)] for j in range(301)]
 
for i in range(1, N+1):
    for j in range(min(i, num_2+num_3)+1):
        for k in range(min(j, num_3)+1):
            s = i-j
            t = j-k
            res = 0
            if s > 0:
                res += dp[s-1][t][k]*s  
            if t > 0:
                res += dp[s+1][t-1][k]*t
            if k > 0:
                res += dp[s][t+1][k-1]*k
            res += N
            res /= (s+t+k)

            dp[s][t][k] = res

print(dp[num_1][num_2][num_3])

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

    n = int(input())

    l1 = l2 = l3 = 0
    for i in map(int,input().split()):
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1

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

    for i in range(1,n+1):
        for j in range(min(i,a)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n/(s+t+k)
                if s > 0:
                    count += dp[s-1][t][k]*(s/(s+t+k))     
                if t > 0 :
                    count += dp[s+1][t-1][k]*(t/(s+t+k))
                if k > 0 :
                    count += dp[s][t+1][k-1]*(k/(s+t+k))

                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()

Solution (Python):

n = int(input())
l1 = l2 = l3 = 0
l = [int(i) for i in input().split()]
for i in l:
    if i == 1:
        l1 += 1
    elif i == 2:
        l2 += 1
    else:
        l3 += 1
a = l2+l3
dp = [[[0.0]*(l3+1) for i in range(a+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(min(i,a)+1):
        for k in range(min(j,l3)+1):
            s = i-j
            t = j-k
            count = n/(s+t+k)
            if s > 0:
                count += dp[s-1][t][k]*(s/(s+t+k))     
            if t > 0 :
                count += dp[s+1][t-1][k]*(t/(s+t+k))
            if k > 0 :
                count += dp[s][t+1][k-1]*(k/(s+t+k))

            dp[s][t][k] = count

print(dp[l1][l2][l3])

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):
    for m in range(min(n,M)+1):
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])