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: Accepted

Solution code:
from collections import defaultdict
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# 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)/(i+j+k)
dp = [[[0]*(A+B+C+1-k-j) for j in range(B+C+1-k)] for k in range(C+1)]

t1 = None

for k in range(C+1):
  t0 = dp[k]
  for j in range(B+C+1-k):
    for i in range(A+B+C+1-k-j):
      try:
        dp[k][j][i] =((i*t0[j][i-1] if i else 0)+
                      (j*t0[j-1][i+1] if j else 0)+
                      (k*t1[j+1][i] if k else 0)+
                      N)/(i+j+k)
      except ZeroDivisionError:
        pass
  t1 = t0


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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# 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)/(i+j+k)
dp = [[[None]*(C+1) for _ in range(B+C+1)] for _ in range(A+B+C+1)]
dp[0][0][0] = 0

for k in range(C+1):
  for j in range(B+C+1-k):
    for i in range(A+B+C+1-k-j):
      try:
        dp[i][j][k] =((i*dp[i-1][j][k] if i else 0)+
                      (j*dp[i+1][j-1][k] if j else 0)+
                      (k*dp[i][j+1][k-1] if k else 0)+
                      N)/(i+j+k)
      except ZeroDivisionError:
        pass

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

Submission status: Accepted

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

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

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
one,two,three=SC

DAYSDICT=[[[0.0]*301 for j in range(301)] for k in range(301)]
DAYSDICT[0][0][0]=0
def days(one,two,three):
    ANS=N
    if one>0:
        ANS+=DAYSDICT[one-1][two][three]*one
    if two>0:
        ANS+=DAYSDICT[one+1][two-1][three]*two
    if three>0:
        ANS+=DAYSDICT[one][two+1][three-1]*three
        
    DAYSDICT[one][two][three]=ANS/(one+two+three)


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

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

Submission status: Runtime Error

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

@lru_cache(maxsize=10*7)
def exval(l, m, n):
    if -1 in [l, m, n]:
        return 0
    if (l, m, n) == (0, 0, 0):
        return 0
    return (l*exval(l-1, m+1, n) + m*exval(l, m-1, n+1) +
            n*exval(l, m, n-1) + N) / (l+m+n)


l, m, n = C[3], C[2], C[1]
print(exval(l, m, n))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))



@lru_cache(maxsize=None)
def f(c1, c2, c3):
    # if memo[c1][c2][c3] != -1:
    #     return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    # memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
# memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
# memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    if min(c1, c2, c3) < 0:
        return 0
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    p1 = c1 / N
    ret += f(c1-1, c2, c3) * p1 / ip0
    p2 = c2 / N
    ret += f(c1+1, c2-1, c3) * p2 / ip0
    p3 = c3 / N
    ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

from functools import lru_cache
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap



def slv(N, A):
    ca = Counter(A)
    s = [[ca[1], ca[2], ca[3]]]
    o = []
    while s:
        c1, c2, c3 = s.pop()
        o.append((c1, c2, c3))
        if c1 > 0:
            s.append((c1-1, c2, c3))
        if c2 > 0:
            s.append((c1+1, c2-1, c3))
        if c3 > 0:
            s.append((c1, c2+1, c3-1))

    memo = defaultdict(lambda: defaultdict(dict))
    memo[0][0][0] = 0
    o.pop()
    while o:
        c1, c2, c3 = o.pop()
        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        if c1 >0:
            ret += memo[c1-1][c2][c3] * p1 / ip0
        if c2 > 0:
            ret += memo[c1+1][c2-1][c3] * p2 / ip0
        if c3 > 0:
            ret += memo[c1][c2+1][c3-1] * p3 / ip0
        memo[c1][c2][c3] = ret


    return memo[ca[1]][ca[2]][ca[3]]

def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@lru_cache(maxsize=None)
def f(c1, c2, c3):
        if min(c1, c2, c3) < 0:
            return 0
        if c1 == c2 == c3 == 0:
            return 0

        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        ret += f(c1-1, c2, c3) * p1 / ip0
        ret += f(c1+1, c2-1, c3) * p2 / ip0
        ret += f(c1, c2+1, c3-1) * p3 / ip0
        return ret

@mt
def slv(N, A):
    ca = Counter(A)
    return f(ca[1], ca[2], ca[3])


N = read_int()
A = read_int_n()
print(slv(N, A))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap
    return d


@lru_cache(maxsize=None)
def f(c1, c2, c3):
        if min(c1, c2, c3) < 0:
            return 0
        if c1 == c2 == c3 == 0:
            return 0

        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        ret += f(c1-1, c2, c3) * p1 / ip0
        ret += f(c1+1, c2-1, c3) * p2 / ip0
        ret += f(c1, c2+1, c3-1) * p3 / ip0
        return ret

