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


def solve(N: int, a: "List[int]"):

    c = [0]*4
    for A in a:
        c[A] += 1

    J = min(c[2]+c[3]+1, N+1)
    I = min(c[1]+c[2]+c[3]+1, N+1)
    kitai = [[[0]*(I+1) for _ in range(J+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(J):
            for i in range(I):
                tot = i+j+k
                if tot == 0 or tot > N:
                    continue
                res = N + kitai[k][j][i-1]*i + \
                    kitai[k][j-1][i+1]*j + kitai[k-1][j+1][i]*k
                kitai[k][j][i] = res/tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int(next(tokens)) for _ in range(N)]  
    solve(N, a)


if __name__ == '__main__':
    main()

Solution (Python):


N = int(input())
a = tuple(int(i) for i in input().split())

"""
i: 寿司が残り3個の皿の枚数
j: 寿司が残り2個の皿の枚数
k: 寿司が残り1個の皿の枚数

dp[i][j][k]: 必要な操作回数の期待値
"""
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]


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

C_1 = a.count(1)
C_2 = a.count(2)
C_3 = a.count(3)

for i in range(C_3+1):
    for j in range(C_2+C_3-i+1):
        for k in range(N-i-j+1):
            if i == j == k == 0:
                continue

            tmp = N
            if i > 0:
                tmp += dp[i-1][j+1][k] * i
            if j > 0:
                tmp += dp[i][j-1][k+1] * j
            if k > 0:
                tmp += dp[i][j][k-1] * k

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

print(dp[C_3][C_2][C_1])

Solution (Python):
def main():
	n = int(input())
	dp = [[[0] * (n - k - j + 1) for j in range(n - k + 1)] for k in range(n + 1)]
	for thr in range(n + 1):
		for two in range(n + 1):
			for one in range(n + 1):
				su = thr + two + one
				if su > n or su == 0:
					continue
				dp[thr][two][one] += n / su
				if thr:
					dp[thr][two][one] += dp[thr - 1][two + 1][one] * thr / su
				if two:
					dp[thr][two][one] += dp[thr][two - 1][one + 1] * two / su
				if one:
					dp[thr][two][one] += dp[thr][two][one - 1] * one / su
	a = b = c = 0
	for x in map(int, input().split()):
		if x == 3:
			a += 1
		elif x == 2:
			b += 1
		elif x == 1:
			c += 1
	print(dp[a][b][c])

if __name__ == "__main__":
	main()

Solution (Python):
n = int(input())
dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
for thr in range(n + 1):
	for two in range(n + 1):
		for one in range(n + 1):
			su = thr + two + one
			if su > n or su == 0:
				continue
			
			dp[thr][two][one] += n / su
			
			if thr:
				dp[thr][two][one] += dp[thr - 1][two + 1][one] * thr / su
			if two:
				dp[thr][two][one] += dp[thr][two - 1][one + 1] * two / su
			if one:
				dp[thr][two][one] += dp[thr][two][one - 1] * one / su
a = b = c = 0
for x in map(int, input().split()):
	if x == 3:
		a += 1
	elif x == 2:
		b += 1
	elif x == 1:
		c += 1
print(dp[a][b][c])

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
C = {1:0,2:0,3:0}
for i in range(N):
    C[A[i]] += 1
dp = [[[0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
for k in range(1,N+1):
    dp[0][0][k] = N/k+dp[0][0][k-1]
for j in range(1,N+1):
    for k in range(N+1-j):
        if k+1<=N and k>=1:
            dp[0][j][k] = N/(j+k)+j/(j+k)*dp[0][j-1][k+1]+k/(j+k)*dp[0][j][k-1]
        elif k==0:
            dp[0][j][0] = N/j+dp[0][j-1][1]
for i in range(1,N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            if j-1>=0 and k-1>=0:
                dp[i][j][k] = N/(i+j+k)+i/(i+j+k)*dp[i-1][j+1][k]+j/(i+j+k)*dp[i][j-1][k+1]+k/(i+j+k)*dp[i][j][k-1]
            elif j==0 and k-1>=0:
                dp[i][0][k] = N/(i+k)+i/(i+k)*dp[i-1][1][k]+k/(i+k)*dp[i][0][k-1]
            elif j-1>=0 and k==0:
                dp[i][j][0] = N/(i+j)+i/(i+j)*dp[i-1][j+1][0]+j/(i+j)*dp[i][j-1][1]
            elif j==0 and k==0:
                dp[i][j][0] = N/i+dp[i-1][1][0]
print(dp[C[3]][C[2]][C[1]])

Solution (Python):

N = int(input())
A = list(map(int, input().split()))
C = [0, A.count(1), A.count(2), A.count(3)]
dp = [[[0.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]+1-k):
        for i in range(N+1-j-k):
            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]
            dp[i][j][k] = res / (i + j + k)
 
print(dp[C[1]][C[2]][C[3]])

Solution (Python):
def p_j_dp():
    n = int(input())
    *a, = map(int, input().split())
    c1 = a.count(1)
    c2 = a.count(2)
    c3 = a.count(3)
    dp = [[[0.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 + 1 - k):
            for i in range(n + 1 - k - j):
                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 /= i + j + k
                dp[i][j][k] = res
    print(dp[c1][c2][c3])
    
p_j_dp()

Solution (Python):
def p_j_dp():
    n = int(input())
    *a, = map(int, input().split())
    c1 = a.count(1)
    c2 = a.count(2)
    c3 = a.count(3)
    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 + 1 - k):
            for i in range(n + 1 - k - j):
                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 /= i + j + k
                dp[i][j][k] = res
    print(dp[c1][c2][c3])
    
p_j_dp()

Solution (Python):
def main():
    N = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = 0, 0, 0
    for ai in a:
        if ai == 1:
            c1+=1
        elif ai == 2:
            c2 += 1
        else:
            c3 += 1
    dp = [[[0]*(c1+c2+c3+1) for i in range(c2+c3+1)] for j in range(c3+1)]
    for i in range(c3+1):
        for j in range(c2+c3+1):
            for k in range(c1+c2+c3+1):
                if i+j+k>N:
                    continue
                if i>0 and j<c2+c3:
                    dp[i][j][k] += (i/N)*dp[i-1][j+1][k]
                if j>0 and k<c1+c2+c3:
                    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]
                if  i+j+k == 0:
                    continue
                dp[i][j][k]+=1
                dp[i][j][k]*=N/(i+j+k)
    print(dp[c3][c2][c1])
main()

Solution (Python):


import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
C = Counter(A)


dp = list3d(N+1, N+1, N+1, INF)

dp[0][0][0] = 0.0
for i in range(N+1):
    for j in range(N+1):
        
        if i+j > N:
            break
        for k in range(N+1):
            
            if i+j+k > N:
                break
            if i == j == k == 0:
                continue
            
            tmp = (i + j + k) / N
            
            res = 1 / tmp
            
            if i and j < N: 
                res += (i/N) / tmp * dp[i-1][j+1][k]
            if j and k < N: 
                res += (j/N) / tmp * dp[i][j-1][k+1]
            if k: 
                res += (k/N) / tmp * dp[i][j][k-1]
            dp[i][j][k] = res
print(dp[C[3]][C[2]][C[1]])

Solution (Python):
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)]
dp[0][0][0] = 0

a,b,c = 0,0,0
for i in range(N):
    if A[i] == 1:
        a += 1
    elif A[i] == 2:
        b += 1
    else:
        c += 1

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

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

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    cnt_aa = Counter(aa)
    nc3 = cnt_aa[3]
    nc2 = cnt_aa[2]
    nc1 = cnt_aa[1]
    dp = [[[0] * (n + 1) for _ in range(nc3 + nc2 + 1)] for _ in range(nc3 + 1)]
    for c3 in range(nc3 + 1):
        for c2 in range(nc2 + nc3 - c3 + 1):
            if c3 + c2 > n: break
            for c1 in range(n + 1):
                s = c1 + c2 + c3
                if s > n: break
                if c1 > 0: dp[c3][c2][c1] += (dp[c3][c2][c1 - 1] + n / s) * c1 / s
                if c2 > 0: dp[c3][c2][c1] += (dp[c3][c2 - 1][c1 + 1] + n / s) * c2 / s
                if c3 > 0: dp[c3][c2][c1] += (dp[c3 - 1][c2 + 1][c1] + n / s) * c3 / s
    print(dp[nc3][nc2][nc1])

main()

Solution (Python):
from collections import Counter

def main():
    N = int(input())
    a = Counter(map(int, input().split()))
    a1, a2, a3 = a.get(1, 0), a.get(2, 0), a.get(3, 0)
    a123 = a1 + a2 + a3 + 1
    u = [[0.0] * (a123 - c2) for c2 in range(a123)]
    v = [[0.0] * (a123 - c2) for c2 in range(a123)]
    t1 = 0.0
    v2 = v[0]
    for c1 in range(1, a123):
        v2[c1] = t1 = N / c1 + t1
    for c2 in range(1, a123):
        v2 = v[c2]
        for c1, t2 in zip(range(301 - c2), v[c2 - 1][1:]):
            v2[c1] = t1 = (N + c1 * t1 + c2 * t2) / (c1 + c2)

    for c3 in range(1, a3 + 1):
        u, v = v, u
        v2 = v[0]
        for c1, t3 in zip(range(a123 - c3), u[1]):
            v2[c1] = t1 = (N + c1 * t1 + c3 * t3) / (c1 + c3)
        for c2 in range(1, a123 - c3):
            v2 = v[c2]
            c23 = c2 + c3
            for c1, t2, t3 in zip(range(a123 - c3 - c2), v[c2 - 1][1:], u[c2 + 1]):
                v2[c1] = t1 = (N + c1 * t1 + c2 * t2 + c3 * t3) / (c1 + c23)

    print(v[a2][a1])
main()

Solution (Python):
N = int(input())
def main():
    a = list(map(int, input().split()))
    d = {0:0, 1:0, 2:0, 3:0}
    for i in a:
        d[i] += 1
    d1 = d[1]
    d123 = d[1] + d[2] + d[3]
    d23 = d[2] + d[3]
    d3 = d[3]
    d2 = d[2]
    l = [[[0] * (d123 + 1) for _ in range(d23 + 1)] for _ in range(d3 + 1)]
    for i in range(d3 + 1):
        for j in range(d23 + 1):
            for k in range(d123 + 1):
                if i + j + k == 0:
                    continue
                if i + j + k > d123:
                    continue
                if i + j > d23:
                    continue
                total = i + j + k
                a = b = c = 0
                if k > 0:
                    a = k * l[i][j][k-1]
                if j > 0:
                    b = j * l[i][j-1][k + 1]
                if i > 0:
                    c = i * l[i-1][j + 1][k]
                l[i][j][k] = (a + b + c + N)/total
    print(l[d3][d2][d1])
main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(), np.int8)

counter = np.bincount(A,minlength=4)
S = A.sum()

B = (counter[2]+counter[3])
C = counter[3]

dp = np.zeros((B+1,C+1),np.float64)

p2 = np.tile(np.arange(B+1)[:,None],(1,C+1))
p3 = np.tile(np.arange(C+1)[None,:],(B+1,1))

bc = np.arange(B+1)[:,None]*2+np.arange(C+1)[None,:]*3

for n in range(1,S+1):
    prev = dp
    one = n-bc
    p1 = np.maximum(0,one)
    dp = p1*prev + N
    dp[1:] += p2[1:]*prev[:-1]
    dp[:-1,1:] += p3[:-1,1:]*prev[1:,:-1]
    dp /= (p1+p2+p3)

answer = dp[B-C,C]
print(answer)

Solution (Python):

from collections import defaultdict

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

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












dp = [[[0.0 for _ in range(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 or i+j+k == 0:
        continue
      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] += N
      dp[i][j][k] /= (i+j+k)

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

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

N = int(input())


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

a = list(map(int, input().split()))
I, J, K = a.count(1), a.count(2), a.count(3)


for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if (i+j+k) <= N:
                
                if (i+j+k) != 0:
                    dp[i][j][k] = float(N) / float(i+j+k)
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * float(i) / float(i+j+k)
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * float(j) / float(i+j+k)
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * float(k) / float(i+j+k)
print(dp[I][J][K])

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

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

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

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k > N: continue
            if i+j+k == 0: continue
            tmp = 1.0*N
            if i>0: tmp += i*dp[i-1][j][k]*1.0
            if j>0: tmp += j*dp[i+1][j-1][k]*1.0
            if k>0: tmp += k*dp[i][j+1][k-1]*1.0
            dp[i][j][k] = tmp/float(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])

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

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

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

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

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

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

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

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

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

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

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

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k > N: continue
            if i+j+k == 0: continue
            tmp = 1.0*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[IJK[0]][IJK[1]][IJK[2]])

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
dp = [[[float(0)] * (N+1) for _ in range(N+1)] for _ in range(N+2)]
ans = float(0)
count = [0]*3
for i in a:
    count[i-1] +=1



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

ans = dp[count[0]][count[1]][count[2]]

print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
dp = [[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
x,y,z = 0,0,0
for i in range(n):
    if a[i] == 1:
        x += 1
    elif a[i] == 2:
        y += 1
    else:
        z += 1
s = x + y + z
for k in range(z+1):
    for j in range(y+z+1-k):
        for i in range(s+1-k-j):
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = 1.0*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[x][y][z])

Solution (Python):





def main():
    from collections import Counter

    def tami(i, j, k):
        if i is 0 and j is 0 and k is 0:
            return

        res = fN
        if i is 0:
            pass
        else:
            res += dp[i - 1][j][k] * i
        if j is 0:
            pass
        else:
            res += dp[i + 1][j - 1][k] * j
        if k is 0:
            pass
        else:
            res += dp[i][j + 1][k - 1] * k
        res *= divTable[i + j + k]

        dp[i][j][k] = res
        return

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

    c = Counter(a)
    one = c[1]
    two = c[2]
    three = c[3]

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

    divTable = [1]
    for i in range(1, N * 3 + 1):
        divTable.append(1.0 / i)

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

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


if __name__ == '__main__':
    main()

Solution (Python):





def main():
    from collections import Counter

    def tami(i, j, k):
        if i is 0 and j is 0 and k is 0:
            return

        res = fN
        if i is not 0:
            res += dp[i - 1][j][k] * i
        if j is not 0:
            res += dp[i + 1][j - 1][k] * j
        if k is not 0:
            res += dp[i][j + 1][k - 1] * k
        res *= divTable[i + j + k]

        dp[i][j][k] = res
        return

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

    c = Counter(a)
    one = c[1]
    two = c[2]
    three = c[3]

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

    divTable = [1]
    for i in range(1, N * 3 + 1):
        divTable.append(1.0 / i)

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

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


if __name__ == '__main__':
    main()

Solution (Python):





def main():
    from collections import Counter

    def tami(i, j, k):
        if i is 0 and j is 0 and k is 0:
            return

        res = fN
        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

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

    c = Counter(a)
    one = c[1]
    two = c[2]
    three = c[3]

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

    divTable = [1]
    for i in range(1, N * 3 + 1):
        divTable.append(1.0 / i)

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

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


if __name__ == '__main__':
    main()

Solution (Python):





def main():
    from collections import Counter

    def tami(i, j, k):
        if i is 0 and j is 0 and k is 0:
            return

        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

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

    c = Counter(a)
    one = c[1]
    two = c[2]
    three = c[3]

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

    divTable = [1]
    for i in range(1, N * 3 + 1):
        divTable.append(1.0 / i)

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

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


if __name__ == '__main__':
    main()

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

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    

    div_tbl = [1]
    div_tbl.extend([1 / i for i in range(1, 300 * 3 + 1)])

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              * div_tbl[r1 + r2 + r3]

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

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

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
a = [int(x) for x in input().split()]

p = [0] * 3
for i in a:
    p[3-i] += 1

dp = [[[0] * (N+1-i-j) for j in range(N+1-i)] for i 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):
            if i + j + k == 0:
                continue
            if i > 0:
                dp[i][j][k] += dp[i-1][j+1][k] * i
            if j > 0:
                dp[i][j][k] += dp[i][j-1][k+1] * j
            if k > 0:
                dp[i][j][k] += dp[i][j][k-1] * k
            dp[i][j][k] += N
            dp[i][j][k] /= (i + j + k)

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

Solution (Python):
import collections

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

d = collections.Counter(a)
s = sum(a)
n1, n2, n3 = d[1], d[2], d[3]

dp = [[0]*(n2+n3+1) for _ in range(n3+1)]
dp[n3][n2] = 1.0
ans = 0

for i in range(s, 0, -1):
  dp2 = [[0]*(n2+n3+1) for _ in range(n3+1)]
  for i3 in range(n3, -1, -1):
    for i2 in range(min(n2+n3, (i-i3*3)//2), -1, -1):
      i1 = i-i3*3-i2*2
      i0 = n-i1-i2-i3
      if i2 < 0 or i1 < 0 or i0 < 0: continue
      e0 = n/(i1+i2+i3)
      dp2[i3][i2] += dp[i3][i2] * i1/(i1+i2+i3)
      ans += dp[i3][i2] * e0*(i1/(i1+i2+i3))
      if i2 > 0:
        dp2[i3][i2-1] += dp[i3][i2] * i2/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i2/(i1+i2+i3))
      if i3 > 0 and i2 < n2+n3:
        dp2[i3-1][i2+1] += dp[i3][i2] * i3/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i3/(i1+i2+i3))
  dp = dp2

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

one = D[1]
two = D[2]
three = D[3]

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

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    dp[c1][c2][c3] = res/(c1 + c2 + c3)

for k in range(three+1) :
    for j in range(two+three+1 - k) :
        for i in range(one+two+three+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

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

Solution (Python):


import sys

class JSushi:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]

        u, v, w = a.count(1), a.count(2), a.count(3)

        dp = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
        for k in range(n + 1):
            for j in range(n + 1 - k):
                for i in range(n + 1 - j - k):
                    if i == j == k == 0:
                        continue
                    s = i + j + k
                    x = 0
                    x += dp[i][j + 1][k - 1] * k
                    x += dp[i + 1][j - 1][k] * j
                    x += dp[i - 1][j][k] * i
                    x += n
                    x /= s
                    dp[i][j][k] = x

        print(dp[u][v][w])


solver = JSushi()
input = sys.stdin.readline

solver.solve()

Solution (Python):
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 10
N=int(raw_input())
f=map(int,raw_input().split())
cc=Counter(f)
dp=[]
for i in range(N+2):
	x=[]
	for j in range(N+2):
		y=[]
		for k in range(N+2):
			y.append(0)
		x.append(y)
	dp.append(x)


for k in range(0,N+1):			
	for j in range(0,N+1):			
		for i in range(0,N+1):
			if(i==0 and j==0 and k==0):
				dp[i][j][k]=0			
			elif(i+j+k<=N):
				
				dp[i][j][k] = N
				if(i>=1):
					dp[i][j][k]+=dp[i-1][j][k]*(i)
				if(j>=1):	
					 dp[i][j][k]+=dp[i+1][j-1][k]*(j)
				if(k>=1):	 
					 dp[i][j][k]+=dp[i][j+1][k-1]*(k)
				
				dp[i][j][k]=dp[i][j][k]/float(i+j+k)
				

print dp[cc[1]][cc[2]][cc[3]]

Solution (Python):
import collections


N = int(input())
c = collections.Counter(list(map(int, input().split())))


dp = [[[0.0 for k in range(310)] for j in range(310)] for i in range(310)]


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



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