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:
N = int(input())
a = list(map(int, input().split()))

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

u = N + 10
dp = [[[-1]* u for _ in range(u)] for _ in range(u)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    res = 0
    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 += N
    res /= (i + j + k)
    dp[i][j][k] = res

    return res

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]
dp = glist(301, 301, 301)
dp[0][0][0] = 0
def sub(i1,i2,i3):
    if dp[i1][i2][i3] is not None:
        return dp[i1][i2][i3]
    ans = n
    if i1>0:
        ans += i1 * sub(i1-1,i2,i3)
    if i2>0:
        ans += i2 * sub(i1+1,i2-1,i3)
    if i3>0:
        ans += i3 * sub(i1,i2+1,i3-1)
    ans = ans/(i1+i2+i3)
    dp[i1][i2][i3] = ans
    return ans
print(sub(n1,n2,n3))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]
dp = glist(301, 301, 301)
dp[0][0][0] = 0
count = [0, 0]
def sub(i1,i2,i3):
    count[0] += 1
    if dp[i1][i2][i3] is not None:
        count[1] += 1
        return dp[i1][i2][i3]
    ans = n
    if i1>0:
        ans += i1 * sub(i1-1,i2,i3)
    if i2>0:
        ans += i2 * sub(i1+1,i2-1,i3)
    if i3>0:
        ans += i3 * sub(i1,i2+1,i3-1)
    ans = ans/(i1+i2+i3)
    dp[i1][i2][i3] = ans
    return ans
print(sub(n1,n2,n3))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]
dp = glist(301, 301, 301)
dp[0][0][0] = 0
count = [0, 0]
def sub(i1,i2,i3):
    count[0] += 1
    if dp[i1][i2][i3] is not None:
        count[1] += 1
        return dp[i1][i2][i3]
    ans = n
    p = 0
    if i1>0:
        ans += i1 * sub(i1-1,i2,i3)
        p += i1
    if i2>0:
        ans += i2 * sub(i1+1,i2-1,i3)
        p += i2
    if i3>0:
        ans += i3 * sub(i1,i2+1,i3-1)
        p += i3
    ans = ans/p
    dp[i1][i2][i3] = ans
    return ans
print(sub(n1,n2,n3))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]
dp = glist(301, 301, 301)
dp[0][0][0] = 0
count = [0]
def sub(i1,i2,i3):
    count[0] += 1
    if dp[i1][i2][i3] is not None:
        return dp[i1][i2][i3]
    ans = 1
    p = 0
    if i1>0:
        ans += i1/n * sub(i1-1,i2,i3)
        p += i1/n
    if i2>0:
        ans += i2/n * sub(i1+1,i2-1,i3)
        p += i2/n
    if i3>0:
        ans += i3/n * sub(i1,i2+1,i3-1)
        p += i3/n
    ans = ans/p
    dp[i1][i2][i3] = ans
    return ans
print(sub(n1,n2,n3))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(301,301,301)

for s in range(S+1):
    for i1 in range(s+1):
        for i2 in range((s-i1)//2+1):
            d,m = divmod((s-i1-2*i2), 3)
            if m:
                continue
            i3 = d
            count += 1
            if i1==i2==i3==0:
                sub[i1][i2][i3] = 0
                continue
            ans = 1
            p = 0
            if i1>0:
                ans += i1/n * sub[i1-1][i2][i3]
                p += i1/n
            if i2>0:
                ans += i2/n * sub[i1+1][i2-1][i3]
                p += i2/n
            if i3>0:
                ans += i3/n * sub[i1][i2+1][i3-1]
                p += i3/n
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l):
    for num in l:
        []