@mt
def slv(N, A):
    ca = Counter(A)
    return f(ca[1], ca[2], ca[3])



def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
from functools import lru_cache
MOD = 10 ** 9 + 7

def li():
    return [int(x) for x in input().split()]


N = int(input())
a = li()
I = a.count(1)
J = a.count(2)
K = a.count(3)

# dp[i][j][k]: 寿司が残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚ある状態から寿司を全てなくすのに必要な操作回数の期待値
# E(i,j,k) = E(i-1,j,k) * i / N + E(i+1,j-1,k) * j / N + E(i,j+1,k-1) * k / N + E(i,j,k) * (N-i-j-k) / N + 1
# E(i,j,k) = (E(i-1,j,k) * i + E(i+1,j-1,k) * j + E(i,j+1,k-1) * k + N) / (i+j+k)
dp = [[[-1] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
dp[0][0][0] = 0

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

@lru_cache()
def E(i, j, k):
    ret = 0
    if i > 0:
        ret += E(i-1, j, k) * i
    if j > 0:
        ret += E(i+1, j-1, k) * j
    if k > 0:
        ret += E(i, j+1, k-1) * k
    ret += N
    ret /= (i + j + k)
    return ret

print(E(I,J,K))

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1e9)+7)
stack_size(int(1e8))
 
def f(d):
    ans = 0
    try:
        return stored[(d[0],d[1],d[2])]
    except:
        pass
    ans = ans + n/(d[0]+d[1]+d[2]) + (d[2]/(d[0]+d[1]+d[2]))*x*f([d[0],d[1]+1,d[2]-1]) + (d[1]/(d[0]+d[1]+d[2]))*x*f([d[0]+1,d[1]-1,d[2]]) + (d[0]/(d[0]+d[1]+d[2]))*f([d[0]-1,d[1],d[2]])
    stored[(d[0],d[1],d[2])] = ans
    return ans
 
 
n = int(input())
a = list(map(int,input().split()))
d = [0 for i in range(3)]
stored = {(0,0,0):0}
 
for i in a:
    d[i-1] +=1
 
print(f(d))

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
ones,twos,threes=0,0,0
for i in l:
    if i==1:
        ones+=1
    elif i==2:
        twos+=2
    else:
        threes+=3
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)]
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:
N=int(input())
a=[int(i) for i in input().split()]
x,y,z=0
for i in a:
    if i==1:
        x+=1
    elif i==2:
        y+=1
    elif i==3:
        z+=1
n=x+y*2+z*3


