Problem:


Score : 400 points

Problem Statement

Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:

Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9).

The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6, respectively.

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

There exists an integer that can be formed by exactly N matchsticks under the conditions.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

The output may not fit into a 64-bit integer type.

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

match = [0,2,5,5,4,5,6,3,7,6]

dig = [0] * (n+1)

inf = 10**9


for i in range(1,n+1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i-mat
        if bef >= 0:
            lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""
def dp(i):
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if dig[bef] == dig[i]-1 and (dig[bef] > 0 or bef == 0):
            if num > maxi:
                maxi = num
                k = bef
    ans += str(maxi)
    dp(k)

dp(n)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))

def dp(n, i):
    if n == 0:
        return 0
    if n < 0:
        return None
    if i == len(CHOICES):
        return None
    
    ret1 = dp(n - CHOICES[i][1], i)
    if ret1 == None:
        ret1 = -1
    elif ret1 == 0:
        ret1 = int(str(CHOICES[i][0]))
    else:
        ret1 = int(str(CHOICES[i][0]) + str(ret1))

    ret2 = dp(n, i+1)
    if ret2 == None:
        ret2 = -1
    else:
        ret2 = ret2
        
    if ret1 == -1 and ret2 == -1:
        return None
    return max(ret1, ret2)



match = [-100,2,5,5,4,5,6,3,7,6]
CHOICES = []
for i in A:
    if (i == 6) and (9 in A):
        continue
    if (i == 3) and (5 in A):
        continue
    if (i == 2) and (3 in A or 5 in A):
        continue
    CHOICES.append([i, match[i]])
CHOICES.sort(reverse=True)
#print(CHOICES)
ans = dp(N,0)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))

def dp(n, i):
    if n == 0:
        return 0
    if n < 0:
        return None
    if i == len(CHOICES):
        return None
    
    ret1 = dp(n - CHOICES[i][1], i)
    if ret1 == None:
        ret1 = 0
    elif ret1 == 0:
        ret1 = int(str(CHOICES[i][0]))
    else:
        ret1 = int(str(CHOICES[i][0]) + str(ret1))

    ret2 = dp(n, i+1)
    if ret2 == None:
        ret2 = 0
    else:
        ret2 = ret2
        
    return max(ret1, ret2)



match = [-100,2,5,5,4,5,6,3,7,6]
CHOICES = []
for i in A:
    if (i == 6) and (9 in A):
        continue
    if (i == 3) and (5 in A):
        continue
    if (i == 2) and (3 in A or 5 in A):
        continue
    CHOICES.append([i, match[i]])

print(CHOICES)
ans = dp(N,0)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))

def dfs(choices, s, cost, i):
    if i == len(choices):
        return -1
    if cost == 0:
        return int(s)
    if cost < 0:
        return -1
    
    if choices[i][0] == 1:
        if cost % 2 == 0:
            return int(s + (cost // 2) * '1')
        else:
            return -1
    
    
    tmp1 = dfs(
        choices,
        s + str(choices[i][0]),
        cost - choices[i][1],
        i
    )
    if i+1 == len(choices):
        tmp2 = -1
    else:
        tmp2 = dfs(
            choices,
            s,
            cost,
            i + 1
        )
    
    ret = max(tmp1, tmp2)
    return ret

match = [-100,2,5,5,4,5,6,3,7,6]
choices = []
for i in A:
    if (i == 6) and (9 in A):
        continue
    if (i == 3) and (5 in A):
        continue
    if (i == 2) and (3 in A or 5 in A):
        continue
    choices.append([i, match[i]])

choices.sort(reverse=True)

ans = dfs(choices, '', N, 0)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))

def dfs(choices, s, cost, i):
    if i == len(choices):
        return -1
    if cost == 0:
        return int(s)
    if cost < 0:
        return -1
    
    
    tmp1 = dfs(
        choices,
        s + str(choices[i][0]),
        cost - choices[i][1],
        i
    )
    if i+1 == len(choices):
        tmp2 = -1
    else:
        tmp2 = dfs(
            choices,
            s,
            cost,
            i + 1
        )
    
    ret = max(tmp1, tmp2)
    return ret

match = [-100,2,5,5,4,5,6,3,7,6]
choices = []
for i in A:
    if (i == 6) and (9 in A):
        continue
    if (i == 3) and (5 in A):
        continue
    if (i == 2) and (3 in A or 5 in A):
        continue
    choices.append([i, match[i]])

choices.sort(reverse=True)

