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: Runtime Error

Solution code:
import collections
import sys
import numpy as np

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

N = int(readline())
A = [int(x) for x in readline().split()]
ac = collections.Counter(A)
assert set(ac.keys()).issubset({1, 2, 3})
C1, C2, C3 = ac[1], ac[2], ac[3]
K = C1 + C2 + C3
dp = np.zeros((K + 3, C2 + C3 + 2, C3 + 1), dtype=np.float64)


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


if __name__ == "__main__":
    print(solve(C1, C2, C3))

Submission status: Runtime Error

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

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


main()

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import Counter

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

dp = np.zeros((S[1] + 1, S[2] + 1, S[3] + 1), dtype=float)
for l in range(1, S[1] + 1):
    for m in range(S[2] + 1):
        if l < m:
            break
        mk = min(m + 1, S[3] + 1)
        dp[l][m][:mk] = (dp[l - 1][m][:mk] * (l - m) + dp[l][m - 1][:mk] * (m - np.arange(mk)) + N) / l

        matr = np.tile(np.arange(mk) / l, (mk, 1))
        matr[np.tri(mk, dtype=bool)] = 1
        matr = np.multiply.accumulate(matr, axis=1)
        matr[np.tri(mk, k=-1, dtype=bool)] = 0

        dp[l][m][:mk] = dp[l][m][:mk] @ matr
print(dp[S[1]][S[2]][S[3]])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)


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



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

    if DP[i][j][k]!=0:
        return DP[i][j][k]
    elif i==0 and j==0 and k==0:
        return DP[i][j][k]
    else:
        res=N
        if i-1>=0:
            res+=rec(i-1,j,k)*i
        if j-1>=0:
            res+=rec(i+1,j-1,k)*j
        if k-1>=0:
            res+=rec(i,j+1,k-1)*k
        
        DP[i][j][k]=res/(i+j+k)
        return DP[i][j][k]

one=0
two=0
three=0
for l in range(N):
    if A[l]==1:
        one+=1
    elif A[l]==2:
        two+=1
    else:
        three+=1

DP=[[[0]*(three+1) for index1 in range(two+1)] for index2 in range(one+1)]
rec(one,two,three)
print(DP[one][two][three])

Submission status: Runtime Error

Solution code:
from collections import Counter
from functools import lru_cache


@lru_cache(maxsize=None)
def dp(i, j, k, n):
    if i == j == k == 0:
        return 0
    ret = 0
    if i > 0:
        ret += i * dp(i - 1, j, k, n)
    if j > 0:
        ret += j * dp(i + 1, j - 1, k, n)
    if k > 0:
        ret += k * dp(i, j + 1, k - 1, n)
    ret += n
    ret /= i + j + k
    return ret


def submit():
    n = int(input())
    a = list(map(int, input().split()))
    c = Counter(a)
    print(dp(c[1], c[2], c[3], n))


submit()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

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

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

#dp = dp3(-1.0, cnt[2]+1, cnt[1]+cnt[2]+1, N+1)
dp = dp3(0.0, N+1, N+1, N+1)
dp = dp3(0.0, 301, 301, 301)
dp[0][0][0] = 0

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

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

start_plate = [0] * 3
for n in range(N):
    start_plate[A[n] - 1] += 1

max_N = 301
dp_calculated = [[[False] * max_N for _ in range(max_N)] for __ in range(max_N)]
memo = [[[0] * max_N for _ in range(max_N)] for __ in range(max_N)]


def dp(i1, i2, i3):
    if dp_calculated[i1][i2][i3]:
        return memo[i1][i2][i3]
    elif i1 < 0 or i2 < 0 or i3 < 0:
        return 0
    else:
        if i1 == 1 and i2 == 0 and i3 == 0:
            dp_calculated[i1][i2][i3] = True
            memo[i1][i2][i3] = N
            return memo[i1][i2][i3]
        else:
            memo[i1][i2][i3] = N / (i1 + i2 + i3)\
            + dp(i1, i2 + 1, i3 - 1) * (i3 / (i1 + i2 + i3))\
            + dp(i1 + 1, i2 - 1, i3) * (i2 / (i1 + i2 + i3))\
            + dp(i1 - 1, i2, i3) * (i1 / (i1 + i2 + i3))
            dp_calculated[i1][i2][i3] = True
            return memo[i1][i2][i3]


