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



Sample input:
3
1 1 1


Sample output:
5.5

Submission status: Time Limit Exceeded

Solution code:
import sys

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

#実家DPと気合い遷移式

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()

Submission status: Time Limit Exceeded

Solution code:
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):
            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)&(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()

Submission status: Time Limit Exceeded

Solution code:
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==0) and (j==0) and (k==0)) else N/(i+j+k) for k in range(C+1)] for i in range(B+C+1)] for j in range(A+B+C+1)]

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
from functools import lru_cache
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


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==0) and (j==0) and (k==0)) else N/(i+j+k) for k in range(C+1)] for i in range(B+C+1)] for j in range(A+B+C+1)]

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
from functools import lru_cache
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


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

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

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
from functools import lru_cache
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
from functools import lru_cache
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


N = I()
a = LI()

@lru_cache(maxsize=None)
def rec(i, j, k):
    if (i==0) and (j==0) and (k==0):
        return 0
    res = N
    if (i>0):
        res += rec(i-1, j, k)*i
    if (j>0):
        res += rec(i+1, j-1, k)*j
    if (k>0):
        res += rec(i, j+1, k-1)*k
    res /= i+j+k
    return res

print(rec(a.count(1), a.count(2), a.count(3)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

dp = [[[0]*303 for i in range(303)] for j in range(303)]

def calc(n1,n2,n3):
    tmp = N
    if dp[n1][n2][n3] != 0:
        return dp[n1][n2][n3]
    elif n1 == n2 == n3 == 0:
        return 0
    else:
        if n1 != 0:
            tmp += n1*calc(n1-1,n2,n3)
        if n2 != 0:
            tmp += n2*calc(n1+1,n2-1,n3)
        if n3 != 0:
            tmp += n3*calc(n1,n2+1,n3-1)
        tmp /= n1+n2+n3
        dp[n1][n2][n3] = tmp
        return tmp

N = inp()
aa = inpl()
cnts = [0]*4
for a in aa:
    cnts[a] += 1

print(calc(*cnts[1:]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

dp = [[[0]*303 for i in range(303)] for j in range(303)]

def calc(n1,n2,n3):
    tmp = 1
    if dp[n1][n2][n3] != 0:
        return dp[n1][n2][n3]
    elif n1 == n2 == n3 == 0:
        return 0
    else:
        if n1 != 0:
            tmp += n1/N*calc(n1-1,n2,n3)
        if n2 != 0:
            tmp += n2/N*calc(n1+1,n2-1,n3)
        if n3 != 0:
            tmp += n3/N*calc(n1,n2+1,n3-1)
        tmp *= N/(n1+n2+n3)
        dp[n1][n2][n3] = tmp
        return tmp

N = inp()
aa = inpl()
cnts = [0]*4
for a in aa:
    cnts[a] += 1

print(calc(*cnts[1:]))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N = I()
a = LI()

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

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

print(rec(a.count(1), a.count(2), a.count(3)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
N=int(input())
A=list(map(int,input().strip().split(' ')))
dic=defaultdict(int)
for i in range(4):
    dic[i]=0
for x in A:
    dic[x]+=1
start=tuple([dic[x] for x in range(4)])
    
Ans={}
def findans(a,b,c,d):
    #print(a,b,c,d)
    if (a,b,c,d) in Ans:
        return Ans[(a,b,c,d)]
    
    if a==len(A):
        return 0
    
    if a<0 or b<0 or c<0 or d<0:
        return 0
    N=len(A)
    temp1=findans(a+1,b-1,c,d)
    temp2=findans(a,b+1,c-1,d)
    temp3=findans(a,b,c+1,d-1)
    
    temp=(temp1*b+temp2*c+temp3*d)/N+1
    temp=temp/(1-a/N)
    Ans[(a,b,c,d)]=temp
    return temp
    
a,b,c,d=start
print(findans(a,b,c,d))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = list(map(int, input().split()))

dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(3 * N + 1)]
#dp[n][i3][i2]...n:上に乗ってる寿司の数、i3:寿司が3貫の皿の枚数、i2:2貫の枚数。
n, i3, i2 = 0, 0, 0

for i in range(N):
	if a[i] == 3:
		i3 += 1
		n += 3
	elif a[i] == 2:
		i2 += 1
		n += 2
	elif a[i] == 1:
		n += 1
		
c1, c2, c3 = 0, 0, 0
		
#寿司を引くのではなく足していく
for m in range(0, n + 1):
	for j3 in range(0, N + 1):
		for j2 in range(0, N + 1):
			j1 = m - 3 * j3 - 2 * j2
			if j1 < 0:
				continue
				
			#サイコロで3貫の皿が出たときの処理
			if j3 > 0 and j2 < N:
				c3 = dp[m - 1][j3 - 1][j2 + 1]
				p3 = j3 / N
			else:
				p3 = 0
			
			#2貫
			if j2 > 0:
				c2 = dp[m - 1][j3][j2 - 1] 
				p2 = j2 / N
			else:
				p2 = 0
			
			#1貫
			if j1 > 0:
				c1 = dp[m - 1][j3][j2]
				p1 = j1 / N
			else:
				p1 = 0
			
			p = p3 + p2 + p1
			if p > 0 and p <= 1:
				dp[m][j3][j2] = (c3 * p3 + c2 * p2 + c1 * p1) / p + 1 / p
			
print(dp[n][i3][i2])

Submission status: Time Limit Exceeded

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

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

def cal(i,j,k):
    if dp[i][j][k] != -1:
        return dp[i][j][k]
    else:
        res = 0
        if i != 0:
            res += i*cal(i-1,j+1,k)
        if j != 0:
            res += j*cal(i,j-1,k+1)
        if k != 0:
            res += k*cal(i,j,k-1)
        res += N
        res /= i+j+k
        dp[i][j][k] = res
        return res

print(cal(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
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]*(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])

Submission status: Time Limit Exceeded

Solution code:
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]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
for k in range(K+1):
    for j in range(J+K+1):
        if j+k > N:
            break
        for i in range(N+1):
            if i+j+k > N:
                break
            if i > 0:
                dp[i][j][k] += i*dp[i-1][j][k]
            if j > 0:
                dp[i][j][k] += j*dp[i+1][j-1][k]
            if k > 0:
                dp[i][j][k] += k*dp[i][j+1][k-1]
            if i+j+k > 0:
                dp[i][j][k] += N
                dp[i][j][k] /= i+j+k
print(dp[I][J][K])

Submission status: Time Limit Exceeded

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

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

def cal(i,j,k):
    if dp[i][j][k] != -1:
        return dp[i][j][k]
    else:
        res = 0
        if i != 0:
            res += i*cal(i-1,j+1,k)
        if j != 0:
            res += j*cal(i,j-1,k+1)
        if k != 0:
            res += k*cal(i,j,k-1)
        res += N
        res /= i+j+k
        dp[i][j][k] = res
        return res

print(cal(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
import fileinput


class Cache():
    def __init__(self, n_1, n_2, n_3):
        self._n_1 = n_1 + n_2 + n_3 + 1
        self._n_2 = n_2 + n_3 + 1
        self._n_3 = n_3 + 1

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

    def get(self, n_1, n_2, n_3):
        return self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2]

    def add(self, n_1, n_2, n_3, val):
        self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2] = val


def num_turns(total, n_1, n_2, n_3, cache):
    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:
                    cache.add(i_1, i_2, i_3, 0)
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * cache.get(i_1 - 1, i_2, i_3)

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * cache.get(i_1 + 1, i_2 - 1, i_3)

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * cache.get(i_1, i_2 + 1, i_3 - 1)
                cache.add(i_1, i_2, i_3, expectation)
    return cache.get(n_1, n_2, n_3)


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, Cache(n_1, n_2, n_3)))

Submission status: Time Limit Exceeded

Solution code:
import fileinput


class Cache():
    def __init__(self, n_1, n_2, n_3):
        self._n_1 = n_1 + n_2 + n_3 + 1
        self._n_2 = n_2 + n_3 + 1
        self._n_3 = n_3 + 1

        self._arr = [-1] * (self._n_1 * self._n_2 * self._n_3)

    def get(self, n_1, n_2, n_3):
        return self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2]

    def add(self, n_1, n_2, n_3, val):
        self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2] = val


