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:
from collections import Counter
import sys
input = sys.stdin.buffer.readline
from itertools import product

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dic = {}
    for p in product(range(n+1),repeat=3):
        dic['{}-{}-{}'.format(*p)] = .0
    n = float(n)
    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        key = '{}-{}-{}'.format(i,j,k)
        if key in dic and dic[key] > 0:
            return dic[key]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dic[key] = ans
        return ans

    ans = exp(a[1],a[2],a[3])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    n = float(n)
    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        if dp[i][j][k]:
            return dp[i][j][k]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dp[i][j][k] = ans
        return ans

    ans = exp(a[1],a[2],a[3])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

NB = 300 + 3 + 1


def solve(values, nb):
    count = [0] * 4
    for v in values:
        count[v] += 1
    # ev[a][b][c] expected value of operations to reach a plates with 1 sushi, b with 2 and a with 3
    ev = [[[0] * NB for _ in range(NB)] for _ in range(NB)]
    # p[a][b][c] expected value of operations to reach a plates with 1 sushi, b with 2 and a with 3
    p = [[[0] * NB for _ in range(NB)] for _ in range(NB)]
    p[count[1]][count[2]][count[3]] = 1
    for c in range(count[3] + 1, -1, -1):
        for b in range(count[3] + count[2] + 1, -1, -1):
            for a in range(nb + 1, -1, -1):
                if a + b + c == 0 or a + b + c > nb:
                    continue
                p_waste = (nb - (a + b + c)) / nb
                ev_waste = p_waste / (1 - p_waste)
                ev[a][b][c] += ev_waste * p[a][b][c]
                # LOG.debug((a, b, c, p_waste, ev_waste, ev[a][b][c], p[a][b][c]))

                if a != 0:
                    # take from 1
                    p_go = a / (a + b + c)
                    p[a - 1][b][c] += p[a][b][c] * p_go
                    ev[a - 1][b][c] += ev[a][b][c] * p_go
                if b != 0:
                    # take from 2
                    p_go = b / (a + b + c)
                    p[a + 1][b - 1][c] += p[a][b][c] * p_go
                    ev[a + 1][b - 1][c] += ev[a][b][c] * p_go
                if c != 0:
                    # take from 3
                    p_go = c / (a + b + c)
                    p[a][b + 1][c - 1] += p[a][b][c] * p_go
                    ev[a][b + 1][c - 1] += ev[a][b][c] * p_go
    return ev[0][0][0] + count[1] + 2 * count[2] + 3 * count[3]


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = list(map(int, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(values, N)
    print("%.10f" % result)


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy

NB = 300 + 3 + 1


def solve(values, nb):
    count = [0] * 4
    for v in values:
        count[v] += 1
    # ev[a][b][c] expected value of operations to reach a plates with 1 sushi, b with 2 and a with 3
    ev = [[[0] * NB for _ in range(NB)] for _ in range(NB)]
    # p[a][b][c] expected value of operations to reach a plates with 1 sushi, b with 2 and a with 3
    p = [[[0] * NB for _ in range(NB)] for _ in range(NB)]
    p[count[1]][count[2]][count[3]] = 1
    for c in range(nb + 1, -1, -1):
        for b in range(nb + 1, -1, -1):
            for a in range(nb + 1, -1, -1):
                if a + b + c == 0 or a + b + c > nb:
                    continue
                p_waste = (nb - (a + b + c)) / nb
                ev_waste = p_waste / (1 - p_waste)
                ev[a][b][c] += ev_waste * p[a][b][c]
                # LOG.debug((a, b, c, p_waste, ev_waste, ev[a][b][c], p[a][b][c]))

                if a != 0:
                    # take from 1
                    p_go = a / (a + b + c)
                    p[a - 1][b][c] += p[a][b][c] * p_go
                    ev[a - 1][b][c] += ev[a][b][c] * p_go
                if b != 0:
                    # take from 2
                    p_go = b / (a + b + c)
                    p[a + 1][b - 1][c] += p[a][b][c] * p_go
                    ev[a + 1][b - 1][c] += ev[a][b][c] * p_go
                if c != 0:
                    # take from 3
                    p_go = c / (a + b + c)
                    p[a][b + 1][c - 1] += p[a][b][c] * p_go
                    ev[a][b + 1][c - 1] += ev[a][b][c] * p_go
    return ev[0][0][0] + count[1] + 2 * count[2] + 3 * count[3]


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = list(map(int, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(values, N)
    print("%.10f" % result)


def configure_log():
    "Configure the log output"
    log_formatter = logging.Formatter("L%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Time Limit Exceeded

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(c+1):
        for j in range(b+c + 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: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0, a.count(1), a.count(2), 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[1]][A[2]][A[3]])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0, a.count(1), a.count(2), 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[1]][A[2]][A[3]])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = n
                    if i > 0:
                        tmp += i * dp[i-1][j][k]
                    if j > 0:
                        tmp += j * dp[i+1][j-1][k]
                    if k > 0:
                        tmp += k * dp[i][j+1][k-1]
                    dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0, a.count(1), a.count(2), a.count(3)]

    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(A[1]+A[2]+A[3] + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = N * 1.0
                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[1]][A[2]][A[3]])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0, a.count(1), a.count(2), a.count(3)]

    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(A[1]+A[2]+A[3] + 1 - k - j):
                if i + j+k == 0:
                    continue
                P = N * 1.0
                if i > 0:
                    P += dp[i-1][j][k] * i
                if j > 0:
                    P += dp[i+1][j-1][k] * j
                if k > 0:
                    P += dp[i][j+1][k-1] * k
                dp[i][j][k] = P / (i+j+k)

    print(dp[A[1]][A[2]][A[3]])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    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(A[1]+A[2]+A[3] + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = N
                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[1]][A[2]][A[3]])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    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(A[1]+A[2]+A[3] + 1 - k - j):
                if i + j+k == 0:
                    continue
                P = N
                if i > 0:
                    P += dp[i-1][j][k] * i
                if j > 0:
                    P += dp[i+1][j-1][k] * j
                if k > 0:
                    P += dp[i][j+1][k-1] * k
                dp[i][j][k] = P/(i+j+k)

    print(dp[A[1]][A[2]][A[3]])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    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(A[1]+A[2]+A[3] + 1 - k - j):
                if i + j+k == 0:
                    continue
                P = N
                if i > 0:
                    P += dp[i-1][j][k] * i
                if j > 0:
                    P += dp[i+1][j-1][k] * j
                if k > 0:
                    P += dp[i][j+1][k-1] * k
                dp[i][j][k] = P/(i+j+k)

    print(dp[A[1]][A[2]][A[3]])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    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(A[1]+A[2]+A[3] + 1 - k - j):
                if i == 0 and j == 0 and k == 0:
                    continue
                P = N
                if i > 0:
                    P += dp[i-1][j][k] * i
                if j > 0:
                    P += dp[i+1][j-1][k] * j
                if k > 0:
                    P += dp[i][j+1][k-1] * k
                dp[i][j][k] = P/(i+j+k)

    print(dp[A[1]][A[2]][A[3]])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

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

    # def solve(c1, c2, c3):
    #     if dp[c1][c2][c3] >= 0:
    #         return(dp[c1][c2][c3])
    #     else:
    #         P = 1
    #         if c1 > 0:
    #             P += solve(c1-1, c2, c3) * (c1/N)
    #         if c2 > 0:
    #             P += solve(c1+1, c2-1, c3)*(c2/N)
    #         if c3 > 0:
    #             P += solve(c1, c2+1, c3-1)*(c3/N)
    #         P /= (1 - (N-c1-c2-c3)/N)
    #         dp[c1][c2][c3] = P

    #         return(P)

    # print(solve(A[1], A[2], A[3]))

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

    print(dp[A[1]][A[2]][A[3]])


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    dp = [[[-1]*(N+1) for i in range(N+1)] for j in range(N+1)]
    # for i in range(1, L+1):
    dp[0][0][0] = 0

    def solve(c1, c2, c3):
        if dp[c1][c2][c3] >= 0:
            return(dp[c1][c2][c3])
        else:
            P = 1
            if c1 > 0:
                P += solve(c1-1, c2, c3) * (c1/N)
            if c2 > 0:
                P += solve(c1+1, c2-1, c3)*(c2/N)
            if c3 > 0:
                P += solve(c1, c2+1, c3-1)*(c3/N)
            P /= (1 - (N-c1-c2-c3)/N)
            dp[c1][c2][c3] = P

            return(P)

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


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import collections
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    a = list(map(int, input().split()))
    A = collections.Counter(a)
    dp = [[[-1]*(N+1) for i in range(N+1)] for j in range(N+1)]
    # for i in range(1, L+1):

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

    def solve(c1, c2, c3):
        if dp[c1][c2][c3] >= 0:
            return(dp[c1][c2][c3])
        else:
            P = 1
            if c1 > 0:
                P += solve(c1-1, c2, c3) * (c1/N)
            if c2 > 0:
                P += solve(c1+1, c2-1, c3)*(c2/N)
            if c3 > 0:
                P += solve(c1, c2+1, c3-1)*(c3/N)
            P /= (1 - (N-c1-c2-c3)/N)
            dp[c1][c2][c3] = P

            return(P)

    print(solve(A[1], A[2], A[3]))
