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()))
dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
c1, c2, c3 = map(a.count, [1,2,3])
dp[c1][c2][c3] = 1
q = [(c1, c2, c3)]
ans = 0
for _ in range(c1 + c2*2 + c3*3):
    nxt = set()
    for c1, c2, c3 in q:
        c = c1 + c2 + c3
        p = dp[c1][c2][c3]
        ans += p * n / c
        if c1 > 0:
            dp[c1-1][c2][c3] += p * c1 / c
            nxt.add((c1-1,c2,c3))
        if c2 > 0:
            dp[c1+1][c2-1][c3] += p * c2 / c
            nxt.add((c1+1,c2-1,c3))
        if c3 > 0:
            dp[c1][c2+1][c3-1] += p * c3 / c
            nxt.add((c1,c2+1,c3-1))
    q = list(nxt)
print(ans)

Submission status: Time Limit Exceeded

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

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

cnt = {1:0, 2:0, 3:0}
for a in a_list:
    cnt[a] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0.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=(res+N)*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=[[[-1.0 for _ in range(n3+1)] for _ in range(n2+n3+1)] for _ in range(n1+n2+n3+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0.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=(res+N)/(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=[[[-1.0 for _ in range(n3+1)] for _ in range(n2+n3+1)] for _ in range(n1+n2+n3+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def rec(N,dp,n1,n2,n3):
    if dp[n3][n2][n1]>=0.0:return dp[n3][n2][n1]
    if all([n1==0,n2==0,n3==0]):return 0.0
    res=0.0
    if n1>0:res+=rec(N,dp,n1-1,n2,n3)*n1
    if n2>0:res+=rec(N,dp,n1+1,n2-1,n3)*n2
    if n3>0:res+=rec(N,dp,n1,n2+1,n3-1)*n3
    res+=N
    res*=1.0/(n1+n2+n3)
    dp[n3][n2][n1]=res
    return dp[n3][n2][n1]
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=[[[-1.0 for _ in range(n1+n2+n3+1)] for _ in range(n2+n3+1)] for _ in range(n3+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0.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=[[[-1.0 for _ in range(n3+1)] for _ in range(n2+n3+1)] for _ in range(n1+n2+n3+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def rec(N,dp,i,j,k):
    if dp[i][j][k]>=0.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=[[[-1.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
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=[[[-1.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
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((N+1,N+1,N+1),-1,dtype=float)
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
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=[[[-1 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
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=[[[-1 for _ in range(310)] for _ in range(310)] for _ in range(310)]
    print(rec(N,dp,n1,n2,n3))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
from collections import Counter
def input(): return sys.stdin.readline().strip()

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

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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
from collections import Counter

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

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: Time Limit Exceeded

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 + 1)] for j in range(N+1)] for k in range(N+1)]

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: Time Limit Exceeded

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(N+1)] for j in range(N+1)] for k in range(N+1)]

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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, AS):
    from collections import Counter
    count = Counter(AS)
    expect = [[[-1] * (N + 1) for i in range(N + 1)] for j in range(N + 1)]
    expect[0][0][0] = 0

    def f(a, b, c):
        p = N
        if a > 0:
            if expect[a - 1][b][c] == -1:
                v = f(a - 1, b, c)
            else:
                v = expect[a - 1][b][c]
            p += v * a
        if b > 0:
            if expect[a + 1][b - 1][c] == -1:
                v = f(a + 1, b - 1, c)
            else:
                v = expect[a + 1][b - 1][c]

            p += f(a + 1, b - 1, c) * b
        if c > 0:
            if expect[a][b + 1][c - 1] == -1:
                v = f(a, b + 1, c - 1)
            else:
                v = expect[a][b + 1][c - 1]

            p += f(a, b + 1, c - 1) * c
        p /= (a + b + c)

        # debug("f: a,b,c,p", a, b, c, p)
        expect[a][b][c] = p
        return p

    return f(count[1], count[2], count[3])


def main():
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


T1 = """
3
1 1 1
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5.5
    """


T2 = """
1
3
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    3.0
    """


T3 = """
2
1 2
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    4.5
    """


# T4 = """
# 10
# 1 3 2 3 3 2 3 2 1 3
# """


# def test_T4():
#     """
#     >>> as_input(T4)
#     >>> N = int(input())
#     >>> AS = list(map(int, input().split()))
#     >>> abs(solve(N, AS) - 54.48064457488221)  < 10 ** -9
#     """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, AS):
    "void()"
    from collections import Counter
    count = Counter(AS)
    expect = [[[-1] * (N + 1) for i in range(N + 1)] for j in range(N + 1)]
    expect[0][0][0] = 0

    def f(a, b, c):
        p = N
        if a > 0:
            if expect[a - 1][b][c] == -1:
                v = f(a - 1, b, c)
            else:
                v = expect[a - 1][b][c]
            p += v * a
        if b > 0:
            if expect[a + 1][b - 1][c] == -1:
                v = f(a + 1, b - 1, c)
            else:
                v = expect[a + 1][b - 1][c]

            p += f(a + 1, b - 1, c) * b
        if c > 0:
            if expect[a][b + 1][c - 1] == -1:
                v = f(a, b + 1, c - 1)
            else:
                v = expect[a][b + 1][c - 1]

            p += f(a, b + 1, c - 1) * c
        p /= (a + b + c)

        # debug("f: a,b,c,p", a, b, c, p)
        expect[a][b][c] = p
        return p

    return f(count[1], count[2], count[3])


def main():
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


T1 = """
3
1 1 1
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5.5
    """


T2 = """
1
3
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    3.0
    """


T3 = """
2
1 2
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    4.5
    """


# T4 = """
# 10
# 1 3 2 3 3 2 3 2 1 3
# """


# def test_T4():
#     """
#     >>> as_input(T4)
#     >>> N = int(input())
#     >>> AS = list(map(int, input().split()))
#     >>> abs(solve(N, AS) - 54.48064457488221)  < 10 ** -9
#     """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, AS):
    "void()"
    from collections import Counter
    count = Counter(AS)
    expect = [[[-1] * (N + 1) for i in range(N + 1)] for j in range(N + 1)]
    expect[0][0][0] = 0

    def f(a, b, c):
        p = 1.0
        if a > 0:
            if expect[a - 1][b][c] == -1:
                v = f(a - 1, b, c)
            else:
                v = expect[a - 1][b][c]
            p += v * a / N
        if b > 0:
            if expect[a + 1][b - 1][c] == -1:
                v = f(a + 1, b - 1, c)
            else:
                v = expect[a + 1][b - 1][c]

            p += f(a + 1, b - 1, c) * b / N
        if c > 0:
            if expect[a][b + 1][c - 1] == -1:
                v = f(a, b + 1, c - 1)
            else:
                v = expect[a][b + 1][c - 1]

            p += f(a, b + 1, c - 1) * c / N
        p *= N / (a + b + c)

        # debug("f: a,b,c,p", a, b, c, p)
        expect[a][b][c] = p
        return p

    return f(count[1], count[2], count[3])


def main():
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


T1 = """
3
1 1 1
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5.5
    """


T2 = """
1
3
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    3.0
    """


T3 = """
2
1 2
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    4.5
    """


# T4 = """
# 10
# 1 3 2 3 3 2 3 2 1 3
# """


# def test_T4():
#     """
#     >>> as_input(T4)
#     >>> N = int(input())
#     >>> AS = list(map(int, input().split()))
#     >>> abs(solve(N, AS) - 54.48064457488221)  < 10 ** -9
#     """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


# def solve(N, AS):
#     "void()"
#     from collections import Counter
#     count = Counter(AS)
#     expect = [[[-1] * N for i in range(N)] for j in range(N)]
#     expect[0][0][0] = 0

#     def f(a, b, c):
#         v =
#         if (a, b, c) in expect:
#             return expect[a][b][c]
#         p = 1.0
#         if a > 0:
#             p += f(a - 1, b, c) * a / N
#         if b > 0:
#             p += f(a + 1, b - 1, c) * b / N
#         if c > 0:
#             p += f(a, b + 1, c - 1) * c / N
#         p *= N / (a + b + c)

#         # debug("f: a,b,c,p", a, b, c, p)
#         expect[(a, b, c)] = p
#         return p

#     return f(count[1], count[2], count[3])

def solve(N, AS):
    "void()"
    from collections import Counter
    count = Counter(AS)
    expect = {}
    expect[(0, 0, 0)] = 0

    def f(a, b, c):
        p = 1.0
        if a > 0:
            if (a - 1, b, c) not in expect:
                v = f(a - 1, b, c)
            else:
                v = expect[(a - 1, b, c)]
            p += v * a / N
        if b > 0:
            if (a + 1, b - 1, c) not in expect:
                v = f(a + 1, b - 1, c)
            else:
                v = expect[(a + 1, b - 1, c)]

            p += f(a + 1, b - 1, c) * b / N
        if c > 0:
            if (a, b + 1, c - 1) not in expect:
                v = f(a, b + 1, c - 1)
            else:
                v = expect[(a, b + 1, c - 1)]

            p += f(a, b + 1, c - 1) * c / N
        p *= N / (a + b + c)

        # debug("f: a,b,c,p", a, b, c, p)
        expect[(a, b, c)] = p
        return p

    return f(count[1], count[2], count[3])


def main():
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


T1 = """
3
1 1 1
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5.5
    """


T2 = """
1
3
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    3.0
    """


T3 = """
2
1 2
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    4.5
    """


# T4 = """
# 10
# 1 3 2 3 3 2 3 2 1 3
# """


# def test_T4():
#     """
#     >>> as_input(T4)
#     >>> N = int(input())
#     >>> AS = list(map(int, input().split()))
#     >>> abs(solve(N, AS) - 54.48064457488221)  < 10 ** -9
#     """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x)


def solve(N, AS):
    "void()"
    from collections import Counter
    count = Counter(AS)
    expect = {}
    expect[(0, 0, 0)] = 0

    def f(a, b, c):
        if (a, b, c) in expect:
            return expect[(a, b, c)]
        p = 1.0
        if a > 0:
            p += f(a - 1, b, c) * a / N
        if b > 0:
            p += f(a + 1, b - 1, c) * b / N
        if c > 0:
            p += f(a, b + 1, c - 1) * c / N
        p *= N / (a + b + c)

        # debug("f: a,b,c,p", a, b, c, p)
        expect[(a, b, c)] = p
        return p

    return f(count[1], count[2], count[3])


def main():
    N = int(input())
    AS = list(map(int, input().split()))
    print(solve(N, AS))


T1 = """
3
1 1 1
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5.5
    """


T2 = """
1
3
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    3.0
    """


T3 = """
2
1 2
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    4.5
    """


# T4 = """
# 10
# 1 3 2 3 3 2 3 2 1 3
# """


# def test_T4():
#     """
#     >>> as_input(T4)
#     >>> N = int(input())
#     >>> AS = list(map(int, input().split()))
#     >>> abs(solve(N, AS) - 54.48064457488221)  < 10 ** -9
#     """


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
sys.setrecursionlimit(10000)

N = int(input())
a = list(map(int, input().split()))
dp = [[[-1 for i in range(310)] for j in range(310)] for k 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

c = Counter(a)
one, two, three = c[1], c[2], c[3]
print(rec(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(n1+n2+n3+1, n2+n3+1, n3+1)
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])]

count = 0
S = sum(a)
sub = glist(n1+n2+n3+1,n2+n3+1,n3+1)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(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
            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, 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)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(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
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])