print(dp(start_plate[0], start_plate[1], start_plate[2]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

start_plate = [0] * 3
for n in range(N):
    start_plate[A[n] - 1] += 1

max_N = 301
dp_calculated = [[[False] * max_N for _ in range(max_N)] for __ in range(max_N)]
memo = [[[0] * max_N for _ in range(max_N)] for __ in range(max_N)]


def dp(i1, i2, i3):
    if dp_calculated[i1][i2][i3]:
        return memo[i1][i2][i3]
    else:
        if i1 == 1 and i2 == 0 and i3 == 0:
            dp_calculated[i1][i2][i3] = True
            memo[i1][i2][i3] = N
            return memo[i1][i2][i3]
        elif i1 < 0 or i2 < 0 or i3 < 0:
            return 0
        else:
            memo[i1][i2][i3] = N / (i1 + i2 + i3)\
            + dp(i1, i2 + 1, i3 - 1) * (i3 / (i1 + i2 + i3))\
            + dp(i1 + 1, i2 - 1, i3) * (i2 / (i1 + i2 + i3))\
            + dp(i1 - 1, i2, i3) * (i1 / (i1 + i2 + i3))
            dp_calculated[i1][i2][i3] = True
            return memo[i1][i2][i3]


print(dp(start_plate[0], start_plate[1], start_plate[2]))

Submission status: Runtime Error

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

start_plate = [0] * 3
for n in range(N):
    start_plate[A[n] - 1] += 1

max_N = 301
dp_calculated = [[[False] * max_N for _ in range(max_N)] for __ in range(max_N)]
memo = [[[0] * max_N for _ in range(max_N)] for __ in range(max_N)]


def dp(i1, i2, i3):
    if dp_calculated[i1][i2][i3]:
        return memo[i1][i2][i3]
    else:
        if i1 == 1 and i2 == 0 and i3 == 0:
            dp_calculated[i1][i2][i3] = True
            memo[i1][i2][i3] = N
            return memo[i1][i2][i3]
        elif i1 < 0 or i2 < 0 or i3 < 0:
            return 0
        else:
            memo[i1][i2][i3] = N / (i1 + i2 + i3)\
            + dp(i1, i2 + 1, i3 - 1) * (i3 / (i1 + i2 + i3))\
            + dp(i1 + 1, i2 - 1, i3) * (i2 / (i1 + i2 + i3))\
            + dp(i1 - 1, i2, i3) * (i1 / (i1 + i2 + i3))
            dp_calculated[i1][i2][i3] = True
            return memo[i1][i2][i3]


print(dp(start_plate[0], start_plate[1], start_plate[2]))

Submission status: Runtime Error

Solution code:
n = int(input())
sushi = [0] * 4
for a in map(int, input().split()):
  sushi[a] += 1
all_sushi = sushi[1] + sushi[2] * 2 + sushi[3] * 3
sushi_2_max = (all_sushi - sushi[1]) // 2
dp = [
  [[0] * (all_sushi + 1) for _ in range(sushi_2_max + 1)]
  for _ in range(sushi[3] + 1)]
dp_00 = dp[0][0]
for one in range(1, all_sushi + 1):
  dp_00 = (n + one * dp_00[one-1]) / one
dp_0 = dp[0]
for two in range(1, sushi_2_max + 1):
  dp_0[two][0] = (n + two * dp_0[two-1][1]) / two
  rest = all_sushi - two * 2
  for one in range(1, rest + 1):
    tmp = n + two * dp_0[two-1][one+1] + one * dp_0[two][one-1]
    dp_0[two][one] = tmp / (one + two)
for three in range(1, sushi[3] + 1):
  rest_one_two = all_sushi - three * 3
  for two in range((rest_one_two - sushi[1]) // 2 + 1):
    rest_one = rest_one_two - two * 2
    for one in range(rest_one + 1):
      tmp = n + three * dp[three-1][two+1][one]
      if two > 0:
        tmp += two * dp[three][two-1][one+1]
      if one > 0:
        tmp += one * dp[three][two][one-1]
      dp[three][two][one] =  tmp / (one + two + three)
print(dp[sushi[3]][sushi[2]][sushi[1]])

Submission status: Runtime Error

Solution code:
def main():
  	import sys
    input = sys.stdin.readline
    
    n = int(input())
    
    l1 = l2 = l3 = 0
    for i in map(int,input().split()):
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1

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

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

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

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

Submission status: Runtime Error

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

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

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

    dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1):
            for i in range(N+1):
                ijk = i + j + k
                if ijk > N:
                    continue
                x = N / ijk
                tmp = 0
                if i > 0:
                    tmp += (dp[i-1][j][k] + x) * (i / ijk)
                if j > 0 and i < N:
                    tmp += (dp[i+1][j-1][k] + x) * (j / ijk)
                if k > 0 and j < N:
                    tmp += (dp[i][j+1][k-1] + x) * (k / ijk)
                dp[i][j][k] = tmp
    print(dp[cnt[0]][cnt[1]][cnt[2]])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

ones , twos, threes = 0,0,0

for i in a:
  if i ==1:
    ones+=1
  elif i ==2:
    twos+=1
  else:
    threes+=1

max_ones = ones+twos+threes
max_twos = twos+threes
max_threes = threes
# dp[n][n][n]
dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]

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
        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: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    d = [[[0] * n for _ in range(n)] for _ in range(n)]
    def f(c1, c2, c3):
        if d[c1][c2][c3]: return d[c1][c2][c3]
        tmp = 1 / (1 - (n - c1 - c2 - c3)/n)
        if c1: tmp += f(c1 - 1, c2, c3) * c1 / n / (1 - (n - c1 - c2 - c3) / n)
        if c2: tmp += f(c1 + 1, c2 - 1, c3) * c2 / n / (1 - (n - c1 - c2 - c3) / n)
        if c3: tmp += f(c1, c2 + 1, c3 - 1) * c3 / n / (1 - (n - c1 - c2 - c3) / n)
        d[c1][c2][c3] = tmp
        return tmp
    c = LI()
    print(f(c.count(1), c.count(2), c.count(3)))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    d = [[[0] * n for _ in range(n)] for _ in range(n)]
    def f(c1, c2, c3):
        if d[c1][c2][c3]: return d[c1][c2][c3]
        tmp = 1 / (1 - (n - c1 - c2 - c3)/n)
        if c1: tmp += f(c1 - 1, c2, c3) * c1 / n / (1 - (n - c1 - c2 - c3) / n)
        if c2: tmp += f(c1 + 1, c2 - 1, c3) * c1 / n / (1 - (n - c1 - c2 - c3) / n)
        if c3: tmp += f(c1, c2 + 1, c3 - 1) * c1 / n / (1 - (n - c1 - c2 - c3) / n)
        d[c1][c2][c3] = tmp
        return tmp
    c = LI()
    print(f(c.count(1), c.count(2), c.count(3)))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[-1] * (301) for i in range(301)] for i in range(301)]