ans = dfs(choices, '', N, 0)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))

def dfs(choices, s, cost, i):
    if i == len(choices):
        return -1
    if cost == 0:
        return int(s)
    if cost < 0:
        return -1
    
    
    tmp1 = dfs(
        choices,
        s + str(choices[i][0]),
        cost - choices[i][1],
        i
    )
    if i+1 == len(choices):
        tmp2 = -1
    else:
        tmp2 = dfs(
            choices,
            s,
            cost,
            i + 1
        )
    
    ret = max(tmp1, tmp2)
    return ret

match = [-100,2,5,5,4,5,6,3,7,6]
choices = []
for i in A:
    choices.append([i, match[i]])

choices.sort(reverse=True)
ans = dfs(choices, '', N, 0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    sorted_A = sorted(A)[::-1]
    dp = fill_dp(N,sorted_A)
    array = find_array(dp,N,sorted_A)
    return "".join(map(str,array))

def fill_dp(N,A):
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    return dp

def fill(A,dp,n,N):
    cand = [ dp[n-RESOURCE_DICT[num]]+1 for num in A if n - RESOURCE_DICT[num] >= 0 ]
    dp[n] = max(cand) if len(cand) > 0  else -100*N

def find_array(dp,N,sorted_A):
    array = []
    current_n = N
    for _ in range(dp[N]):
        for number in sorted_A:
            if dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    sorted_A = sorted(A)[::-1]
    dp = fill_dp(N,sorted_A)
    array = find_array(dp,N,sorted_A)
    return "".join(map(str,array))

def fill_dp(N,A):
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    return dp

def fill(A,dp,n,N):
    cand = [ dp[n-RESOURCE_DICT[num]]+1 for num in A if n - RESOURCE_DICT[num] >= 0 ]
    dp[n] = max(cand) if len(cand) > 0  else -100*N

def find_array(dp,N,sorted_A):
    array = []
    current_n = N
    print(sorted_A)
    for _ in range(dp[N]):
        for number in sorted_A:
            if dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break
    print(array)                
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

Submission status: Runtime Error

Solution code:

def get_input():
    N,K = [int(_) for _ in input().split()]
    S = [int(_) for _  in list(input())]
    return N,K,S

def solve(N,K,S):
    length = len(S)
    array = count_array(S)
    start_char = S[0]
    ans = find_max(array,K,start_char)
    return ans

def find_max(array,K,start_char):
    if start_char ==0 and len(array) <= 2 * K:
        return sum(array)
    elif start_char == 1 and len(array) <=2 * K+1 :
        return sum(array)
    else:
        if start_char == 0:
            start,end = 1,2*K+2
        else:
            start,end = 0,2*K+1
        idx = 0
                    
        current_sum = sum(array[start:end])
        ret = [current_sum]
        if start_char == 0:
            ret.append(sum(array[0:2*K]))
        ret.append(sum(array[-2*K:]))
        while(1):
            start+=2
            end+=2
            if end > len(array):
                break
            current_sum = current_sum- sum(array[start-2:start]) + sum(array[end-2:end])
            ret.append(current_sum)
    return max(ret)
            

def count_array(S):
    array = []
    cur_char = S[0]
    cur_val = 1
    for char in S[1:]:
        if cur_char != char:
            array.append(cur_val)
            cur_char = char
            cur_val = 1
        else:
            cur_val+=1
    array.append(cur_val)

    return array





if __name__ == "__main__":
    N,K,S = get_input()
    ans = solve(N,K,S)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    A = sorted(A)[::-1]
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    array = find_array(dp,N,A)
    return "".join(map(str,array))

def fill(A,dp,n,N):
    cand = [ dp[n-num]+1 for num in A if n - num >= 0 ]
    dp[n] = max(cand) if len(cand) > 0 else -100*N

def find_array(dp,N,A):
    array = []
    sorted_A = sorted(A)
    current_n = N
    for _ in range(dp[N]):
        for number in sorted_A[::-1]:
            if dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break                
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys 
RESOURCE_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    A = sorted(A)[::-1]
    dp = [ -100*N for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        fill(A,dp,i,N)
    print(dp)
    array = find_array(dp,N,A)
    return "".join(map(str,array))

def fill(A,dp,n,N):
    cand = [ dp[n-num]+1 for num in A if n - num >= 0 ]
    dp[n] = max(cand) if len(cand) > 0 else -100*N

def find_array(dp,N,A):
    array = []
    sorted_A = sorted(A)
    print(sorted_A )
    current_n = N
    for _ in range(dp[N]):
        for number in sorted_A[::-1]:
            if dp[current_n-RESOURCE_DICT[number]] == dp[current_n]-1:
                array.append(number)
                current_n -= RESOURCE_DICT[number]
                break
    print(array)
                
    return array


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys 
RESOURC_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    dp = [-1 for _ in range(N+1)]
    for i in range(N+1):
        fill(A,dp,i)
    return dp[N]


def count_digit(number,current=0):
    if number == 0:
        return current
    else:
        return count_digit(number//10,current=current+1)

def fill(A,dp,n):
    cand = []
    for number in A:
        weight = RESOURC_DICT[number]
        if n -weight>=0:
            if n- weight == 0:
                cand.append(number)
            else:
                if dp[n-weight] != -1:
                    cand.append(max(
                        10**count_digit(dp[n-weight])*number + dp[n-weight],
                        10 * dp[n-weight] +number  )
                        )
                else:
                    cand.append(-1)
        else:
            cand.append(-1)
    dp[n] = max(cand)


if __name__ =="__main__":
    N,M,A = get_input()
    ans = solve(N,M,A)
    print(ans)

Submission status: Runtime Error

Solution code:
import sys 
RESOURC_DICT = dict([(k,v) for k,v in zip(range(1,10),[2,5,5,4,5,6,3,7,6])])

def get_input():
    N,M = [ int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]
    return N,M,A


def solve(N,M,A):
    dp = [-1 for _ in range(N+1)]
    for i in range(N+1):
        fill(A,dp,i)
    return dp[N]


def count_digit(number,current=0):
    if number == 0:
        return current
    else:
        return count_digit(number//10,current=current+1)

def fill(A,dp,n):
    cand = []
    for number in A:
        weight = RESOURC_DICT[number]
        if n -weight>=0:
            if n- weight == 0:
                cand.append(number)
            else:
                if dp[n-weight] != -1:
                    cand.append(max(
                        10**count_digit(dp[n-weight])*number + dp[n-weight],
                        10 * dp[n-weight] +number  )
                        )
                else:
                    cand.append(-1)
        else:
            cand.append(-1)
    dp[n] = max(cand)


if __name__ =="__main__":
    N,M,A = get_input()
    solve(N,M,A)
    print(ans)

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)

V = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-1e10] * (N + 1)
dp[0] = 0

for i in range(1, N + 1):
    # i 本で表せる最大の桁数を dp に求める
    l = [dp[i - V[j]] + 1 for j in A if i - V[j] >= 0]
    if l:
        dp[i] = max(l)
# 各桁の最大値を求めていく
n = N
while n > 0:
    for j in A:
        if dp[n] == dp[n - V[j]] + 1:
            print(j, end='')
            n = n - V[j]
            break
print()

Submission status: Runtime Error

Solution code:
inf = float('inf')
N , M = map(int,input().split())
am = list(map(int,input().split()))
ll = [[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
l = [2,5,5,4,5,6,3,7,6]
# マッチをN本使うときの、最大の整数
dp = [-inf] * (N+1)
uselist = []
for a in am:
    uselist.append(ll[a-1])
for use in uselist:
    dp[use[1]] = max(dp[use[1]],use[0])
#print(dp)
for i in range(N+1):
    for use in uselist:
        dp[i] = max(dp[i] , dp[i-use[1]]*10+use[0])
#print(dp)
print(dp[-1])

Submission status: Runtime Error

Solution code:
def solve(n, a_list):
    numbers_map = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    usable_map = {}
    for a in a_list:
        usable_map[a] = numbers_map[a]

    # 1-origin 桁数を保存 -infで初期化
    inf = 1000
    dp = [0] + [-inf for _ in range(n)]
    for value in usable_map.values():
        dp[value] = 1

    # time O(NM)
    for cost in range(1, n + 1):
        for value in usable_map.values():
            if cost - value < 0 or dp[cost - value] == 0:
                continue
            dp[cost] = max(
                dp[cost],
                dp[cost - value] + 1
            )

    buff = []
    digit = n
    reverse_usable_list = sorted(usable_map.items(), reverse=True)
    while True:
        for num, value in reverse_usable_list:
            if digit - value < 0 or dp[digit] - 1 != dp[digit - value]:
                continue
            buff.append(str(num))
            digit -= value
            break
        if digit <= 0:
            break

    return "".join(buff)


def main():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))

    ans = solve(n, a_list)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
def solve(n, a_list):
    digits_map = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    useage_map = {}
    for a in a_list:
        useage_map[a] = digits_map[a]

    # 1-origin
    dp = [0 for _ in range(n + 1)]
    for digits, value in useage_map.items():
        dp[value] = digits

    # time O(NM)
    for cost in range(1, n + 1):
        for digits, value in useage_map.items():
            if cost - value < 0 or dp[cost - value] == 0:
                continue
            dp[cost] = max(
                dp[cost],
                int("{}{}".format(digits, dp[cost - value]))
            )

    return dp[n]


def main():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))

    ans = solve(n, a_list)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 数字kに対するマッチ必要本数を返す
