Problem p03128 (python)

Fixed submission:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min]
l.sort(key=lambda x: x[1], reverse=True)
C = g + l

def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for i in range(len(C)):
            a, m = C[i]
            nxt = dp(rem-m, C[i:])
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


i = 0
while True:
    quo = N // n_min - i
    rem = N % n_min + i * n_min
    lst = dp(rem, C)
    if lst is not None:
        lst = sorted(lst + [a_min] * (quo-len(lst)), reverse=True)
        print(''.join(map(str, lst)))
        break
    i += 1

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min]
l.sort(key=lambda x: x[1], reverse=True)


def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for i in range(len(C)):
            a, m = C[i]
            nxt = dp(rem-m, C[i:])
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


lst = dp(N % n_min, g + l)
lst = sorted(lst + [a_min] * (N//n_min - len(lst)), reverse=True)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min]
l.sort(key=lambda x: x[1], reverse=True)


def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for a, m in C:
            nxt = dp(rem-m, C)
            if nxt is not None:
                ret = [a] + nxt
                break
            C.pop(0)
    return ret


lst = dp(N % n_min, g + l)
lst = sorted(lst + [a_min] * (N//n_min - len(lst)), reverse=True)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min]
l.sort(key=lambda x: x[1], reverse=True)

def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for a, m in C:
            nxt = dp(rem-m, C)
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


lst = dp(N % n_min, g + l)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min]
l.sort(key=lambda x: x[1], reverse=True)

def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for a, m in C:
            nxt = dp(rem-m, C)
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


lst = dp(N % n_min, g + l)
lst = sorted(lst + [a_min] * (N//n_min - len(lst)), reverse=True)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min][::-1]
l.sort(key=lambda x: x[1], reverse=True)

def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for a, m in C:
            nxt = dp(rem-m, C)
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


lst = dp(N % n_min, g + l)
lst = sorted(lst + [a_min] * (N//n_min - len(lst)), reverse=True)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min][::-1]


def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for a, m in C:
            nxt = dp(rem-m, C)
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


lst = dp(N % n_min, g + l)
lst = sorted(lst + [a_min] * (N//n_min - len(lst)), reverse=True)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])


def dp(N, B, min_):
    if N == 0:
        return []
    elif N // min_[1] < 1:
        return None
    elif N % min_[1] == 0:
        return [min_[0]] * (N // min_[1])
    else:
        for a, n in B:
            if (N // min_[1]) - ((N-n) // min_[1]) == 1:
                ret = dp(N-n, B, min_)
                if ret is not None:
                    return [a] + ret
        return None


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])


def dp(N, B, min_):
    if N == 0:
        return []
    elif N // min_[1] < 1:
        return None
    elif N % min_[1] == 0:
        return [min_[0]] * (N // min_[1])
    else:
        for a, n in B:
            if (N // min_[1]) - ((N-n) // min_[1]) == 1:
                ret = dp(N-n, B, min_)
                if ret is not None:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])


def dp(N, B, min_):
    if N == 0:
        return []
    elif N // min_[1] < 1:
        return None
    elif N % min_[1] == 0:
        return [min_[0]] * (N // min_[1])
    else:
        for a, n in B:
            if (N // min_[1]) - ((N-n) // min_[1]) == 1:
                ret = dp(N-n, B, min_[1])
                if ret is not None:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N == 0:
        return []
    elif N // min_ < 1:
        return None
    else:
        for a, n in B:
            if (N // min_) - ((N-n) // min_) == 1:
                ret = dp(N-n, B, min_)
                if ret is not None:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N // min_ == 1:
        for a, n in B:
            if n == N:
                return [a]
        return None
    else:
        for a, n in B:
            if (N // min_) - ((N-n) // min_) == 1:
                ret = dp(N-n, B, min_)
                if ret is not None:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N // min_ == 1:
        for a, n in B:
            if n == N:
                return [a]
        return None
    else:
        for a, n in B:
            if (n - min_) <= (N % min_):
                ret = dp(N-n, B, min_)
                if ret is None:
                    continue
                else:
                    return [a] + ret


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
min_ = min(B, key=lambda x: x[1])[1]


def dp(N, B, min_):
    if N // min_ == 1:
        for a, n in B:
            if n == N:
                return [a]
    else:
        for a, n in B:
            if (n - min_) <= (N % min_):
                return [a] + dp(N-n, B, min_)


lst = dp(N, B, min_)
print(''.join(map(str, lst)))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

num = sorted([(a, req[a]) for a in A], key=lambda x: x[1])
k_min, n_min = num[0]
gt = sorted([(k, n-n_min) for k, n in num if k > k_min],
            key=lambda x: x[0], reverse=True)
lt = sorted([(k, n-n_min) for k, n in num if k < k_min],
            key=lambda x: x[0])
order = N // n_min
sum_rem = N - n_min*order

lst = []
for k, n in gt:
    if sum_rem == 0:
        continue
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
for k, n in lt:
    if sum_rem == 0:
        continue
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
lst.extend([k_min]*(order-len(lst)))


print(''.join(map(str, sorted(lst, reverse=True))))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

num = sorted([(a, req[a]) for a in A], key=lambda x: x[1])
k_min, n_min = num[0]
gt = sorted([(k, n-n_min) for k, n in num[1:] if k > k_min],
            key=lambda x: x[0], reverse=True)
lt = sorted([(k, n-n_min) for k, n in num[1:] if k < k_min],
            key=lambda x: x[0])
order = N // n_min
sum_rem = N - n_min*order

lst = []
for k, n in gt:
    if sum_rem == 0:
        continue
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
for k, n in lt:
    if sum_rem == 0:
        continue
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
lst.extend([k_min]*(order-len(lst)))


print(''.join(map(str, sorted(lst, reverse=True))))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

num = sorted([(a, req[a]) for a in A], key=lambda x: x[1])
k_min, n_min = num[0]
gt = sorted([(k, n-n_min) for k, n in num[1:] if k > k_min],
            key=lambda x: x[0], reverse=True)
lt = sorted([(k, n-n_min) for k, n in num[1:] if k < k_min],
            key=lambda x: x[0])
order = N // n_min
sum_rem = N - n_min*order

lst = []
for k, n in gt:
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
for k, n in lt:
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
lst.extend([k_min]*(order-len(lst)))


print(''.join(map(str, sorted(lst, reverse=True))))

Buggy submission (verdict: Runtime Error):
from sys import stdin

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

A_min = min(A)

k = 1
for i in range(int(A_min**0.5))[::-1]:
    if A_min % (i+1) != 0:
        continue
    k1, k2 = i+1, A_min//(i+1)
    if all(a % k2 == 0 for a in A):
        k = max(k, k2)
    elif all(a % k1 == 0 for a in A):
        k = max(k, k1)

print(k)

# D

from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

num = sorted([(a, req[a]) for a in A], key=lambda x: x[1])
k_min, n_min = num[0]
gt = sorted([(k, n-n_min) for k, n in num[1:] if k > k_min],
            key=lambda x: x[0], reverse=True)
lt = sorted([(k, n-n_min) for k, n in num[1:] if k < k_min],
            key=lambda x: x[0])
order = N // n_min
sum_rem = N - n_min*order

lst = []
for k, n in gt:
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
for k, n in lt:
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
lst.extend([k_min]*(order-len(lst)))


print(''.join(map(str, sorted(lst, reverse=True))))

Buggy submission (verdict: Runtime Error):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

num = sorted([(a, req[a]) for a in A], key=lambda x: x[1])
k_min, n_min = num[0]
gt = sorted([(k, n-n_min) for k, n in num[1:] if k > k_min],
            key=lambda x: x[0], reverse=True)
lt = sorted([(k, n-n_min) for k, n in num[1:] if k < k_min],
            key=lambda x: x[0])
order = N // n_min
sum_rem = N - n_min*order

lst = []
for k, n in gt:
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
for k, n in lt:
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
lst.extend([k_min]*(order-len(lst)))