Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02852 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, S: str):

    S = S[::-1]
    data = [0]*(N+1)
    past = 0
    for i in range(N+1):
        if S[i] == "1":
            data[i] = past
        else:
            past = i
    ans = []
    curr = 0
    while True:
        ne = curr+M
        if ne >= N:
            ans.append(N-curr)
            break
        if S[ne] == "1":
            ne = data[ne]
            if ne <= curr:
                print(-1)
                return
        ans.append(ne - curr)
        curr = ne
    print(*reversed(ans), sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, M, S)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, S: str):

    # 最短手数を求める
    DP = [INF]*(N+1)
    DP[0] = 0
    for i in range(1, N+1):
        if S[i] == "1":
            continue
        for j in range(1, M+1):
            if i-j < 0:
                break
            DP[i] = min(DP[i], DP[i-j]+1)

    if DP[-1] == INF:
        print(-1)
        return
    # 逆順に辿って実際の手を求める
    # 辞書順になるよう、後ろから貪欲に選ぶ
    ans = []
    curr = N
    while curr > 0:
        for i in range(M, 0, -1):
            if curr-i == 0:
                break
            if DP[curr-i] < DP[curr]:
                break
        curr = curr - i
        ans.append(i)
    print(*reversed(ans), sep=" ")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, M, S)


if __name__ == '__main__':
    main()
Problem p02890 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
from collections import Counter
from itertools import accumulate
from collections import defaultdict
INF = float("inf")


def solve(N: int, A: "List[int]"):
    c = Counter(A)
    d = Counter(c.values())
    d = tuple(accumulate([d[i] for i in range(N, -1, -1)]))[::-1]
    S = [0]*(N+1)
    for i in range(1, N+1):
        S[i] = S[i-1] + d[i]

    def isOK(y):
        return S[y] < K*y

    def binary_search(x):
        ng = -1
        ok = len(x)+1

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid):
                ok = mid
            else:
                ng = mid
        return ng, ok

    for K in range(1, N+1):
        ng, ok = binary_search(range(N))
        print(ng)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections import Counter
from itertools import accumulate
from collections import defaultdict
INF = float("inf")


def solve(N: int, A: "List[int]"):
    c = Counter(A)
    d = Counter(c.values())
    d = tuple(accumulate([d[i] for i in range(N, -1, -1)])[::-1])
    S = [0]*(N+1)
    for i in range(1, N+1):
        S[i] = S[i-1] + d[i]

    def isOK(y):
        return S[y] < K*y

    def binary_search(x):
        ng = -1
        ok = len(x)+1

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid):
                ok = mid
            else:
                ng = mid
        return ng, ok

    for K in range(1, N+1):
        ng, ok = binary_search(range(N))
        print(ng)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()