def num(k):
    costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return costs[k-1]

# 動的計画法
# dp(i) := i本の最大桁数(i = 0,1,...,N)
# constructor
inf = 1000
# -infに設定しないと数字の選択時にミスる
dp = [-inf for _ in range(N+1)]
dp[0] = 0

cost_list = [num(k) for k in A]
for i in range(1, N+1):
    for cost in cost_list:
        if i - cost < 0:
            pass
        else:
            temp = dp[i - cost] + 1
            dp[i] = max(dp[i], temp)

ans = ''
many = N
for d in range(dp[N]): # 各桁
    for k in sorted(A, reverse=True):
        if dp[many - num(k)] == dp[many] - 1:
            ans += str(k)
            many -= num(k)
            break
        else:
            pass

print(int(ans))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 数字kに対するマッチ必要本数を返す
def num(k):
    costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return costs[k-1]

# 動的計画法
# dp(i) := i本の最大桁数(i = 0,1,...,N)
# constructor
inf = 1000
# -infに設定しないと数字の選択時にミスる
dp = [-inf for _ in range(N+1)]
dp[0] = 0

cost_list = [num(k) for k in A]
for i in range(1, N+1):
    for cost in cost_list:
        if i - cost < 0:
            pass
        else:
            temp = dp[i - cost] + 1
            dp[i] = max(dp[i], temp)