dp=[[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=0
def calc(h,i,j):
    global n,N
    if h+i+j==0 or h<0 or h>n or i<0 or i>n or j<0:
        return 0
    if dp[h][i][j]!=-1:
        return dp[h][i][j]
    dp[h][i][j]=(calc(h-1,i,j)*h/N+calc(h+1,i-1,j)*i/N+calc(h,i+1,j-1)*j/N+1)*N/(h+i+j)
    return dp[h][i][j]

a=calc(x,y,z)
print(dp[x][y][z])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define reps(i, m, n) for (int i = m; i < n; i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

map<ll, double> memo;

double dp(int a, int b, int c, int n){
    if ((a == 0) && (b == 0) && (c == 0)) return 0.0;
    if ((a < 0) || (b < 0) || (c < 0)) return 0.0;
    if ((a > n) || (b > n) || (c > n)) return 0.0;
    ll judge = a*1000000+b*1000+c;
    if (memo[judge] != 0) return memo[judge];
    double res = n;
    res += a*dp(a-1, b, c, n);
    res += b*dp(a+1, b-1, c, n);
    res += c*dp(a, b+1, c-1, n);
    res /= a+b+c;
    memo[judge] = res;
    return res;
}

int main(void){
    int n;
    scanf("%d", &n);
    int a = 0;
    int b = 0;
    int c = 0;
    int sub;
    rep(i, n){
        scanf("%d", &sub);
        if (sub == 1) a++;
        if (sub == 2) b++;
        if (sub == 3) c++;
    }
    
    double ans;
    ans = dp(a, b, c, n);
    
    printf("%.11lf", ans);
    
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

N = int(input())

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

expv = np.array([[[-1.0] * (sushi_count[3]+1) for i in range(N-sushi_count[1]+1)] for i in range(N+1)])

expv[0][0][0] = 0.0

@njit
def get_expv(i, j, k):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(i-1, j, k) * (i / N)
    if j != 0:
        result += get_expv(i+1, j-1, k) * (j / N)
    if k != 0:
        result += get_expv(i, j+1, k-1) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

print(get_expv(sushi_count[1], sushi_count[2], sushi_count[3]))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
// #define int long long
#define Matrix vector<vector<int> >
// #define Matrix vector<vector<int> >
#define double long double
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define td(v) v.begin(),v.end()
#define tdr(v) v.rbegin(),v.rend()
#define endl "\n"
#define Matrix vector<vector<int> >
using namespace std;
const int MOD = 1e9+7;
const long long INF = 5e18;
const double pi = acos(-1.0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
 
inline long long mod(long long n, long long m){
    long long ret = n%m;
    if(ret < 0) ret += m;
    return ret;
}
 
double rad(double x){
    return x*pi/180.0;
}
 
bool isleft(pair<int,int> a, pair<int,int> b, pair<int,int> c){
    int det = (b.first-a.first)*(c.second-a.second) - (c.first-a.first)*(b.second-a.second);
    if(det>=0) return true;
    if(det<0) return false;
    return false;
}
 
int exp(int a, int b){
    int result = 1;
    while (b > 0){
        if (b & 1)
            result = mod(result*a,MOD);
 
        b >>= 1;
        a = mod(a*a,MOD);
    }
    return result;
}

double memo[321][321][321];
int vet[321];
int n;
double dp(int t, int d, int u){
	if(t+d+u==0) return 0;
	double &x = memo[t][d][u];
	if(x!=-1) return x;
	x = 0;
	if(t>0)
		x+=t*dp(t-1,d+1,u);
	if(d>0)
		x+=d*dp(t,d-1,u+1);
	if(u>0){
		x+=u*dp(t,d,u-1);
	}
	x/=(t+d+u)*1.0;
	x+=n*1.0/(t+d+u);
	return x;
}
void solve(){
	cin>>n;
	int q[4] = {0,0,0};
	for(int i=0;i<n;i++){
		cin>>vet[i];
		q[vet[i]]++;
	}
	for(int i=0;i<321;i++)
		for(int j=0;j<321;j++)
			for(int k=0;k<321;k++)
				memo[i][j][k]=-1;
	cout<<fixed<<setprecision(13);
	cout<<dp(q[3],q[2],q[1])<<endl;
}

signed main(){
    fastio;
    int t=1;
    // cin>>t;
    while(t--)
        solve();
}

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit


@njit('(f8[:,:,:],i4,i4,i4,i4,)', cache=True)
def solve(dp, N, n1, n2, n3):

    if dp[n1][n2][n3] >= 0.0:
        return dp[n1][n2][n3]
    if n1 == n2 == n3 == 0:
        return 0.0

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(dp, N, n1, n2 + 1, n3 - 1) * n3
    if n2 >= 1:
        ret += solve(dp, N, n1 + 1, n2 - 1, n3) * n2
    if n1 >= 1:
        ret += solve(dp, N, n1 - 1, n2, n3) * n1

    ret = (ret + N) / cnt
    dp[n1][n2][n3] = ret
    return ret


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

    dp = np.full((N + 1, N + 1, N + 1), -1, dtype=np.float64)

    a1, a2, a3 = 0, 0, 0
    for i in range(N):
        if A[i] == 1:
            a1 += 1
        elif A[i] == 2:
            a2 += 1
        elif A[i] == 3:
            a3 += 1

    print(solve(dp, N, a1, a2, a3))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from numba import njit
sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1 = A.count(1)
    n2 = A.count(2)
    n3 = A.count(3)

    dp = np.full((N + 1, N + 1, N + 1), -1, dtype=np.float64)
    dp[0][0][0] = 0

    print(solve(N, dp, n1, n2, n3))


@njit('(i4,f8[:,:,:],i4,i4,i4,)', cache=True)
def solve(N, dp, n1, n2, n3):

    if dp[n1][n2][n3] != -1:
        return dp[n1][n2][n3]

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(N, dp, n1, n2 + 1, n3 - 1) * n3 / cnt
    if n2 >= 1:
        ret += solve(N, dp, n1 + 1, n2 - 1, n3) * n2 / cnt
    if n1 >= 1:
        ret += solve(N, dp, n1 - 1, n2, n3) * n1 / cnt

    dp[n1][n2][n3] = ret + (N / cnt)
    return ret + (N / cnt)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache
n = int(input())
a = [int(i) for i in input().split(' ')]
z,o,tw,th = 0,0,0,0
for i in a:
    if i==0:
        z+=1
    elif i==1:
        o+=1
    elif i==2:
        tw+=1
    else:
        th+=1

def expectedValue(z,o,tw, th):
    if o+tw+th==0:
        return 0
    return (z+o+tw+th)/(o+th+tw)

@lru_cache(None)
def solve(z,o,tw,th):
    ans = expectedValue(z,o,tw,th)
    # print(z,o,tw,th, ans)
    if(o>0):
        ans +=  ((o)/(o+tw+th))* (solve(z+1,o-1,tw, th))
        # ans +=   solve(z+1,o-1,tw, th)
    if(tw>0):
        ans +=  ((tw)/(o+tw+th))* (solve(z,o+1,tw-1, th))
        # ans +=  solve(z,o+1,tw-1, th)
    if(th>0):
        ans +=  ((th)/(o+tw+th))* (solve(z,o,tw+1, th-1))
        # ans += solve(z,o ,tw+1, th-1)
    # print(z,o,tw,th,ans)
    return ans

print(solve(z,o,tw,th))

Submission status: Runtime Error

Solution code:
n=int(input())
arr=list(map(int,input().split()))
one=two=three=0
for i in arr:
    if i==1:
        one+=1
    elif i==2:
        two+=1
    elif i==3:
        three+=1
max_one=one+two+three
max_two=two+three
max_three=three
dp=[[[0.0]*(n+1) for i in range(n)] for j in range(n+1)]
for k in range(max_three+1):
    for j in range(max_two+1-k):
        for i in range(max_one+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:
import sys
import numpy as np
from numba import njit

@njit
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0:return dp[i][j][k]
    if all([i==0,j==0,k==0]):return 0.0
    res=0.0
    if i>0:res+=rec(N,dp,i-1,j,k)*i
    if j>0:res+=rec(N,dp,i+1,j-1,k)*j
    if k>0:res+=rec(N,dp,i,j+1,k-1)*k
    res+=N
    res*=1.0/(i+j+k)
    dp[i][j][k]=res
    return dp[i][j][k]
def main():
    N=int(sys.stdin.readline())
    a=tuple(map(int,sys.stdin.readline().split()))
    n1,n2,n3=a.count(1),a.count(2),a.count(3)
    dp=np.full((310,310,310),-1,dtype='float')
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

N = int(input())
a = list(map(int, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)
dp = [[[-1 for i in range(three + 10)] for j in range(two + 10)] for k in range(one + 10)]

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 /= i+j+k
    dp[i][j][k] = res
    return res

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

Submission status: Runtime Error

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:
        []

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

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

Solution code:
from collections import Counter as C
from functools import lru_cache
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=10000)
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: Runtime Error

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
st = time.time()
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]))
#print(time.time()-st)

Submission status: Runtime Error

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] * (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
            dp[i][j][k] += n
            if i - 1 >= 0:
                dp[i][j][k] += i * dp[i - 1][j][k]
            if j - 1 >= 0:
                dp[i][j][k] += j * dp[i + 1][j - 1][k]
            if k - 1 >= 0:
                dp[i][j][k] += k * dp[i][j + 1][k - 1]
            dp[i][j][k] /= i + j + k
print(dp[num1 - num2][num2 - num3][num3])

Submission status: Runtime Error

Solution code:
N=int(input())
C = Counter(map(int, input().split()))
dp = [[[.0] * (N + 2) for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(C[3] + 1):
    for j in range(N - C[1] - i + 1):
        for k in range(N - i - j + 1):
            if i + j + k != 0:
                dp[i][j][k] = (
                    N +
                    i * dp[i - 1][j + 1][k] +
                    j * dp[i][j - 1][k + 1] +
                    k * dp[i][j][k - 1]
                ) / (i + j + k)
print(dp[C[3]][C[2]][C[1]])

Submission status: Runtime Error

Solution code:
N=int(input())
C = Counter(map(int, input().split()))
dp = [[[.0] * (N + 2) for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(C[3] + 1):
    for j in range(N - C[1] - i + 1):
        for k in range(N - i - j + 1):
            if i + j + k != 0:
                dp[i][j][k] = (
                    N +
                    i * dp[i - 1][j + 1][k] +
                    j * dp[i][j - 1][k + 1] +
                    k * dp[i][j][k - 1]
                ) / (i + j + k)
                print(dp)
                print(' ')
print(dp[C[3]][C[2]][C[1]])

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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


def main():
    global N
    N = int(input())
    a = map(int, input().split())
    single = double = triple = 0
    for sushi in a:
        if sushi == 1:
            single += 1
        elif sushi == 2:
            double += 1
        elif sushi == 3:
            triple += 1
    print(rec(single, double, triple))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


@lru_cache
def rec(i, j):
    global p
    if i < 0 or j < 0:
        return 0.0
    return rec(i - 1, j) * (1 - p[i - 1]) + \
        rec(i - 1, j - 1) * p[i - 1]


def main():
    N = int(input())
    global p
    p = list(map(float, input().split()))
    ans = 0
    for i in range(N//2+1, N+1):
        ans += rec(N, i)


if __name__ == "__main__":
    main()