main()

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
sys.setrecursionlimit(10**5)
N = int(input())
a = list(map(int, input().split()))
A = collections.Counter(a)

L = sum(a) + 1
dp = [[[-1]*(N+1) for i in range(N+1)] for j in range(N+1)]
# for i in range(1, L+1):

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


def solve(c1, c2, c3):
    if dp[c1][c2][c3] >= 0:
        return(dp[c1][c2][c3])
    else:
        P = 1
        if c1 > 0:
            P += solve(c1-1, c2, c3) * (c1/N)
        if c2 > 0:
            P += solve(c1+1, c2-1, c3)*(c2/N)
        if c3 > 0:
            P += solve(c1, c2+1, c3-1)*(c3/N)
        P /= (1 - (N-c1-c2-c3)/N)
        dp[c1][c2][c3] = P

        return(P)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dic = {}

    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        key = '{}-{}-{}'.format(i,j,k)
        if key in dic:
            return dic[key]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dic[key] = ans
        return ans

    ans = exp(a[1],a[2],a[3])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[''] * (310) for _ in range(310)] for _ in range(310)]
    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        if dp[i][j][k]:
            return dp[i][j][k]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dp[i][j][k] = ans
        return ans

    ans = exp(a[1],a[2],a[3])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[[''] * (310) for _ in range(310)] for _ in range(310)]
    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        if dp[i][j][k]:
            return dp[i][j][k]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dp[i][j][k] = ans
        return ans

    ans = exp(a.count(1),a.count(2),a.count(3))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}

    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        key = '{}-{}-{}'.format(i,j,k)
        if key in dic:
            return dic[key]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dic[key] = ans
        return ans

    ans = exp(a.count(1),a.count(2),a.count(3))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}

    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        key = '{}-{}-{}'.format(i,j,k)
        if key in dic:
            return dic[key]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        return ans

    ans = exp(a.count(1),a.count(2),a.count(3))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