sub = {}
count = 0
S = sum(a)
for s in range(S+1):
    for i1 in range(s+1):
        for i2 in range((s-i1)//2+1):
            d,m = divmod((s-i1-2*i2), 3)
            if m:
                continue
            i3 = d
            count += 1
            if i1==i2==i3==0:
                sub[i1,i2,i3] = 0
                continue
            ans = 1
            p = 0
            if i1>0:
                ans += i1/n * sub[i1-1,i2,i3]
                p += i1/n
            if i2>0:
                ans += i2/n * sub[i1+1,i2-1,i3]
                p += i2/n
            if i3>0:
                ans += i3/n * sub[i1,i2+1,i3-1]
                p += i3/n
            ans = ans/p
            sub[i1,i2,i3] = ans
print(sub[n1,n2,n3])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
sub = {}
count = [0]
S = sum(a)
for s in range(S+1):
    for i1 in range(s+1):
        for i2 in range((s-i1)//2+1):
            for i3 in range((s-i1-2*i2)//3+1):
                if i1==i2==i3==0:
                    sub[i1,i2,i3] = 0
                    continue
                ans = 1
                p = 0
                if i1>0:
                    ans += i1/n * sub[i1-1,i2,i3]
                    p += i1/n
                if i2>0:
                    ans += i2/n * sub[i1+1,i2-1,i3]
                    p += i2/n
                if i3>0:
                    ans += i3/n * sub[i1,i2+1,i3-1]
                    p += i3/n
                ans = ans/p
                sub[i1,i2,i3] = ans
print(sub[n1,n2,n3])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
dp = defaultdict(float)
dp[0,0,0] = 0
def sub(i1,i2,i3):
#     print(i1,i2,i3)
    if (i1,i2,i3) in dp:
        return dp[i1,i2,i3]
    ans = 1
    p = 0
    if i1>0:
        ans += i1/n * sub(i1-1,i2,i3)
        p += i1/n
    if i2>0:
        ans += i2/n * sub(i1+1,i2-1,i3)
        p += i2/n
    if i3>0:
        ans += i3/n * sub(i1,i2+1,i3-1)
        p += i3/n
    ans = ans/p
    dp[i1,i2,i3] = ans
    return ans
print(sub(n1,n2,n3))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000)

N = int(input())

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


def rec(i, j, k):
    global dp, N

    if dp[i][j][k] >= 0.0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0

    res = 0.0
    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 += N
    res *= (1.0 / (i+j+k))

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


dic = {}
dic[0] = 0
dic[1] = 0
dic[2] = 0
dic[3] = 0
for a in map(int, input().split(" ")):
    dic[a] += 1

print(rec(dic[1], dic[2], dic[3]))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

# サイコロで1が出るまでにサイコロを振る回数の期待値は、1が出る確率の逆数で1/(1/6) = 6
# 
# 皿に乗った寿司が1,0,0であるとき、寿司1が乗った皿を選ぶまでの試行回数の期待値は3
# [1,1,1]　に対して、最初に寿司が乗った皿を選ぶ試行回数の期待値は1/(3/3) = 1
# 残る状態は[0,1,1] (皿は区別しない)
# ここから寿司が乗った皿を選ぶ試行回数の期待値は1/(2/3) = 1.5
# 残る状態は[0,0,1]
# ここから寿司が乗った皿を選ぶ試行回数の期待値は1/(1/3) = 3
# すべて足し合わせると1 + 1.5 + 3 = 5.5

# 寿司が乗ってる皿の数が分かれば、次の状態に移行するときの期待値が分かるので足し上げていく
# dp[i][j][k] = 寿司が1個乗った皿がi個、寿司が2個乗った皿がj個、寿司が3個乗った皿がk個の
# 状態から最終状態までの期待値
# 寿司が1個乗った皿を選ぶとき
# dp[i][j][k] から dp[i - 1][j][k]に遷移
# N個からi個の皿を選ぶときの試行回数の期待値はN / i
# 寿司が2個乗った皿を選ぶとき (寿司が1個の皿が一つ増える)
# dp[i][j][k] から dp[i + 1][j - 1][k]に遷移
# N個からj個の皿を選ぶときの試行回数の期待値はN / j
# 寿司が3個乗った皿を選ぶとき (寿司が2個の皿が一つ増える)
# dp[i][j][k] から dp[i][j + 1][k - 1]に遷移
# dp[0][0][0] = 0 (寿司が乗った皿が残った状態は最終状態)

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

# sushi[n] : 寿司がn個乗った皿の枚数
sushi = [0] * 4
for a in A:
  if a > 0:
    sushi[a] += 1
    
dp = [[[-1 for k in range(N + 1)] for j in range(N + 1)] for i in range(N + 1)]

def solve(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.0
  ret = 0.0
  if i > 0:
    ret += solve(i - 1,j,k) * i
  if j > 0:
    ret += solve(i + 1,j - 1,k) * j
  if k > 0:
    ret += solve(i,j + 1,k - 1) * k
  ret += N
  ret *= 1.0 / (i + j + k)
  dp[i][j][k] = ret
  return ret

print(solve(sushi[1],sushi[2],sushi[3]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

N = int(input())
P = list(map(int, input().split()))
INF = -1.0
dp = [[[INF]*(N+1) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 0.0

def dfs(C1, C2, C3):
#i個の皿がCi皿ある時の期待値
    if dp[C1][C2][C3]==INF:
        ret = N
        if C1>=1:#1個の皿
            ret += dfs(C1-1, C2, C3)*C1
        if C2>=1:#2個の皿
            ret += dfs(C1+1, C2-1, C3)*C2
        if C3>=1:#3個の皿
            ret += dfs(C1, C2+1, C3-1)*C3
        ret /= (C1+C2+C3)
        dp[C1][C2][C3] = ret
    return dp[C1][C2][C3]

def main():
    print(dfs(P.count(1), P.count(2), P.count(3)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    cnt = Counter(As)

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

    ans = dp[cnt[1]][cnt[2]][cnt[3]]
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10**9)

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    cnt = Counter(As)

    N2, N3 = (N+1)*(N+1), (N+1)*(N+1)*(N+1)

    def rec(i, j, k):
        z = i*N2 + j*N + k
        expe = memo[z]
        if expe == -1:
            expe = 0.0
            if i > 0:
                expe += i/N * rec(i-1, j, k)
            if j > 0:
                expe += j/N * rec(i+1, j-1, k)
            if k > 0:
                expe += k/N * rec(i, j+1, k-1)
            if i+j+k:
                expe = (expe+1)*N/(i+j+k)
            memo[z] = expe
        return expe

    memo = [-1] * N3

    ans = rec(cnt[1], cnt[2], cnt[3])
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

dp=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
def c():
    for k in range(C+1):
        for j in range(B+C+1-k):
            for i in range(n+1-k-j):
                if i==0 and j==0 and k==0:
                    continue
                res=1.0*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[A][B][C])
c()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)


dp=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
def c():
    for k in range(C+1):
        for j in range(B+C+1-k):
            for i in range(n+1-k-j):
                if i==0 and j==0 and 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[A][B][C])
c()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

dp=[[[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(n+1-k-j):
            if i==0 and j==0 and 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[A][B][C])

Submission status: Time Limit Exceeded

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

A=a.count(1)
B=a.count(2)
C=a.count(3)

dp=[[[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(n+1-k-j):
            if i==0 and j==0 and 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[A][B][C])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e7))
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

d=A+B+C
memo=[[[-1]*(d+1) for _ in range(d+1)] for _ in range(d+1)]
memo[0][0][0]=0
def c(i,j,k):
        if memo[i][j][k]!=-1:
            return memo[i][j][k]
        else:
            memo[i][j][k]=n/(i+j+k)
            if 1<=i<=d:
                memo[i][j][k]+=c(i-1,j,k)*i/(i+j+k)
            if 0<=i<=d-1 and 1<=j<=d:
                memo[i][j][k]+=c(i+1,j-1,k)*j/(i+j+k)
            if 0<=j<=d-1 and 1<=k<=d:
                memo[i][j][k]+=c(i,j+1,k-1)*k/(i+j+k)
            return memo[i][j][k]

print(c(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e7))
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

memo=[[[-1]*(301) for _ in range(301)] for _ in range(301)]
memo[0][0][0]=0
def c(i,j,k):
        if memo[i][j][k]!=-1:
            return memo[i][j][k]
        else:
            memo[i][j][k]=n/(i+j+k)
            if 1<=i<=300:
                memo[i][j][k]+=c(i-1,j,k)*i/(i+j+k)
            if 0<=i<=299 and 1<=j<=300:
                memo[i][j][k]+=c(i+1,j-1,k)*j/(i+j+k)
            if 0<=j<=299 and 1<=k<=300:
                memo[i][j][k]+=c(i,j+1,k-1)*k/(i+j+k)
            return memo[i][j][k]

print(c(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e7))
n=int(input())
a=list(map(int,input().split()))

A=a.count(1)
B=a.count(2)
C=a.count(3)

memo=[[[-1]*(301) for _ in range(301)] for _ in range(301)]
memo[0][0][0]=0
def c(i,j,k):
        if memo[i][j][k]!=-1:
            return memo[i][j][k]
        else:
            memo[i][j][k]=n/(i+j+k)
            if 0<=i-1<=300:
                memo[i][j][k]+=c(i-1,j,k)*i/(i+j+k)
            if 0<=i+1<=300 and 0<=j-1<=300:
                memo[i][j][k]+=c(i+1,j-1,k)*j/(i+j+k)
            if 0<=j+1<=300 and 0<=k-1<=300:
                memo[i][j][k]+=c(i,j+1,k-1)*k/(i+j+k)
            return memo[i][j][k]

print(c(A,B,C))

Submission status: Time Limit Exceeded

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

# dp[i][j][k] = 1 個の皿が i 枚, 2 個の皿が j 枚, 3 この皿が k 枚になるときの操作回数の期待値
dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

def solution(i: int, j: int, k: int):
    if dp[i][j][k] or i+j+k == 0:
        return dp[i][j][k]

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

    return dp[i][j][k]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter as C
from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
N = int(input())
count = C(list(map(int, input().split())))
i,j,k = [count[n] for n in range(1,4)]

@lru_cache(maxsize=10**8)
def g(i):
    if i == 0:
        return 0
    elif i == 1:
        return N
    return g(i-1) + N/i

@lru_cache(maxsize=10**8)
def f(i,j,k):
    if j == 0 and k == 0:
        return g(i)
    ret = 0
    if i>0:
        ret += i * f(i-1,j,k)
    if j>0:
        ret += j * f(i+1,j-1,k)
    if k>0:
        ret += k * f(i,j+1,k-1)

    ret += N
    ret *= 1/(i+j+k)

    return ret

print(f(i,j,k))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter as C
from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
N = int(input())
MAX = 300
count = C(list(map(int, input().split())))
i,j,k = [count[n] for n in range(1,4)]

@lru_cache(maxsize=10**8)
def f(i,j,k):
    if i == 0 and j == 0 and k == 0:
        return 0
    ret = 0
    if i>0:
        ret += i * f(i-1,j,k)
    if j>0:
        ret += j * f(i+1,j-1,k)
    if k>0:
        ret += k * f(i,j+1,k-1)

    ret += N
    ret *= 1/(i+j+k)

    return ret

print(f(i,j,k))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter as C
N = int(input())
MAX = 300
count = C(list(map(int, input().split())))
dp = [[[-1 for k in range(MAX+1)] for j in range(MAX+1)] for i in range(MAX+ 1)]

def f(i,j,k):
    if dp[i][j][k]>=0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    ret = 0
    if i>0:
        ret += i * f(i-1,j,k)
    if j>0:
        ret += j * f(i+1,j-1,k)
    if k>0:
        ret += k * f(i,j+1,k-1)

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

    return ret

i,j,k = [count[n] for n in range(1,4)]
print(f(i,j,k))

Submission status: Time Limit Exceeded

Solution code:
# your code goes here
n=int(input())

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

ones,twos,threes=0,0,0

#count no of one two and three sushis plate
for i in a:
	if i==1:
		ones+=1
	
	elif i==2:
		twos+=1
		
	else:
		threes+=1;
		

#max possible no of different plates with one two or three sushis because 3 and two can be reduced to 1 if we eat sushis from them
max_ones=ones+twos+threes
max_twos=twos+threes
max_threes=threes



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


#here in loop we are subtracting because we are counting current no of differnt no of sushis plate present
for k in range(max_threes+1):
	for j in range(max_twos+1-k):
		for i in range(max_ones+1-j-k):
			
			if i+j+k==0:
				continue
			
			else:
				dp[i][j][k]=n/(i+j+k); #minimum no of operatin 3 plate mein ek ek sushi h to 3 baar khayengey
				
				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)
		
		
		
print(dp[i][j][k])

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
dic = collections.defaultdict(int)
for i in range(len(a)):
    dic[a[i]]+=1
ans = 0
dp = [[[-1] * 310 for i in range(310)]for j in range(310)]
def rec(i,j,k):
    if dp[i][j][k]>=0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0
    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 += n
    res *= 1.0/(i+j+k)

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

print(rec(dic[1],dic[2],dic[3]))

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
dic = collections.defaultdict(int)
for i in range(len(a)):
    dic[a[i]]+=1
ans = 0
dp = [[[-1] * 310 for i in range(310)]for j in range(310)]
def rec(i,j,k):
    if dp[i][j][k]>=0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0

    res = 0.0
    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 += n
    res *= 1.0/(i+j+k)

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

print(rec(dic[1],dic[2],dic[3]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    count = [0 for _ in range(4)]
    for a in A:
        count[a] += 1
    dp = [[[-1 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 0

    def rec(x, y, z):
        ret = dp[x][y][z]
        if ret >= 0:
            return ret
        ret = N
        if x > 0:
            ret += x * rec(x - 1, y, z)
        if y > 0:
            ret += y * rec(x + 1, y - 1, z)
        if z > 0:
            ret += z * rec(x, y + 1, z - 1)
        ret /= (x + y + z)
        dp[x][y][z] = ret
        return ret

    print(rec(count[1], count[2], count[3]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    count = [0 for _ in range(4)]
    for a in A:
        count[a] += 1
    dp = [[[-1 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 0

    def rec(x, y, z):
        ret = dp[x][y][z]
        if ret >= 0:
            return ret
        ret = N
        if x > 0:
            ret += x * rec(x - 1, y, z)
        if y > 0:
            ret += y * rec(x + 1, y - 1, z)
        if z > 0:
            ret += z * rec(x, y + 1, z - 1)
        ret /= (x + y + z)
        dp[x][y][z] = ret
        return ret

    print(rec(count[1], count[2], count[3]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

U = N + 1
inf = 1e18

dp = [[[inf] * U for _ in range(U)] for _ in range(U)]
dp[0][0][0] = 0.0

for c in range(N + 1):
    for b in range(N + 1):
        for a in range(N + 1):
            if a + b + c == 0:
                continue
            prob = 0
            E = N
            if a > 0:
                E += a * dp[a - 1][b][c]
                prob += a
            if b > 0 and a < N:
                E += b * dp[a + 1][b - 1][c]
                prob += b
            if c > 0 and b < N:
                E += c * dp[a][b + 1][c - 1]
                prob += c
            dp[a][b][c] = E / prob

x = C[1]
y = C[2]
z = C[3]
print(dp[x][y][z])

Submission status: Time Limit Exceeded

Solution code:
#### https://atcoder.jp/contests/dp/tasks/dp_j
####
d={(0,0,0):0}
def expected_days(c1,c2,c3):
	# print(c1,c2,c3)
	
	if (c1,c2,c3) in d:
		return d[(c1,c2,c3)]
	if c1<0 or c2<0 or c3<0:
		return 0
	e1=(c1/total)*expected_days(c1-1,c2,c3)
	e2=(c2/total)*expected_days(c1+1,c2-1,c3)
	e3=(c3/total)*expected_days(c1,c2+1,c3-1)

	d[(c1,c2,c3)]=(1+e1+e2+e3)*total/(c1+c2+c3)

	return d[(c1,c2,c3)]





n=int(input())
arr=list(map(lambda x:int(x)-1,input().split()))
cnt=[0]*3
for i in arr:
	cnt[i]+=1
cnt=tuple(cnt)
total=len(arr)
res=expected_days(*cnt)
# print(d)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
def f(i,j,k):
	global hashi
	if(i+j+k==0):
		return 0
	if((i,j,k) in hashi):
		return hashi[(i,j,k)]
	sumi=0
	if(i>0):
		sumi+=i*(1+f(i-1,j,k))
	if(j>0):
		sumi+=j*(1+f(i+1,j-1,k))
	if(k>0):
		sumi+=k*(1+f(i,j+1,k-1))
	sumi+=(n-i-j-k)
	sumi=sumi/(i+j+k)
	hashi[(i,j,k)]=sumi
	return sumi
n=int(input())
l=input().split()
li=[int(i) for i in l]
count1=0
count2=0
count3=0
for i in li:
	if(i==1):
		count1+=1
	elif(i==2):
		count2+=1
	else:
		count3+=1
hashi=dict()
print(f(count1,count2,count3))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

cnt = [0 for _ in range(4)]

sl = input().split()
for x in sl:
    dish = int(x)
    cnt[dish] += 1

ev = [[[0 for _ in range(n+5)] for _ in range(n+5)] for _ in range(n+5)]
p = [[[0 for _ in range(n+5)] for _ in range(n+5)] for _ in range(n+5)]
dp = [[[0 for _ in range(n+5)] for _ in range(n+5)] for _ in range(n+5)]

p[cnt[1]][cnt[2]][cnt[3]] = 1

for three in reversed(range(n+1)):
    for two in reversed(range(n+1)):
        for one in reversed(range(n+1)):
            if one == 0 and two == 0 and three == 0:
                continue
            
            p_waste = (n - one - two - three) / n
            ev_waste = p_waste / (1-p_waste)
            ev[one][two][three] += ev_waste * p[one][two][three]
            if one != 0:
                p_go = one / (one+two+three)
                p[one-1][two][three] += p[one][two][three] * p_go
                ev[one-1][two][three] += ev[one][two][three] * p_go
            if two != 0:
                p_go = two / (one+two+three)
                p[one+1][two-1][three] += p[one][two][three] * p_go
                ev[one+1][two-1][three] += ev[one][two][three] * p_go
            if three != 0:
                p_go = three / (one+two+three)
                p[one][two+1][three-1] += p[one][two][three] * p_go
                ev[one][two+1][three-1] += ev[one][two][three] * p_go

#print(ev)
#print(p[0][0][0])
#for row in ev:
#    print(row)
print(ev[0][0][0] + cnt[1] + cnt[2]*2 + cnt[3]*3)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = list(map(int, input().split()))
num1, num2, num3 = 0, 0, 0
num1 = A.count(1)
num2 = A.count(2)
num3 = n - num1 - num2
num2 += num3
num1 += num2
dp = [[[0.0] * (num3 + 1) for _ in range(num2 + 1)] for _ in range(num1 + 1)]

for k in range(num3 + 1):
    for j in range(num2 + 1):
        for i in range(num1 + 1):
            if i == 0 and j == 0 and k == 0:
                continue
            temp = n
            if i - 1 >= 0 and i <= num1:
                temp += i * dp[i - 1][j][k]
            if j - 1 >= 0 and i + 1 <= num1:
                temp += j * dp[i + 1][j - 1][k]
            if j + 1 <= num2 and k - 1 >= 0:
                temp += k * dp[i][j + 1][k - 1]
            dp[i][j][k] = temp / (i + j + k)
print(dp[num1 - num2][num2 - num3][num3])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = list(map(int, input().split()))
num1, num2, num3 = 0, 0, 0
for a in A:
    if a == 1:
        num1 += 1
    elif a == 2:
        num2 += 1
    else:
        num3 += 1
num2 += num3
num1 += num2
dp = [[[0.0] * (num3 + 1) for _ in range(num2 + 1)] for _ in range(num1 + 1)]

for k in range(num3 + 1):
    for j in range(num2 + 1):
        for i in range(num1 + 1):
            if i == 0 and j == 0 and k == 0:
                continue
            temp = n
            if i - 1 >= 0 and i <= num1:
                temp += i * dp[i - 1][j][k]
            if j - 1 >= 0 and i + 1 <= num1:
                temp += j * dp[i + 1][j - 1][k]
            if j + 1 <= num2 and k - 1 >= 0:
                temp += k * dp[i][j + 1][k - 1]
            dp[i][j][k] = temp / (i + j + k)
print(dp[num1 - num2][num2 - num3][num3])