Problem p02921 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(S: str, T: str):
    print(sum([s == t for s, t in zip(S, T)]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(S, T)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        s, t = edge
        self.E[s].append(t)


def solve(N: int, A: "List[List[int]]"):
    a_head = [0]*N
    stack = list(range(N))
    next_stack = []
    day = -1
    flag = True
    g = Graph(N)

    while flag:
        day += 1
        g.E = [[] for _ in range(N)]
        flag = False

        for i in stack:
            h = a_head[i]
            if h == N-1:
                continue
            if i in g.E[A[i][h]-1]:
                a_head[i] += 1
                a_head[A[i][h]-1] += 1
                flag = True
                next_stack.append(i)
                next_stack.append(A[i][h]-1)
                g.E[A[i][h]-1].remove(i)
            else:
                g.add_edge([i, A[i][h]-1])
        stack = next_stack[:]

    for h in a_head:
        if h != N-1:
            print(-1)
            return
    print(day)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()
Problem p02973 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
from bisect import bisect_right

INF = float("inf")


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(sum([1 for d in dp if d < INF]))
    # print(dp)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")


def solve(N: int, A: "List[int]"):

    a = deque([-INF])

    def isOK(index, key):
        return a[index] < key

    def binary_search(key):
        ng = -1
        ok = len(a)

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok

    ans = 0
    for aval in A:
        ok = binary_search(aval)
        # print(a, a[ok])
        if a[ok] == -INF:
            ans += 1
        a.insert(ok, aval)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()
Problem p02985 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
from collections import deque
from collections import defaultdict
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    # 枝
    edges = defaultdict(list)
    for from_, to_ in zip(a, b):
        edges[from_].append(to_)
        edges[to_].append(from_)

    # 色を決定済みかどうか
    flag = [False]*(N+1)

    def recur(n, preK, prepreK):
        count = 1
        count *= K-preK-prepreK
        count %= MOD
        flag[n] = True
        if edges[n] == 1:
            print(n, preK, prepreK, count)
            return count
        else:
            e = [ee for ee in edges[n] if flag[ee] is False]
            for i, to_ in enumerate(e):
                count *= recur(to_, 1, preK+i)
                count %= MOD
            return count

    print(recur(1, 0, 0) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections import deque
from collections import defaultdict
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    # 枝
    edges = defaultdict(list)
    for from_, to_ in zip(a, b):
        edges[from_].append(to_)
        edges[to_].append(from_)

    # 色を決定済みかどうか
    flag = [False]*(N+1)

    def recur(n, preK, prepreK):
        count = 1
        count *= K-preK-prepreK
        count %= MOD
        flag[n] = True
        if edges[n] == 1:
            print(n, preK, prepreK, count)
            return count
        else:
            e = [ee for ee in edges[n] if flag[ee] is False]
            for i, to_ in enumerate(e):
                count *= recur(to_, 1, preK+i)
                count %= MOD
            return count

    print(recur(1, 0, 0) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)


if __name__ == '__main__':
    main()
Problem p03049 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, s: "List[str]"):

    ABcount = 0
    Aend = 0
    Bstart = 0
    AendBstart = 0
    for i in range(N):
        ABcount += s[i].count("AB")
        if s[i][0] == "B" and s[i][-1] == "A":
            AendBstart += 1
        elif s[i][0] == "B":
            Bstart += 1
        elif s[i][-1] == "A":
            Aend += 1

    if AendBstart == 0:
        ABcount += min(Aend, Bstart)
    else:
        if Aend + Bstart > 0:
            ABcount += min(Aend, Bstart) + AendBstart
        else:
            ABcount += AendBstart - 1
    print(ABcount)
    # if AendBstart > 1:
    #     ABcount += AendBstart - 1
    #     AendBstart = 1
    # if Aend > 0 or Bstart > 0:
    #     ABcount += min(Aend, Bstart)+AendBstart
    # print(ABcount)

    # 愚直
    # print("愚直")
    # ans = []
    # for kumi in itertools.permutations(s, N):
    #     ans.append("".join(kumi).count("AB"))
    # print(max(ans))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, s)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, s: "List[str]"):

    ABcount = 0
    Aend = 0
    Bstart = 0
    AendBstart = 0
    for i in range(N):
        if "AB" in s[i]:
            ABcount += 1

        if s[i][0] == "B" and if s[i][-1] == "A":
            AendBstart += 1
        elif s[i][0] == "B":
            Bstart += 1
        elif s[i][-1] == "A":
            Aend += 1

    if AendBstart > 1:
        ABcount += AendBstart - 1
        AendBstart = 1
    if Aend > 0 or Bstart > 0:
        ABcount += min(Aend, Bstart)+AendBstart
    print(ABcount)

    # 愚直
    # print("愚直")
    # ans = []
    # for kumi in itertools.permutations(s, N):
    #     ans.append("".join(kumi).count("AB"))
    # print(max(ans))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, s)


if __name__ == '__main__':
    main()
Problem p03050 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
import math
import bisect
INF = float("inf")


def solve(N: int):

    if N == 1:
        print(0)
        return
    count = 0
    for r in range(1, int(math.sqrt(N))+1):  # 商
        # 余りは二分探索で良い
        lower = -(-N//r+1)
        upper = N//r
        while lower + 1 < upper:
            mid = (lower+upper)//2
            if N % mid >= r:
                lower = mid
            else:
                upper = mid
        if N % lower == r:
            count += lower
    print(count)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
import bisect
INF = float("inf")


def solve(N: int):

    count = 0
    for r in range(1, int(math.sqrt(N))+1):  # 商
        # 余りは二分探索で良い
        lower = -(-N//r+1)
        upper = N//r
        while lower + 1 < upper:
            mid = (lower+upper)//2
            if N % mid >= r:
                lower = mid
            else:
                upper = mid
        if N % lower == r:
            count += lower
    print(count)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
import bisect
INF = float("inf")


def solve(N: int):

    count = 0
    for r in range(1, int(math.sqrt(N))+1):  # 商
        # 余りは二分探索で良い
        lower = -(-N//r+1)
        upper = N//r
        while lower + 1 < upper:
            mid = (lower+upper)//2
            if N % mid >= r:
                lower = mid
            else:
                upper = mid
        if N % lower == r:
            count += lower
    print(count)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()
Problem p03059 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(A: int, B: int, T: int):
    print(B*int(T/A))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(A, B, T)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
import math
from collections import Counter
import collections
INF = float("inf")


import math


class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        """サイズNの配列を元にしたセグメント木
        """
        # 単位元
        self.idelem = 0
        # 比較関数
        self.func = GCD

        self.N0 = 2**(math.ceil(math.log2(N)))
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        """k番目の値をxに更新
        """
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        """区間[l, r)の最小値
        """
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s

    def __str__(self):
        return str(self.tree[self.N0-1:-1])


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def GCDs(*a):
    # リストで入力しないよう注意。
    if len(a) == 0:
        return -1  # エラー

    if len(a) == 1:
        return a[0]

    res = a[0]
    for i in range(1, len(a)):
        res = GCD(res, a[i])
    return res


def solve(N: int, A: "List[int]"):

    st = SegmentTree(N)
    for i, a in enumerate(A):
        st.update(i, a)

    buf = []
    for i in range(N):
        buf.append(GCD(st.query(0, i), st.query(i+1, N)))
    print(max(buf))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()
Problem p03101 (python)

Fixed submission:
H, W = [int(x) for x in input().split()]
h, w = [int(x) for x in input().split()]
print((H-h)*(W-w))

Buggy submission (verdict: Runtime Error):
import numpy as np
N, M, C = [int(x) for x in input().split()]
B = np.array([int(x) for x in input().split()])
A = np.array([[int(x) for x in input().split()] for _ in range(N)])
 
print(np.sum(A.dot(B) > -C))
Problem p03102 (python)

Fixed submission:
import numpy as np
N, M, C = [int(x) for x in input().split()]
B = np.array([int(x) for x in input().split()])
A = np.array([[int(x) for x in input().split()] for _ in range(N)])
print(np.sum(np.sum(A*B, axis=1) > -C))

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import numpy as np
N, M, C = [int(x) for x in input().split()]
B = np.array([int(x) for x in input().split()])
A = np.array([[int(x) for x in input().split()] for _ in range(N)])

print(np.sum(A@B > -C))
Problem p03103 (python)

Fixed submission:
N, M = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
AB.sort(key=lambda x: x[0])

s = 0
for ab in AB:
    if ab[1] > M:
        s += M*ab[0]
        break
    else:
        s += ab[0]*ab[1]
        M -= ab[1]

print(s)

Buggy submission (verdict: Runtime Error):
import numpy as np
N, M, C = [int(x) for x in input().split()]
B = np.array([int(x) for x in input().split()])
A = np.array([[int(x) for x in input().split()] for _ in range(N)])
 
print(np.sum(A.dot(B) > -C))

Buggy submission (verdict: Runtime Error):
import numpy as np
N, M, C = [int(x) for x in input().split()]
B = np.array([int(x) for x in input().split()])
A = np.array([[int(x) for x in input().split()] for _ in range(N)])
 
print(np.sum(A@B > -C))

Buggy submission (verdict: Runtime Error):
print(AB)

N, M = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
AB.sort(key=lambda x: x[0])

s = 0
for ab in AB:
    if ab[1] > M:
        s += M*ab[0]
        break
    else:
        s += ab[0]*ab[1]
        M -= ab[1]

print(s)
Problem p03138 (python)

Fixed submission:
from math import log2
import sys
N, K = [int(x) for x in input().split()]
a = [int(y) for y in input().split()]


def nketame(a, n):
    return (a & (1 << n)) >> n


def f(x):
    return sum([y ^ x for y in a])


if K == 0:
    print(f(0))
else:
    ans = []
    b = 0
    for i in range(int(log2(K))+1, 0, -1):
        # print("i", i)
        c = [nketame(x, i-1) for x in a].count(1)
        if c < N-c:
            bb = b + (1 << (i-1))
        else:
            bb = b
        if bb <= K:
            b = bb
            ans.append(b)
    # print(ans)
    print(f(max(ans)))

    # 全列挙
    # print("true ", max([(x, f(x)) for x in range(K+1)], key=lambda x: x[1]))

Buggy submission (verdict: Runtime Error):
from math import log2
import sys
N, K = [int(x) for x in input().split()]
a = [int(y) for y in input().split()]


def nketame(a, n):
    return (a & (1 << n)) >> n


def f(x):
    return sum([y ^ x for y in a])


if K == 0:
    print(f(0))
    sys.exit(1)

ans = []
for i in range(1, int(log2(K))+1):
    b = 1
    for j in range(i):
        b = b << 1
        c = [nketame(x, j) for x in a].count(1)
        if c < N-c:
            b += 1
    ans.append(b)
# print(ans)
# print(max(ans))
hprint(f(max(ans)))

Buggy submission (verdict: Runtime Error):
from math import log2
import sys
N, K = [int(x) for x in input().split()]
a = [int(y) for y in input().split()]
cand = [i for i in range(K)]


def nketame(a, n):
    return (a & (1 << (n-1))) >> (n-1)


def f(x):
    return sum([y ^ x for y in a])


if K == 0:
    print(f(0))
    sys.exit(1)

k = int(log2(K)+1)              # keta
# print(k)
ans = 0
for i in range(k, 0, -1):
    # print("sum", [nketame(x, i) for x in a])
    if sum([nketame(x, i) for x in a]) > int(N/2):
        ans += 0
    else:
        ans += 1
    # print("ans", "{0:08b}".format(ans << (i-1)), ans << (i-1))
    cand = [x for x in cand if nketame(x, i) == (ans & 1)]
    # print("cand", cand)
    if len(cand) == 1:
        break
    ans = ans << 1

ans = ans << (i-1)
# print("A", ans)
# print("f(A)", f(ans))
print(f(ans))

# for x in a:
#     print("0b{0:08b}".format(x))
# for i in range(K):
#     print("i:{0}, 0b{1:08b}".format(i, i))

# for i in range(K):
#     ans = sum([x ^ i for x in a])
#     print("f({0}) = {1:08b} = {2}".format(i, ans, ans))
Problem p03169 (python)

Fixed submission:
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):

    c = [0]*4
    for A in a:
        c[A] += 1

    J = min(c[2]+c[3]+1, N+1)
    I = min(c[1]+c[2]+c[3]+1, N+1)
    kitai = [[[0]*(I+1) for _ in range(J+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(J):
            for i in range(I):
                tot = i+j+k
                if tot == 0 or tot > N:
                    continue
                res = N + kitai[k][j][i-1]*i + \
                    kitai[k][j-1][i+1]*j + kitai[k-1][j+1][i]*k
                kitai[k][j][i] = res/tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections import Counter


def solve(N: int, a: "List[int]"):

    c = Counter(a)
    kitai = [[[0]*(c[1]+c[2]+c[3]+1) for _ in range(c[2]+c[3]+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(c[2]+c[3]+1):
            for i in range(c[1]+c[2]+c[3]+1):
                tot = i+j+k
                if tot == 0:
                    continue
                kitai[k][j][i] = N + kitai[k][j][i-1]*i + kitai[k][j-1][i+1]*j \
                    + kitai[k-1][j+1][i]*k
                kitai[k][j][i] /= tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()