def num_turns(total, n_1, n_2, n_3, cache):
    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:
                    cache.add(i_1, i_2, i_3, 0)
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * cache.get(i_1 - 1, i_2, i_3)

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * cache.get(i_1 + 1, i_2 - 1, i_3)

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * cache.get(i_1, i_2 + 1, i_3 - 1)
                cache.add(i_1, i_2, i_3, expectation)
    return cache.get(n_1, n_2, n_3)


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, Cache(n_1, n_2, n_3)))

Submission status: Time Limit Exceeded

Solution code:
import fileinput


class Cache():
    def __init__(self, n_1, n_2, n_3):
        self._n_1 = n_1 + n_2 + n_3 + 1
        self._n_2 = n_2 + n_3 + 1
        self._n_3 = n_3 + 1

        self._arr = [-1] * (self._n_1 * self._n_2 * self._n_3)

    def get(self, n_1, n_2, n_3):
        return self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2]

    def add(self, n_1, n_2, n_3, val):
        self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2] = val

def num_turns(total, n_1, n_2, n_3, cache):
    if cache.get(n_1, n_2, n_3) != -1:
        return cache.get(n_1, n_2, n_3)

    with_sushi = n_1 + n_2 + n_3 

    if with_sushi == 0: return 0

    res = total / with_sushi

    if n_1 > 0:
        p = n_1 / with_sushi
        res += p * num_turns(total, n_1 - 1, n_2, n_3, cache)
    
    if n_2 > 0:
        p = n_2 / with_sushi
        res += p * num_turns(total, n_1 + 1, n_2 - 1, n_3, cache)

    if n_3 > 0:
        p = n_3 / with_sushi
        res += p * num_turns(total, n_1, n_2 + 1, n_3 - 1, cache)

    cache.add(n_1, n_2, n_3, res)
    return res

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, Cache(n_1, n_2, n_3)))