for a in range(n):
  for b in range(n):
    for c in range(n):
      result = n
      result += (dp[a-1][b][c] if a-1 >= 0 else 0)
      result += (dp[a+1][b-1][c] if b-1 >= 0 else 0)
      result += (dp[a][b+1][c-1] if c-1 >= 0 else 0)
      dp[a][b][c]=result / (a+b+c)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
# sys.setrecursionlimit(10**7)

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[-1] * (301) for i in range(301)] for i in range(301)]

for a in range(n):
  for b in range(n):
    for c in range(n):
      result = n
      result += dp[a-1][b][c] if a-1 >= 0 else 0
      result += dp[a+1][b-1][c] if b-1 >= 0 else 0
      result += dp[a][b+1][c-1] if c-1 >= 0 else 0
      dp[a][b][c]=result / (a+b+c)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[-1] * (301) for i in range(301)] for i in range(301)]

for a in range(n):
  for b in range(n):
    for c in range(n):
      result = n
      result += dp[a-1][b][c] if a-1 >= 0 else 0
      result += dp[a+1][b-1][c] if b-1 >= 0 else 0
      result += dp[a][b+1][c-1] if c-1 >= 0 else 0
      dp[a][b][c]=result / (a+b+c)

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

# def rec (a,b,c):
#   if not (a >= 0 and b >= 0 and c >= 0):
#     return 0
#   if a == b == c == 0:
#     return 0
#   if dp[a][b][c] != -1:
#     return dp[a][b][c]
#   result = n
#   result += rec(a-1,b,c) * a
#   result += rec(a+1,b-1,c) * b
#   result += rec(a,b+1,c-1) * c
#   dp[a][b][c] = result / (a+b+c)
#   return dp[a][b][c]

# print(rec(A,B,C))

Submission status: Runtime Error

Solution code:
import numpy as np

import sys
sys.setrecursionlimit(10**7)
n = int(input())

D = np.full((n+1, n+1, n+1, n+1), -1)
def dfs(a, b, c, d):
  if a == n:
    return 0
  if D[a, b, c, d] != -1:
    return D[a, b, c, d]
  rep = n
  if b != 0:
    rep += b * dfs(a+1, b-1, c, d)
  if c != 0:
    rep += c * dfs(a, b+1, c-1, d)
  if d != 0:
    rep += d * dfs(a, b, c+1, d-1)
  rep /= (n-a)
  D[a, b, c, d] = rep
  return rep

L = [0]*4
for a in map(int, input().split()):
  L[a] += 1
ans = dfs(*L)
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

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