from sys import setrecursionlimit
setrecursionlimit(300 ** 3 + 10)


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

memo = {(0, 0, 0): 0.0}
def dp(i, j, k):
    if (i, j, k) in memo:
        return memo[(i, j, k)]

    res = N
    if i > 0:
        res += i * dp(i - 1, j, k)
    if j > 0:
        res += j * dp(i + 1, j - 1, k)
    if k > 0:
        res += k * dp(i, j + 1, k - 1)

    res /= (i + j + k)

    memo[(i, j, k)] = res

    return res

C = Counter(A)
print(dp(C[1], C[2], C[3]))

Submission status: Time Limit Exceeded

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
        np.asmatrix(matr)

        dp[l][m][:mk] = np.dot(dp[l][m][:mk], matr)
print(dp[S[1]][S[2]][S[3]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read():
    N = int(input().strip())
    A = map(int, input().strip().split())
    return N, A


def dfs(i, j, k, N, dp):
    if any([i < 0, j < 0, k < 0, i + j + k > N]):
        return 0.0
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    x = 0.0
    x += dfs(i-1, j, k, N, dp) * (i / N)
    x += dfs(i+1, j-1, k, N, dp) * (j / N)
    x += dfs(i, j+1, k-1, N, dp) * (k / N)
    x += 1.0
    x *= N / (i + j + k)
    dp[i][j][k] = x
    return dp[i][j][k]


def solve(N, A):
    dp = [[[-1.0 for k in range(N + 2)] for j in range(N + 2)] for i in range(N + 2)]
    C = [0 for i in range(4)]
    for a in A:
        C[a] += 1
    dp[0][0][0] = 0.0
    return dfs(C[1], C[2], C[3], N, dp)


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import Counter
def dfs(i,j,k):
    global N
    if i==0 and j==0 and k==0:
        return 0
    if dp[i][j][k]>=0:
        return dp[i][j][k]
    else:
        res=N
        if(i>0):
            res+=dfs(i-1,j,k)*i
        if(j>0):
            res+=dfs(i+1,j-1,k)*j
        if(k>0):
            res+=dfs(i,j+1,k-1)*k
        res*=1/(i+j+k)
        dp[i][j][k]=res
        return res
dp=[[[-1]*301 for i in range(301)] for i in range(301)]
N=int(input())
a=list(map(int,input().split()))
c=Counter(a)
i,j,k=c[1],c[2],c[3]
print(dfs(i,j,k))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(a+b+c-k-j+1):
            if i+j+k == 0:
                continue
            DP[i][j][k] = n
            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])