Problem p03169 (python)

Fixed submission:
def main():
    import sys
    input = sys.stdin.readline

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

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

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


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.readline

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

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

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


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from functools import lru_cache
sys.setrecursionlimit(10*9)


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


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

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

Buggy submission (verdict: Runtime Error):
import sys
from functools import lru_cache
sys.setrecursionlimit(10*8)


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

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

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

Buggy submission (verdict: Runtime Error):
import sys
from functools import lru_cache
sys.setrecursionlimit(10*8)


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


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

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