@lru_cache(n**3)
def dfs(one,two,three):
    if one<0 or two<0 or three<0:
        return 0
    s = one+two+three
    if s == 0:
        return 0
    zero = n-s
    tmp = (one*dfs(one-1,two,three) + two*dfs(one+1, two-1, three) + three*dfs(one,two+1,three-1) + n)/(n - zero)
    return tmp

ans = dfs(one,two,three)
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

S = [0] * 3
for a in A:
  S[a-1] += 1

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

print(calc(*S))

Submission status: Runtime Error

Solution code:
k = int(input())
d = int(input())

li = list(map(int,(list(str(k)))))
leng = len(li)
mod = 10**9+7

dp1 = [0 for _ in range(d)]
dp2 = [0 for _ in range(d)]

mm1 = li[0]
for i in range(mm1):
    dp2[i%d] = 1

for i in range(1,leng):
    for j in range(0,10):
        for l in range(d):
            #既にk以下であることが確定
            dp1[(l+j)%d] = (dp1[(l+j)%d]+dp2[l])%mod

        #上からi桁目でk以下が確定
        if j<li[i]:
            dp1[(mm1+j)%d] = (dp1[(mm1+j)%d]+1)%mod
    #print(dp1,dp2)
    

    mm1 = (mm1+li[i])%d
    dp2 = [dp1[i] for i in range(d)]
    dp1 = [0 for _ in range(d)]


print((dp2[0]-1)%mod)

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
a = input().split()

c1 = a.count('1')
c2 = a.count('2')
c3 = a.count('3')

# dp =[ [[-1] * (n+1) for _ in range(n+1)] for __ in range(c3+1)]
# dp = np.full((c3+1, c2+c3+1, n+1), -1.0)
# dp[0][0][0] = 0

from functools import lru_cache
@lru_cache(maxsize=None)
def calc_dp(t3,t2,t1):
    # global dp
    # if(dp[t3][t2][t1] > -1):
    #     return dp[t3][t2][t1]
    if(t3+t2+t1==0):
        return 0

    temp = 0
    if(t3 > 0):
        temp += calc_dp(t3-1,t2+1,t1) * t3/(t1+t2+t3)
    if(t2 > 0):
        temp += calc_dp(t3,t2-1,t1+1) * t2/(t1+t2+t3)
    if(t1 > 0):
        temp += calc_dp(t3,t2,t1-1) * t1/(t1+t2+t3)
    temp = temp + n/(t1+t2+t3)

    # dp[t3][t2][t1] = temp
    return temp

print(calc_dp(c3,c2,c1))

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
a = input().split()

c1 = a.count('1')
c2 = a.count('2')
c3 = a.count('3')

# dp =[ [[-1] * (n+1) for _ in range(n+1)] for __ in range(c3+1)]
dp = np.full((c3+1, c2+c3+1, n+1), -1.0)
dp[0][0][0] = 0

from functools import lru_cache
@lru_cache(maxsize=None)
def calc_dp(t3,t2,t1):
    # global dp
    if(dp[t3][t2][t1] > -1):
        return dp[t3][t2][t1]

    temp = 0
    if(t3 > 0):
        temp += calc_dp(t3-1,t2+1,t1) * t3/(t1+t2+t3)
    if(t2 > 0):
        temp += calc_dp(t3,t2-1,t1+1) * t2/(t1+t2+t3)
    if(t1 > 0):
        temp += calc_dp(t3,t2,t1-1) * t1/(t1+t2+t3)
    temp = temp + n/(t1+t2+t3)

    # dp[t3][t2][t1] = temp
    return temp

print(calc_dp(c3,c2,c1))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter


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

    c = Counter(a)
    kitai = [[[0]*(c[1]+c[2]+c[3]+1) for _ in range(c[2]+c[3]+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(c[2]+c[3]+1):
            for i in range(c[1]+c[2]+c[3]+1):
                tot = i+j+k
                if tot == 0:
                    continue
                kitai[k][j][i] = 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] /= 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))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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<N:
                    dp[i][j][k] += (i/N)*dp[i-1][j+1][k]
                if j>0 and k<N:
                    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()

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10*9)


@lru_cache(maxsize=None)
def dp(x1, x2, x3):
    if x1 == x2 == x3 == 0:
        return 0
    eat1 = dp(x1-1, x2, x3)*(x1/N) if x1 > 0 else 0
    eat2 = dp(x1+1, x2-1, x3)*(x2/N) if x2 > 0 else 0
    eat3 = dp(x1, x2+1, x3-1)*(x3/N) if x3 > 0 else 0
    return (1 + eat1 + eat2 + eat3) * (N/(x1+x2+x3))


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

