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:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
while(dim > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
    dim -= 1
print(ans if ans else 0)

Submission status: Runtime Error

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
while(dim > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            dim -= 1
            break
print(0)

Submission status: Runtime Error

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
while(dim > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            dim -= 1
            break
print(ans if ans else 0)

Submission status: Runtime Error

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
while(N > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
print(ans if ans else 0)

Submission status: Runtime Error

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
while(N > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
print(ans)

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split(' '))
useable_numbers = list(sorted(map(int, input().split(' '))))
required_maches = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}

dp = dict()

def evaluate(used_numbers):
    if used_numbers == []:
        return 0
    return int(''.join(map(str, sorted(used_numbers, reverse=True))))

def find(used_matches):
    if used_matches in dp:
        return dp[used_matches]
    if used_matches == 0:
        dp[used_matches] = []
        return dp[used_matches]
    if used_matches < 0:
        dp[used_matches] = None
        return dp[used_matches]
    
    candidates = [ai for ai in useable_numbers 
        if find(used_matches - required_maches[ai]) is not None]
    if candidates == []:
        dp[used_matches] = None
        return dp[used_matches]
    
    max_ai = max(candidates,
        key=lambda ai: evaluate(find(used_matches - required_maches[ai]) + [ai]))
    dp[used_matches] = find(used_matches - required_maches[max_ai]) + [max_ai]
    return dp[used_matches]

print(evaluate(find(n)))

Submission status: Runtime Error

Solution code:
#ABC118D-MatchMatching.py

from sys import stdin
from functools import lru_cache

input = stdin.readline

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

A = list(map(int, input().split()))
A.sort(reverse=True)

B = [2,5,5,4,5,6,3,7,6]

def num(n):
    return B[n-1]

@lru_cache(maxsize=None)
def dp(i):
    if i == 0:
        return 0
    elif i < 0:
        return -float('inf')
    else:
        C = []
        for j in range(M):
            C.append(dp(i-num(A[j]))+1)
        return max(C)

s = ''
n = dp(N)
K = N

for i in range(n):
    for j in range(M):
        if dp(K-num(A[j])) == dp(K)-1:
            s += str(A[j])
            K -= B[A[j]-1]
            break

print(int(s))

Submission status: Runtime Error

Solution code:
import sys

def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  A = list(map(int, input().split()))
  d = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
  
  dp = [0 for _ in range(N+1)]
  for i in range(1, N+1):
    dpi = - float('inf')
    for a in A:
      if i % d[a] == 0:
        dpi = max(dpi, i // d[a])
      elif d[a] <= i:
        dpi = max(dpi, dp[i - d[a]] + 1)
    dp[i] = dpi

  ans = [0 for _ in range(dp[N])]
  for i in range(len(ans)):
    num = 0
    for a in A:
      if dp[N - d[a]] == dp[N] - 1:
        num = max(num, a)
    ans[i] = str(num)
    N -= d[num]

  print(''.join(ans))


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
def printing(a_start, a_2, n):
    if a_start[1] == 5:
        aaaaaa

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)

    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Runtime Error

Solution code:
def printing(a_start, a_2, n):
    if a_start[1] == 4:
        aaaaaa

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)

    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Runtime Error

Solution code:
def printing(a_start, a_2, n):
    if a_start[1] == 3:
        aaaaaa

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)

    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
from itertools import product

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


COST = np.array([2, 5, 5, 4, 5, 6, 3, 7, 6])

N, M = ds_in()
A_list = np.array(ds_in())
A_cost = COST[A_list - 1]  # 0始まりで取得

min_cost = min(A_cost)
base_num = max(A_list[A_cost == min_cost])

if N % min_cost == 0:
    print(int(str(base_num) * (N//min_cost)))
    exit()

# 本数をmin_costのmodを考え、cost最小のものを記憶
mod_cost = {i: [-1, 10**6] for i in range(1, min_cost)}
for a, c in zip(A_list, A_cost):
    mod = c % min_cost
    if mod > 0:
        if c < mod_cost[mod][1]:
            mod_cost[mod][1] = c
            mod_cost[mod][0] = a
        elif c == mod_cost[mod][1]:
            mod_cost[mod][0] = max(a, mod_cost[mod][0])

# 存在しないmodは除く
for i in range(1, min_cost):
    if mod_cost[i][1] == 10**6:
        mod_cost.pop(i)

N_mod = N % min_cost
upper = []
for m in mod_cost.keys():
    upper.append([i for i in range(0, N_mod // m + 1)])


ans = []
for cand in product(*upper):
    if N_mod == sum(map(lambda x, y: x*y, mod_cost.keys(), cand)):
        temp_N = N
        num_list = []
        for x, y in zip(mod_cost.keys(), cand):
            num_list.extend([mod_cost[x][0]] * y)
            temp_N -= mod_cost[x][1] * y
        if temp_N >= 0:
            num_list.extend([base_num] * (temp_N // min_cost))
            num_list.sort()
            ans.append(int(''.join(map(str, num_list[::-1]))))

print(max(ans))

Submission status: Runtime Error

Solution code:
def printing(a_start, a_2, n):
    if a_start[1] == 2:
        aaaaaa

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)

    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
from itertools import product

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


COST = np.array([2, 5, 5, 4, 5, 6, 3, 7, 6])

N, M = ds_in()
A_list = np.array(ds_in())
A_cost = COST[A_list - 1]  # 0始まりで取得

min_cost = min(A_cost)
base_num = max(A_list[A_cost == min_cost])

if N % min_cost == 0:
    print(int(str(base_num) * (N//min_cost)))
    exit()

# 本数をmin_costのmodを考え、cost最小のものを記憶
mod_cost = {i: [-1, 10**6] for i in range(1, min_cost)}
for a, c in zip(A_list, A_cost):
    mod = c % min_cost
    if mod > 0:
        if c < mod_cost[mod][1]:
            mod_cost[mod][1] = min(c, mod_cost[mod][1])
            mod_cost[mod][0] = a
        elif c == mod_cost[mod][1]:
            mod_cost[mod][0] = max(a, mod_cost[mod][0])

# 存在しないmodは除く
for i in range(1, min_cost):
    if mod_cost[i][1] == 10**6:
        mod_cost.pop(i)

N_mod = N % min_cost
upper = []
for m in mod_cost.keys():
    upper.append([i for i in range(0, N_mod // m + 1)])


ans = []
for cand in product(*upper):
    if N_mod == sum(map(lambda x, y: x*y, mod_cost.keys(), cand)):
        temp_N = N
        num_list = []
        for x, y in zip(mod_cost.keys(), cand):
            num_list.extend([mod_cost[x][0]] * y)
            temp_N -= mod_cost[x][1] * y
        num_list.extend([base_num] * (temp_N // min_cost))
        num_list.sort()
        ans.append(int(''.join(map(str, num_list[::-1]))))

print(max(ans))

Submission status: Runtime Error

Solution code:
match_num=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int, input().split())
nums=sorted(list(map(int, input().split())),reverse=True)
INF=1000000
#max桁数
dp = [-INF for _ in range(N+1)]
dp[0]=0
usables=[]
for n in nums:
  usables.append(match_num[n])

for i in range(min(usables), N+1):
  tmp=[]
  for u in usables:
    if (i-u)>=0:
      tmp.append(dp[i-u])
  
  dp[i]=max(tmp)+1

remained_maches=N

ans=''  
for i in range(dp[N]):
  for j in range(M):
    if dp[remained_maches]-1==dp[remained_maches-usables[j]]:
      ans+=str(nums[j])
      remained_maches-=usables[j]
      break
        
print(ans)

Submission status: Runtime Error

Solution code:
match_num=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int, input().split())
nums=sorted(list(map(int, input().split())),reverse=True)
INF=1000000
#max桁数
dp = [-INF for _ in range(N+1)]
dp[0]=0
usables=[]
for n in nums:
  usables.append(match_num[n])

for i in range(min(usables), N+1):
  tmp=[]
  for u in usables:
    if(i-u)>=0:
      tmp.append(dp[i-u])
  
  dp[i]=max(tmp)+1

remained_maches=N

ans=''  
for i in range(dp[N]):
  for j in range(M):
    if dp[remained_maches]-1==dp[remained_maches-usables[j]]:
      ans+=str(nums[j])
      remained_maches-=usables[j]
      break

print(dp)
print(ans)

Submission status: Runtime Error

Solution code:
match_num=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int, input().split())
nums=sorted(list(map(int, input().split())),reverse=True)
INF=1000000
#max桁数
dp = [-INF for _ in range(N+1)]
dp[0]=0
usables=[]
for n in nums:
  usables.append(match_num[n])

for i in range(min(usables), N+1):
  tmp=[]
  for u in usables:
    tmp.append(dp[i-u])
  
  dp[i]=max(tmp)+1

remained_maches=N

ans=''  
for i in range(dp[N]):
  for j in range(M):
    if remained_maches-usables[j]>=0 :
      if dp[remained_maches]-1==dp[remained_maches-usables[j]]:
        ans+=str(nums[j])
        remained_maches-=usables[j]
        break
print(ans)

Submission status: Runtime Error

Solution code:
d=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=list(map(int,input().split()))
l=[]
for a in A:
    l.append([a,d[a]])
l.sort(key=lambda x:x[0],reverse=True)
l.sort(key=lambda x:x[1])
min_val,min_match=l[0]

ans=[]
if N%min_match==0:
    ans.append(int(str(min_val)*(N//min_match)))
from itertools import combinations
for i in range(1,M):
    for p in combinations(l[1:],i):
        v=[]
        m_sum=0
        for val,mat in p:
            v.append(str(val))
            m_sum+=mat
        if (N-m_sum)%min_match==0:
            ans.append(int(''.join(sorted(v+
                [str(min_val)]*((N-m_sum)//min_match),reverse=True))))
print(max(ans))

Submission status: Runtime Error

Solution code:
d=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=list(map(int,input().split()))
l=[]
for a in A:
    l.append([a,d[a]])
l.sort(key=lambda x:x[0],reverse=True)
l.sort(key=lambda x:x[1])
min_val,min_match=l[0]

ans=[]
if N%min_match==0:
    ans.append(str(min_val)*(N//min_match))
from itertools import combinations
for i in range(1,M):
    for p in combinations(l[1:],i):
        v=[]
        m_sum=0
        for val,mat in p:
            v.append(str(val))
            m_sum+=mat
        if (N-m_sum)%min_match==0:
            ans.append(int(''.join(sorted(v+
                [str(min_val)]*((N-m_sum)//min_match),reverse=True))))
print(max(ans))

Submission status: Runtime Error

Solution code:
match_num=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int, input().split())
nums=sorted(list(map(int, input().split())),reverse=True)
INF=1000000
#max桁数
dp = [-INF for _ in range(N+1)]
dp[0]=0
usables=[]
for n in nums:
  usables.append(match_num[n])

for i in range(min(usables), N+1):
  tmp=[]
  for u in usables:
    tmp.append(dp[i-u])
  
  dp[i]=max(tmp)+1

remained_maches=N

ans=''  
for i in range(dp[N]):
  for j in range(M):
    if dp[remained_maches]-1==dp[remained_maches-usables[j]]:
      ans+=str(nums[j])
      remained_maches-=usables[j]
      break
      
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

    #  replaces = [digits[i][0] for i in idxs]
    #  uppers = [d for d in replaces if d > base_digit]
    #  lowers = [d for d in replaces if d < base_digit]

      num = number[:]

    #  if len(uppers) > 0:
    #    num = uppers + num[len(uppers):]

    #  if len(lowers) > 0:
    #    num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):

  number = [base_digit] * base_length
  remain -= base_cost * base_length

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

    #  replaces = [digits[i][0] for i in idxs]
    #  uppers = [d for d in replaces if d > base_digit]
    #  lowers = [d for d in replaces if d < base_digit]

      num = number[:]

    #  if len(uppers) > 0:
    #    num = uppers + num[len(uppers):]

    #  if len(lowers) > 0:
    #    num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number))

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
A = list(map(int,input().split()))
match = np.array([[a,num_match(a)] for a in A])
sorted_num = match[np.argsort(match[:,0])[::-1]]
sorted_match = match[np.argsort(match[:,1])]
min_num_match = sorted_match[0][1]
max_k = int(N/min_num_match)#一番小さいマッチ数の整数を使える数
rem = N%min_num_match + min_num_match
#rem+match[min_match_index][1]*kがmin以外の組み合わせの合計
ans_exist = False
ans = 0
used_match = []
for k in range(max_k):#remを更新していく？
    if rem in sorted_match[:,1]:
        ans_exist = True
        used_match.append(rem)
        break
    else:
        for n in sorted_match[:,1]:
            if n < rem and n!=min_num_match :
                used_match.append(n)
                rem = rem-n
                break
    if ans_exist:
        #max_k = max_k-k
        break
    else:
        rem = rem + min_num_match
used_match.append(min_num_match)
used_num = []
for um in used_match:
    for i in range(sorted_num.shape[0]):
        if um == sorted_num[i][1]:
            used_num.append(sorted_num[i][0])
            break
base_num=used_num.pop()
sorted_used_num = sorted(used_num,reverse=True)
upper  =[]
lower = []
for s in sorted_used_num:
    if s > base_num:
        upper.append(s)
    else:
        lower.append(s)
lower = sorted(lower)
ans_list = [base_num]*max_k
if len(upper) > 0:
    for i in range(len(upper)):
        ans_list[i] = upper[i]
if len(lower) > 0:
    for j in range(len(lower)):
        ans_list[len(ans_list)-1-j] = lower[j]
ans = ""
for a in ans_list:
    ans = ans + str(a)
ans = int(ans)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):

  number = [base_digit] * base_length
  remain -= base_cost * base_length

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

      replaces = [digits[i][0] for i in idxs]
      uppers = [d for d in replaces if d > base_digit]
      lowers = [d for d in replaces if d < base_digit]

      num = number[:]

      if len(uppers) > 0:
        num = uppers + num[len(uppers):]

      if len(lowers) > 0:
        num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number))

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
d = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
d_ = {}
for i in range(M):
    d_[d[A[i]]] = A[i]
diff = [(d_[key],key) for key in d_]
diff.sort()

DP = ['']*(N+1)
for a,l in diff:
    DP[l] = str(a)
    
for i in range(N+1):
    for a,l in diff:
        if i-l >= 0:
            if len(DP[i-l])+1>=len(DP[i]) and DP[i-l]!='':
                    DP[i] = str(a)+DP[i-l]

ans = list(DP[N])
ans.sort()
ans.reverse()
ans = ''.join(ans)
print(ans)

Submission status: Runtime Error

Solution code:
"""
Match Matching
提出 #4299735 を参考に作成
"""


def solve():
    # 初期値の設定
    num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    # 丁度n本で作成できる最大桁数を格納する.
    # 初期値は -inf (丁度使い切ることは不可能) としておく
    dp = [-1 * float("inf")] * (N + 1)

    # 動的計画法で丁度n本のマッチを使うときに作れる最大桁数を計算する
    for n in range(1, N + 1):
        for a in A:
            if n - num[a] >= 0:
                # マッチがnum[a]本あるときにaが作れるなら,
                # n - num[a]本の時よりも1桁多く作れるはず.
                # これをすべてのAに対して行い、その中で最大となった桁数を求める.
                dp[n] = max(dp[n], dp[n - num[a]] + 1)
    # print('各本数丁度で作れる最大桁数')
    # print(dp)

    # 回答となる数値を算出
    ans = ''
    for i in range(dp[N]):  # dp[N]桁の数を上位の桁から決定していく
        for a in A:
            # num[a]本使って数を作ったとき,
            # N - num[a] 本で作れる桁数よりも N 本で作れる桁数のほうが1多い場合,
            # numを作っても最終的に作れる数の桁数は変わらない.
            # そのため dp[N] - 1 == dp[N - num[a]] を満たすような最大のAを作り,
            # 作成する数の上位桁に使用すればよい.
            # 同じ本数のマッチを使用する場合はより大きい数を採用する.
            # そのためAはあらかじめ降順にソートしておく.
            # 最初の条件で配列外アクセスを防ぐ
            if N - num[a] > -1 and dp[N] - 1 == dp[N - num[a]]:
                ans += str(a)
                N -= num[a]
                break
        # print('現在の残本数', N, '採用された数', a)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
"""
Match Matching
提出 #4299735 を参考に作成
"""


def solve():
    # 初期値の設定
    num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    # 丁度n本で作成できる最大桁数を格納する.
    # 初期値は -inf (丁度使い切ることは不可能) としておく
    dp = [-1 * float("inf")] * (N + 1)

    # 動的計画法で丁度n本のマッチを使うときに作れる最大桁数を計算する
    dp[0] = 0
    for a in A:
        if num[a] <= N:
            dp[num[a]] = 1
    
    for n in range(1, N + 1):
        for a in A:
            if n - num[a] >= 0:
                # マッチがnum[a]本あるときにaが作れるなら,
                # n - num[a]本の時よりも1桁多く作れるはず.
                # これをすべてのAに対して行い、その中で最大となった桁数を求める.
                dp[n] = max(dp[n], dp[n - num[a]] + 1)
    # print('各本数丁度で作れる最大桁数')
    # print(dp)

    # 回答となる数値を算出
    ans = ''
    for i in range(dp[N]):  # dp[N]桁の数を上位の桁から決定していく
        for a in A:
            # num[a]本使って数を作ったとき,
            # N - num[a] 本で作れる桁数よりも N 本で作れる桁数のほうが1多い場合,
            # numを作っても最終的に作れる数の桁数は変わらない.
            # そのため dp[N] - 1 == dp[N - num[a]] を満たすような最大のAを作り,
            # 作成する数の上位桁に使用すればよい.
            # 同じ本数のマッチを使用する場合はより大きい数を採用する.
            # そのためAはあらかじめ降順にソートしておく.
            if dp[N] - 1 == dp[N - num[a]]:
                ans += str(a)
                N -= num[a]
                break
        # print('現在の残本数', N, '採用された数', a)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
"""
Match Matching
提出 #4299735 を参考に作成
"""


def solve():
    # 初期値の設定
    num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    # 丁度n本で作成できる最大桁数を格納する.
    # 初期値は -inf (丁度使い切ることは不可能) としておく
    dp = [-1 * float("inf")] * (N + 1)
    # 動的計画法で丁度n本のマッチを使うときに作れる最大桁数を計算する
    dp[0] = 0
    for n in range(1, N + 1):
        for a in A:
            if n - num[a] >= 0:
                # マッチがnum[a]本あるときにaが作れるなら,
                # n - num[a]本の時よりも1桁多く作れるはず.
                # これをすべてのAに対して行い、その中で最大となった桁数を求める.
                dp[n] = max(dp[n], dp[n - num[a]] + 1)
    # print('各本数丁度で作れる最大桁数')
    # print(dp)

    # 回答となる数値を算出
    ans = ''
    for i in range(dp[N]):  # dp[N]桁の数を上位の桁から決定していく
        for a in A:
            # num[a]本使って数を作ったとき,
            # N - num[a] 本で作れる桁数よりも N 本で作れる桁数のほうが1多い場合,
            # numを作っても最終的に作れる数の桁数は変わらない.
            # そのため dp[N] - 1 == dp[N - num[a]] を満たすような最大のAを作り,
            # 作成する数の上位桁に使用すればよい.
            # 同じ本数のマッチを使用する場合はより大きい数を採用する.
            # そのためAはあらかじめ降順にソートしておく.
            if dp[N] - 1 == dp[N - num[a]]:
                ans += str(a)
                N -= num[a]
                break
        # print('現在の残本数', N, '採用された数', a)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N, M= map(int, input().split())
a_list = sorted(map(int, input().split()), reverse = True)

# インデックスを分かりやすくするために先頭に0を追加
match_num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

# 桁数を調べる
for i in range(1, N+1):
    dp[i] = max([dp[i - match_num[a]] + 1 for a in a_list])

# 各桁に使う数字を調べる
ans = [""] * dp[N]
rest_match = N
for i in range(dp[N]):
    for a in a_list:
        index = rest_match - match_num[a]
        if index >= 0 and dp[index] == dp[N] - i - 1:
            rest_match -= match_num[a]
            ans[i] = str(a)
            break
print("".join(ans))

Submission status: Runtime Error

Solution code:
N, M= map(int, input().split())
a_list = sorted(map(int, input().split()), reverse = True)

# インデックスを分かりやすくするために先頭に0を追加
match_num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

# 桁数を調べる
for i in range(1, N+1):
    dp[i] = max([dp[i - match_num[a]] + 1 for a in a_list])

# 各桁に使う数字を調べる
ans = [""] * dp[N]
rest_match = N
for i in range(dp[N]):
    for a in a_list:
        if dp[rest_match - match_num[a]] == dp[N] - i - 1:
            rest_match -= match_num[a]
            ans[i] = str(a)
            break
print("".join(ans))