Submission status: Time Limit Exceeded

Solution code:
import fileinput


class Cache():
    def __init__(self, total):
        self._total = total + 1

        self._arr = [-1] * (self._total**3)

    def get(self, n_1, n_2, n_3):
        return self._arr[n_1 + n_2 * self._total + n_3 * self._total * self._total]

    def add(self, n_1, n_2, n_3, val):
        self._arr[n_1 + n_2 * self._total + n_3 * self._total * self._total] = val

def num_turns(total, n_1, n_2, n_3, cache):
    if cache.get(n_1, n_2, n_3) != -1:
        return cache.get(n_1, n_2, n_3)

    with_sushi = n_1 + n_2 + n_3

    if with_sushi == 0: return 0

    res = total / with_sushi

    if n_1 > 0:
        p = n_1 / with_sushi
        res += p * num_turns(total, n_1 - 1, n_2, n_3, cache)
    
    if n_2 > 0:
        p = n_2 / with_sushi
        res += p * num_turns(total, n_1 + 1, n_2 - 1, n_3, cache)

    if n_3 > 0:
        p = n_3 / with_sushi
        res += p * num_turns(total, n_1, n_2 + 1, n_3 - 1, cache)

    cache.add(n_1, n_2, n_3, res)
    return res

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, Cache(total)))

Submission status: Time Limit Exceeded

Solution code:
import fileinput

cache = {}

def num_turns(total, n_1, n_2, n_3):
    if (n_1, n_2, n_3) in cache:
        return cache[(n_1, n_2, n_3)]
    with_sushi = n_1 + n_2 + n_3

    if with_sushi == 0: return 0

    res = total / with_sushi

    if n_1 > 0:
        p = n_1 / with_sushi
        res += p * num_turns(total, n_1 - 1, n_2, n_3)
    
    if n_2 > 0:
        p = n_2 / with_sushi
        res += p * num_turns(total, n_1 + 1, n_2 - 1, n_3)

    if n_3 > 0:
        p = n_3 / with_sushi
        res += p * num_turns(total, n_1, n_2 + 1, n_3 - 1)

    cache[(n_1, n_2, n_3)] = res
    return res

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))