cnt = [0] * 4
for i in range(N):
    cnt[a[i]] += 1
print(dp(cnt[1], cnt[2], cnt[3]))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10*8)


@lru_cache(maxsize=None)
def dp(x1, x2, x3):
    if x1 == x2 == x3 == 0:
        return 0
    eat1 = dp(x1-1, x2, x3)*(x1/N) if x1 > 0 else 0
    eat2 = dp(x1+1, x2-1, x3)*(x2/N) if x2 > 0 else 0
    eat3 = dp(x1, x2+1, x3-1)*(x3/N) if x3 > 0 else 0
    return (1 + eat1 + eat2 + eat3) * (N/(x1+x2+x3))

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

cnt = [0] * 4
for i in range(N):
    cnt[a[i]] += 1
print(dp(cnt[1], cnt[2], cnt[3]))

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10*8)


@lru_cache(maxsize=None)
def dp(x1, x2, x3):
    if x1 == x2 == x3 == 0:
        return 0
    if x1 < 0 or x2 < 0 or x3 < 0:
        return 0
    return (1 + dp(x1-1, x2, x3)*(x1/N) + dp(x1+1, x2-1, x3)*(x2/N) + dp(x1, x2+1, x3-1)*(x3/N)) * (N/(x1+x2+x3))


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

cnt = [0] * 4
for i in range(N):
    cnt[a[i]] += 1
print(dp(cnt[1], cnt[2], cnt[3]))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
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
    print(dfs(d[1],d[2],d[3]))
@lru_cache(maxsize=None)
def dfs(a, b, c):
    if a + b + c == 0:
        return 0
    t1 = t2 = t3 = 0
    total = a + b + c
    if a > 0:
        t1 = (a/total) * dfs(a-1, b, c)
    if b > 0:
        t2 = (b/total) * dfs(a+1, b-1, c)
    if c > 0:
        t3 = (c/total) * dfs(a, b+1, c-1)
    return N/total + t1 + t2 + t3
main()

Submission status: Runtime Error

Solution code:
from collections import Counter
from functools import lru_cache

@lru_cache(maxsize=None)
def dp(N, c1, c2, c3):
    if c1 + c2 + c3 == 0:
        return 0
    r = N
    if c1:
        r += c1 * dp(N, c1 - 1, c2, c3)
    if c2:
        r += c2 * dp(N, c1 + 1, c2 - 1, c3)
    if c3:
        r += c3 * dp(N, c1, c2 + 1, c3 - 1)
    return r / (c1 + c2 + c3)

def main():
    N = int(input())
    a = list(map(int, input().split()))
    a = Counter(a)
    print(dp(N, a.get(1, 0), a.get(2, 0), a.get(3, 0)))


main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

from functools import lru_cache
from collections import Counter

@lru_cache(None)
def F(one,two,thr):
    if one==two==thr==0:
        return 0
    x = 1
    if one:
        x += one/N*F(one-1,two,thr)
    if two:
        x += two/N*F(one+1,two-1,thr)
    if thr:
        x += thr/N*F(one,two+1,thr-1)
    x *= N; x /= (one+two+thr)
    return x

counter = Counter(A)

answer = F(*[counter[n] for n in [1,2,3]])
print(answer)

Submission status: Runtime Error

Solution code:
import collections
from functools import lru_cache

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]

@lru_cache(maxsize=None)
def calc(i1, i2, i3):
  if i1 == i2 == i3 == 0:
    return 0

  ex = n/(i1+i2+i3)
  if i1 > 0:
    ex += calc(i1-1, i2, i3) * (i1/(i1+i2+i3))
  if i2 > 0:
    ex += calc(i1+1, i2-1, i3) * (i2/(i1+i2+i3))
  if i3 > 0:
    ex += calc(i1, i2+1, i3-1) * (i3/(i1+i2+i3))

  return ex

print(calc(n1, n2, n3))

Submission status: Runtime Error

Solution code:
import collections

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

# DPテーブルを初期化
dp = [[[None for k in range(310)] for j in range(310)] for i in range(310)]
dp[0][0][0] = 0.0

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

Submission status: Runtime Error

Solution code:
n,a=int(input()),list(map(int,input().split()));c=[0,0,0];x=[1.0/i for i in range(1,n+1)];dp=[[[-1]*(c[2]+2) for i in range(c[1]+c[2]+2)]for i in range(n+2)]
for i in a:c[i-1]+=1
for k in range(c[2]+1):
  for j in range(c[2]+c[1]-k+1):
    for i in range(n-k-j+1):
      if i+j+k>0:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]]+1)