ans = ''
many = N
for d in range(dp[N]): # 各桁
    for k in sorted(A, reverse=True):
        if dp[many - num(k)] == dp[many] - 1:
            ans += str(k)
            many -= num(k)
            break
        else:
            pass

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 数字kに対するマッチ必要本数を返す
def num(k):
    costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    return costs[k-1]

# 動的計画法
# dp(i) := i本の最大桁数(i = 0,1,...,N)
# constructor
inf = 1000
dp = [-inf for _ in range(N+1)]
dp[0] = 0

costs = [num(k) for k in A]
for i in range(1, N+1):
    for cost in costs:
        if i - cost < 0:
            pass
        else:
            temp = dp[i - cost] + 1
            dp[i] = max(dp[i], temp)

ans = ''
many = N
for _ in range(dp[N]): # 各桁
    for k in sorted(A, reverse=True):
        if dp[many - num(k)] == dp[many] - 1:
            ans += str(k)
            many -= num(k)
            break
        else:
            pass

print(ans)

Submission status: Runtime Error

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 2 in a and 3 in a:
        a.remove(2)
    if 6 in a and 9 in a:
        a.remove(6)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if max(use) == b[0]:
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
            # n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            break
        else:
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Runtime Error

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 2 in a and 3 in a:
        a.remove(2)
    if 6 in a and 9 in a:
        a.remove(6)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if max(use) == b[0]:
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
        else:
            return base
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Runtime Error

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 2 in a and 3 in a:
        a.remove(2)
    if 6 in a and 9 in a:
        a.remove(6)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if max(use) == b[0]:
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
        else:
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Runtime Error

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 2 in a and 3 in a:
        a.remove(2)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if max(use) == b[0]:
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + (str(tmp_n) * tmp_c)
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
        else:
            tmp_n = use[-1]
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Runtime Error

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if max(use) == b[0]:
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + (str(tmp_n) * tmp_c)
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
        else:
            tmp_n = use[-1]
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Runtime Error

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    count = 0
    while n > 0 and count < 5:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if max(use) == b[0]:
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + (str(tmp_n) * tmp_c)
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
        else:
            tmp_n = use[-1]
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
        count += 1
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Runtime Error

Solution code:
n, _ = map(int, input().split())
numbers = list(map(int, input().split()))
reqs = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}

memo = {}