Submission status: Time Limit Exceeded

Solution code:
import fileinput

def num_turns(total, n_1, n_2, n_3):
    with_sushi = n_1 + n_2 + n_3

    if with_sushi == 0: return 0

    res = total / (n_1 + n_2 + n_3)

    if n_1 > 0:
        p = n_1 / with_sushi
        res += p * num_turns(total, n_1 - 1, n_2, n_3)
    
    if n_2 > 0:
        p = n_2 / with_sushi
        res += p * num_turns(total, n_1 + 1, n_2 - 1, n_3)

    if n_3 > 0:
        p = n_3 / with_sushi
        res += p * num_turns(total, n_1, n_2 + 1, n_3 - 1)

    return res

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))

Submission status: Time Limit Exceeded

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

dp = Counter()

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

geta = 1000
geta2 = geta**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*geta2 + b*geta + c] = N/S + a/S*dp[(a-1)*geta2 + b*geta + c]\
            +b/S*dp[(a+1)*geta2 + (b-1)*geta + c]\
            +c/S*dp[a*geta2 + (b+1)*geta + c - 1]

print(dp[SA*geta2 + SB*geta + SC])

Submission status: Time Limit Exceeded

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

dp = Counter()

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

geta = 1000
geta2 = geta**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
            res = N/S
            res += a/S*dp[(a-1)*geta2 + b*geta + c]
            res += b/S*dp[(a+1)*geta2 + (b-1)*geta + c]
            res += c/S*dp[a*geta2 + (b+1)*geta + c - 1]
            dp[a*geta2 + b*geta + c] = res

print(dp[SA*geta2 + SB*geta + SC])

Submission status: Time Limit Exceeded

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

dp = Counter()

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

geta = 1000
geta2 = geta**2
for c in range(N+1):
    for b in range(N+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            res = 0 if S == 0 else N/S
            if a != 0:
                res += a/S*dp[(a-1)*geta2 + b*geta + c]
            if b != 0:
                res += b/S*dp[(a+1)*geta2 + (b-1)*geta + c]
            if c != 0:
                res += c/S*dp[a*geta2 + (b+1)*geta + c - 1]
            dp[a*geta2 + b*geta + c] = res
CA = Counter(A)
print(dp[CA[1]*geta2 + CA[2]*geta + CA[3]])

Submission status: Time Limit Exceeded

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

dp = [-1]*((n+1)*(n+1)*(n+1))
dp[0] = 0

def dfs(i, j, k, n):
    tmp = k*(n+1)**2  + j*(n+1)**1 + i*(n+1)**0
    if dp[tmp] != -1:
        return dp[tmp]
    res = 1
    if k > 0:
        res += (k/n) * dfs(i, j, k-1, n)
    if j > 0:
        res += (j/n) * dfs(i, j-1, k+1, n)
    if i > 0:
        res += (i/n) * dfs(i-1, j+1, k, n)
    dp[tmp] = (n/(i+k+j)) * res
    return dp[tmp]

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

dfs(cnt3, cnt2, cnt1, n)
print(dp[cnt1*(n+1)**2  + cnt2*(n+1)**1 + cnt3*(n+1)**0])

Submission status: Time Limit Exceeded

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

dp = [-1]*((n+1)*(n+1)*(n+1))
dp[0] = 0

def dfs(i, j, k, n):
    tmp = k*(n+1)**2  + j*(n+1)**1 + i*(n+1)**0
    if dp[tmp] != -1:
        return dp[tmp]
    res = 1
    if k > 0:
        res += (k/n) * dfs(i, j, k-1, n)
    if j > 0:
        res += (j/n) * dfs(i, j-1, k+1, n)
    if i > 0:
        res += (i/n) * dfs(i-1, j+1, k, n)
    dp[tmp] = (n/(i+k+j)) * res
    return dp[tmp]

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

dfs(cnt3, cnt2, cnt1, n)
print(dp[cnt1*(n+1)**2  + cnt2*(n+1)**1 + cnt3*(n+1)**0])