Problem p03169 (python)

Fixed submission:
def main():
    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
    dp = [[[0 for i in range(1+single+double+triple-j-k)]
           for j in range(double + triple + 1 - k)] for k in range(triple + 1)]
    for k in range(triple+1):
        for j in range(double + triple + 1-k):
            for i in range(1+single+double+triple-j-k):
                if i == 0 and j == 0 and k == 0:
                    continue
                first = second = third = 0
                if i-1 >= 0 and j >= 0 and k >= 0:
                    first = dp[k][j][i-1]
                if i+1 >= 0 and j-1 >= 0 and k >= 0:
                    second = dp[k][j - 1][i+1]
                if i >= 0 and j+1 >= 0 and k-1 >= 0:
                    third = dp[k-1][j + 1][i]
                dp[k][j][i] = (first*i + second * j +
                               third * k + N) / (i + j + k)
    print(dp[triple][double][single])


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
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()

Buggy submission (verdict: Runtime Error):
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()

Buggy submission (verdict: Runtime Error):
import numpy as np


def main():
    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
    dp = np.zeros((single + 3, double + 3, triple + 3))
    for k in range(triple+2):
        for j in range(double+2):
            for i in range(single + 2):
                if i == 0 and j == 0 and k == 0:
                    continue
                first = second = third = 0
                if i-1 >= 0 and j >= 0 and k >= 0:
                    first = dp[i - 1][j][k]
                if i+1 >= 0 and j-1 >= 0 and k >= 0:
                    second = dp[i + 1][j - 1][k]
                if i >= 0 and j+1 >= 0 and k-1 >= 0:
                    third = dp[i][j + 1][k - 1]
                dp[i][j][k] = (first*i + second * j +
                               third * k + N) / (i + j + k)
    print(dp[single][double][triple])


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import numpy as np


def main():
    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
    dp = np.zeros((single + 3, double + 3, triple + 3))
    for k in range(triple+2):
        for j in range(double+2):
            for i in range(single + 2):
                if i == 0 and j == 0 and k == 0:
                    continue
                print(i, j, k)
                first = second = third = 0
                if i-1 >= 0 and j >= 0 and k >= 0:
                    first = dp[i - 1][j][k]
                if i+1 >= 0 and j-1 >= 0 and k >= 0:
                    second = dp[i + 1][j - 1][k]
                if i >= 0 and j+1 >= 0 and k-1 >= 0:
                    third = dp[i][j + 1][k - 1]
                dp[i][j][k] = (first*i + second * j +
                               third * k + N) / (i + j + k)
    print(dp[single][double][triple])


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import random


def main():
    N = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for _ in range(10**4):
        tmp = a.copy()
        all = list(range(N))
        not_aten = set(all)
        while not_aten:
            x = random.choice(all)
            tmp[x] -= 1
            if tmp[x] == 0:
                not_aten.remove(x)
            ans += 1
    print(ans/10**4)


if __name__ == "__main__":
    main()