def max_counts(a, b):
    """
    a と b 大きい方を返す
    :param a: solve() の返り値
    :param b: solve() の返り値
    :return:
    """
    if a is None:
        return b
    if b is None:
        return a
    # 桁数は大きいほうが大きい
    if sum(a) > sum(b):
        return a
    if sum(a) < sum(b):
        return b
    # 桁数が同じなら、大きい数字の多いほうが大きい
    for a_c, b_c in zip(reversed(a), reversed(b)):
        if a_c > b_c:
            return a
        if a_c < b_c:
            return b
    return a


def solve(n):
    """
    n 本のマッチを使ったときの最大の整数の 0 から 9 までの使用回数をリストで返す
    :param n:
    :rtype: list of int
    """
    if n in memo:
        return memo[n]
    if n == 0:
        return [0 for _ in range(10)]
    if n < 0:
        return None

    res = None
    for num in numbers:
        counts = solve(n - reqs[num])
        if counts:
            res = max_counts(res, counts[:num] + [counts[num] + 1] + counts[num + 1:])

    memo[n] = res
    return res


result_counts = solve(n)
ans = ''
for num in range(9, 0, -1):
    for _ in range(result_counts[num]):
        ans += str(num)
print(ans)

Submission status: Runtime Error

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(N + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]]=1
for n in range(2,N+1):
    for a in A:
        if n-Cost[a]>=0 and dp[n-Cost[a]] != -1:
            dp[n]=max(dp[n], dp[n-Cost[a]]+1)
k=dp[N]
n=N
buf=[]
for i in range(dp[N]-1):
    b=-1
    for a in A:
        if n-Cost[a]>=0 and dp[n-Cost[a]] == k-1:
            b=max(b,a)
    k-=1
    n-=Cost[b]
    buf.append(b)
b=-1
for a in A:
    if Cost[a] == n:
        b=max(b,a)
buf.append(b)
print("".join(map(str,buf)))

Submission status: Runtime Error

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(N + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]]=1
for n in range(2,N+1):
    for a in A:
        if dp[n-Cost[a]] != -1:
            dp[n]=max(dp[n], dp[n-Cost[a]]+1)
k=dp[N]
n=N
buf=[]
for i in range(dp[N]-1):
    b=-1
    for a in A:
        if dp[n-Cost[a]] == k-1:
            b=max(b,a)
    k-=1
    n-=Cost[b]
    buf.append(b)
b=-1
for a in A:
    if Cost[a] == n:
        b=max(b,a)
buf.append(b)
print("".join(map(str,buf)))

Submission status: Runtime Error

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(N + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]]=1
for n in range(N+1):
    for a in A:
        if dp[n-Cost[a]] != -1:
            dp[n]=max(dp[n], dp[n-Cost[a]]+1)
k=dp[N]
n=N
buf=[]
if dp[N]-1>0:
    for i in range(dp[N]-1):
        b=-1
        for a in A:
            if dp[n-Cost[a]] == k-1:
                b=max(b,a)
            
        k-=1
        n-=Cost[b]
        buf.append(b)
b=-1
for a in A:
    if Cost[a] == n:
        b=max(b,a)
buf.append(b)
print("".join(map(str,buf)))

Submission status: Runtime Error

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(N + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]]=1
for n in range(N+1):
    for a in A:
        if dp[n-Cost[a]] != -1:
            dp[n]=max(dp[n], dp[n-Cost[a]]+1)
k=dp[N]
n=N
buf=[]
if dp[N]-1>=0:
    for i in range(dp[N]-1):
        b=-1
        for a in A:
            if dp[n-Cost[a]] == k-1:
                b=max(b,a)
            
        k-=1
        n-=Cost[b]
        buf.append(b)
b=-1
for a in A:
    if Cost[a] == n:
        b=max(b,a)
buf.append(b)
print("".join(map(str,buf)))

Submission status: Runtime Error

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(N + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]]=1
for n in range(N+1):
    for a in A:
        if dp[n-Cost[a]] != -1:
            dp[n]=max(dp[n], dp[n-Cost[a]]+1)
k=dp[N]
n=N
buf=[]
if dp[N]>=2:
    for i in range(dp[N]-1):
        b=-1
        for a in A:
            if dp[n-Cost[a]] == k-1:
                b=max(b,a)
            
        k-=1
        n-=Cost[b]
        buf.append(b)
b=-1
for a in A:
    if Cost[a] == n:
        b=max(b,a)
buf.append(b)
print("".join(map(str,buf)))