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:
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)))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    A = []
    A_num = {}
    A_num[1] = 2
    A_num[2] = 5
    A_num[3] = 5
    A_num[4] = 4
    A_num[5] = 5
    A_num[6] = 6
    A_num[7] = 3
    A_num[8] = 7
    A_num[9] = 6
    for i in range(M):
        A.append(int(input_raw[i]))

    dp = [0] * (N + 1)
    A.sort(reverse = True)

    for i in range(1, N + 1):
        max_num = -sys.maxint
        for a in A:
            if i - A_num[a] >= 0 and dp[i - A_num[a]] >= 0:
                max_num = max(max_num, dp[i - A_num[a]] + 1)
        dp[i] = max_num

    remain = N
    s = ""
    for i in range(dp[N]):
        for a in A:
            if dp[remain - A_num[a]] == dp[remain] - 1:
                s += str(a)
                remain = remain - A_num[a]
                break
    print s



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = {}
for a in map(int, input().split()):
    na = needs[a]
    if na in usable:
        usable[na] = max(usable[na], a)
    else:
        usable[na] = a
use_keys = sorted(usable.keys())

dp = [-9] * (n + 1)
dp[0] = 0
for d in range(2, n + 1):
    for u in use_keys:
        du = d - u
        if du < 0:
            break
        dp[d] = max(dp[d], dp[du] + 1)

ans = ''
remain = n
rk = [(str(a), needs[a]) for a in sorted(usable.values(), reverse=True)]
for d in range(dp[n] - 1, -1, -1):
    for a, na in rk:
        if dp[remain - na] == d:
            ans += a
            remain -= na
            break

print(ans)

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = {}
for a in map(int, input().split()):
    na = needs[a]
    if na in usable:
        usable[na] = max(usable[na], a)
    else:
        usable[na] = a
use_keys = sorted(usable.keys())

dp = [-9] * (n + 1)
dp[0] = 0
for d in range(2, min(8, n + 1)):
    for u in use_keys:
        du = d - u
        if du < 0:
            break
        dp[d] = max(dp[d], dp[du] + 1)
for d in range(8, n + 1):
    for u in use_keys:
        dp[d] = max(dp[d], dp[d - u] + 1)

ans = ''
remain = n
rk = [(str(a), needs[a]) for a in sorted(usable.values(), reverse=True)]
for d in range(dp[n] - 1, -1, -1):
    for a, na in rk:
        if dp[remain - na] == d:
            ans += a
            remain -= na
            break

print(ans)

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

Solution code:
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)))

Submission status: Runtime Error

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

Num_All={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
Num=list(set([Num_All[a] for a in A]))

Num.sort()
Gyaku={n:0 for n in Num}
for a in A:
    if a>Gyaku[Num_All[a]]:
        Gyaku[Num_All[a]]=a


dp=[ [0,[]] for i in range(N+1)]

for n in Num:
    dp[n]=[ 1,[[n]] ]

for i in range(min(Num),N+1):
    for n in Num:
        if i<n:
            continue
        if dp[i-n][0]>0 and dp[i-n][0]+1>dp[i][0]:
            dp[i]=[ dp[i-n][0]+1,[k+[n] for k in dp[i-n][1]] ]
        elif dp[i-n][0]>0 and dp[i-n][0]+1==dp[i][0]:
            for k in dp[i-n][1]:
                dp[i][1].append(k+[n])

Num_koho=dp[N][1]

Koho=[[Gyaku[k] for k in nk] for nk in Num_koho]
Ans_koho=[]
for k in Koho:
    k.sort(reverse=True)
    Ans_koho.append(sum((10**(len(k)-i-1))*k[i] for i in range(len(k))))
    
print max(Ans_koho)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]

c = list(map(int,input().split()))

c.sort()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [-1 for i in range(a+1)]
dp[0] = 0
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if i-cc[j][1] >= 0 and dp[i-cc[j][1]] >= 0:
			dp[i] = max(dp[i-cc[j][1]]+1,dp[i])
ccc.reverse()
k = a
co = ''
for i in range(dp[a]):
	for j in range(b):
		if dp[k-ccc[j][1]] == dp[k] - 1 and k-ccc[j][1] >= 0:
			co += str(ccc[j][0])
			k -= ccc[j][1]
			break
print(co)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
*A, = map(int, input().split())
 
cost_define = [2,5,5,4,5,6,3,7,6]
 
C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])
 
#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)
 
#余ったら最大桁から増やしていく
res = ""
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (0 < c):
        if (c <= amari):
          n = min(keta, amari // c)
          amari -= (c * n)
          res += str(a) * n
          keta -= n
          found = True
          break
      elif (0 == c):
        found = False
        break
    if not found:
      res += str(min_cost_number) * keta
      keta = 0
      break
  else:
    res += str(min_cost_number) * keta
    keta = 0
    break
  #print(keta, res)
 
#まだ余っていたら最下位から数を減らしてでも本数を使い切る
while (0 < amari):
  tmp_c = 0
  tmp_a = 0
  for (c,a) in zip(C,A):
    c -= min_cost
    if ((0 < c) and (c <= amari) and (amari <= c*(len(res) - keta))):
      #あと勝ち
      if (tmp_c <= c):
      	tmp_c = c
      	tmp_a = a
  n = (amari // tmp_c)
  amari -= (tmp_c * n)
  #print(amari,tmp_c)

  new_res = res[:-(keta+n)] + str(tmp_a)*n
  if (0 < keta):
    new_res += res[-(keta):]
  res = new_res
  keta += n
 
print(res)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]

c = list(map(int,input().split()))

c.sort()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [-1 for i in range(a+1)]
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if dp[i-cc[j][1]] >= 0:
			dp[i] = max(dp[i-cc[j][1]]+1,dp[i])

k = a
co = ''
for i in range(dp[a]):
	for j in range(b):
		if dp[k-ccc[j][1]] == dp[k] and k-ccc[j][1] >= 0:
			co += str(ccc[j][0])
			k -= ccc[j][1]
			break
print(co)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
*A, = map(int, input().split())
 
cost_define = [2,5,5,4,5,6,3,7,6]
 
C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])
 
#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)
 
#余ったら最大桁から増やしていく
res = ""
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (0 < c):
        if (c <= amari):
          n = min(keta, amari // c)
          amari -= (c * n)
          res += str(a) * n
          keta -= n
          found = True
          break
      elif (0 == c):
        found = False
        break
    if not found:
      res += str(min_cost_number) * keta
      keta = 0
      break
  else:
    res += str(min_cost_number) * keta
    keta = 0
    break
  #print(keta, res)
 
#まだ余っていたら最下位から数を減らしてでも本数を使い切る
while (0 < amari):
  tmp_c = 0
  tmp_a = 0
  for (c,a) in zip(C,A):
    c -= min_cost
    if ((c <= amari) and (amari <= c*(len(res) - keta))):
      #あと勝ち
      if (tmp_c <= c):
      	tmp_c = c
      	tmp_a = a
  n = (amari // tmp_c)
  amari -= (tmp_c * n)
  #print(amari,tmp_c)

  new_res = res[:-(keta+n)] + str(tmp_a)*n
  if (0 < keta):
    new_res += res[-(keta):]
  res = new_res
  keta += n
 
print(res)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    if a <= N:
        dp[C[a]] = (1,0)
Z = list( set( C[a] for a in A))
Z.sort()
for i in range(2,N+1):
    for z in Z:
        if i > z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
s = N
ANS = [0]*10
while s != 0:
    _, b = dp[s]
    ANS[s-b] += 1
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans = ans + str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for i in range(M):
    dp[C[A[i]]] = (1,0)
Z = list( set( C[a] for a in A))
Z.sort()
for i in range(2,N+1):
    for z in Z:
        if i > z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
s = N
ANS = [0]*10
while s != 0:
    _, b = dp[s]
    ANS[s-b] += 1
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans = ans + str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

ntom = dict(zip(
        range(1,N+1),
        [2,5,5,4,5,6,3,7,6]
       ))

mtoa = {}
for a in A:
    m = ntom[a]
    mtoa[m] = max(mtoa.get(m, 0), a)

ms = mtoa.keys()
dp = [float('-inf')] * (N+1)
dp[0] = 0
for i in range(min(ms), N+1):
    dp[i] = max(dp[i-x] for x in ms if i >= x) + 1

mms = sorted([(v, m) for m, v in mtoa.items()], reverse=True)
ans = []
left = N
while left:
    for v,m in mms:
        if left >= m and dp[left] == dp[left - m] + 1:
            left -= m
            ans.append(v)
            break
        
print(*ans, sep='')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
*A, = map(int, input().split())
 
cost_define = [2,5,5,4,5,6,3,7,6]
 
C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])
 
#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)
 
#余ったら最大桁から増やしていく
res = ""
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (0 < c):
        if (c <= amari):
          n = min(keta, amari // c)
          amari -= (c * n)
          res += str(a) * n
          keta -= n
          found = True
          break
      elif (0 == c):
        found = False
        break
    if not found:
      res += str(min_cost_number) * keta
      keta = 0
      break
  else:
    res += str(min_cost_number) * keta
    keta = 0
    break
  #print(keta, res)
 
#まだ余っていたら最下位から数を減らしてでも本数を使い切る
while (0 < amari):
  tmp_c = 0
  tmp_a = 0
  for (c,a) in zip(C,A):
    c -= min_cost
    if ((c <= amari) and (amari <= c*len(res))):
      #あと勝ち
      if (tmp_c <= c):
      	tmp_c = c
      	tmp_a = a
  n = (amari // tmp_c)
  amari -= (tmp_c * n)
  #print(amari,tmp_c)

  new_res = res[:-(keta+n)] + str(tmp_a)*n
  if (0 < keta):
    new_res += res[-(keta):]
  res = new_res
  keta += n
 
print(res)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
# Z = list( set( [C[a] for a in A]))
# Z.sort()
# for i in range(2,N+1):
#     for z in Z:
#         if i > z:
#             if dp[i-z][0] == 1:
#                 dp[i] = (1, i-z)
#                 break
# s = N
# ANS = [0]*10
# while s != 0:
#     _, b = dp[s]
#     ANS[s-b] += 1
#     s = b
# ans = ""
# for i in range(9,0,-1):
#     if ANS[C[i]] > 0:
#         if i in A:
#             ans = ans + str(i)*ANS[C[i]]
#             ANS[C[i]] = 0
# print( ans)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]

c = list(map(int,input().split()))

c.sort()
c.reverse()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [-1 for i in range(a+1)]
dp[0] = 0
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if cc[j][1] <= i:
			dp[i] = max(dp[i-cc[j][1]]+1,1,dp[i])

k = a
co = ''
for i in range(dp[a]+2):
	for j in range(b):
		if dp[k-ccc[j][1]] == dp[k]-1:
			co = co + str(ccc[j][0])
			k -= ccc[j][1]
			break
print(co)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
Z = list( set( C[a] for a in A))
Z.sort()

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
Z = list( set( C[a] for a in A))
Z.sort()
for i in range(2,N+1):
    for z in Z:
        if i > z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
print("a")
# s = N
# ANS = [0]*10
# while s != 0:
#     _, b = dp[s]
#     ANS[s-b] += 1
#     s = b
# ans = ""
# for i in range(9,0,-1):
#     if ANS[C[i]] > 0:
#         if i in A:
#             ans = ans + str(i)*ANS[C[i]]
#             ANS[C[i]] = 0
# print( ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))

val = {1 : 2, 2 : 5, 3 : 5, 4 : 4, 5 : 5, 6 : 6, 7 : 3, 8 : 7, 9 : 6}

dp = ['0' for i in range(n+1)]

for i in range(1, n+1):
	for j in a:
		if (i == val[j]):
			dp[i] = str(j)
		elif dp[i-val[j]] != '0':
			if j >= int(dp[i-val[j]][0]):
				temp = str(j) + dp[i-val[j]]
			else:
				temp = dp[i-val[j]] + str(j)
			dp[i] = str(max(int(dp[i]), int(temp)))

print(dp[n])

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]

c = list(map(int,input().split()))

c.sort()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [0 for i in range(a+1)]
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if cc[j][1] <= i:
			dp[i] = max(dp[i-cc[j][1]]+1,1,dp[i])

k = a
co = ''
for i in range(dp[a]+2):
	for j in range(b):
		if dp[k-ccc[j][1]] == dp[k]-1:
			co = str(ccc[j][0]) + co
			k -= ccc[j][1]
			break
print(co)

Submission status: Runtime Error

Solution code:
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

inf = float('inf')
match = (inf, 2, 5, 5, 4, 5, 6, 3, 7, 6)
matnum = set([match[a] for a in A])
dp = [0]+[-inf]*N

for i in range(1, N+1):
    dp[i] = max([10*dp[i-match[a]] + a for a in A])

print(''.join(sorted(str(dp[-1]), reverse = True)))

Submission status: Runtime Error

Solution code:
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

inf = float('inf')
match = (inf, 2, 5, 5, 4, 5, 6, 3, 7, 6)
matnum = set([match[a] for a in A])
dp = [0]+[-inf]*N

for i in range(1, N+1):
    dp[i] = max([10*dp[i-a] + a for a in A])

print(''.join(sorted(str(dp[-1]), reverse = True)))

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]

c = list(map(int,input().split()))

c.sort()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [-1 for i in range(a+1)]
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if cc[j][1] <= i:
			dp[i] = max(dp[i-cc[j][1]]+1,1,dp[i])

k = a
co = ''
for i in range(dp[a]):
	for j in range(b):
		if dp[k-ccc[j][1]] == dp[k]-1:
			co = str(ccc[j][0]) + co
			k -= ccc[j][1]
			break
print(co)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
using namespace std;

int N,M;
int A[10],num[10] = {0,2,5,5,4,5,6,3,7,6};
vector<int> B;
vector<string> v;

void dfs(int n,string S){
	if(n==0) v.push_back(S);
	else{
		for(int i=0;i<(int) B.size();i++){
			char c = '0'+B[i];
			if(n-num[B[i]]>=0) dfs(n-num[B[i]],S+c);
		}
	}
}

int main(){
	cin >> N >> M;
	int cnt = 100;
	int a;
	for(int i=1;i<=M;i++){
		cin >> A[i];
		if(cnt>=num[A[i]]){
			cnt = num[A[i]];
			a = A[i];
		}
	}
	set<int> s;
	sort(A+1,A+M+1,greater<int>());
	for(int i=1;i<=M;i++){
		if(s.count(num[A[i]])==0){
			B.push_back(A[i]);
			s.insert(num[A[i]]);
		}
	}
	string ans;
	while(N-cnt>=0){
		char c = '0'+a;
		ans = ans+c;
		N -= cnt;
	}
	for(int i=0;i<(int) B.size();i++){
		if(N-num[B[i]]==0){
			char c = '0'+B[i];
			if(B[i]>a) ans = c+ans;
			else ans = ans + c;
			cout << ans << endl;
			return 0;
		}
	}
	string now = ans;
	int l = ans.size();
	ans = "";
	int c = 0;
	while(c<=min(l-1,7)){
		now.erase(now.begin()+(int) now.size()-1);
		c++;
		N += cnt;
		dfs(N,"");
		for(int i=0;i<(int) v.size();i++){
			string s1 = now+v[i],s2 = v[i]+now;
			if(ans.size()>s1.size()) continue;
			if(s1>s2 && s1>ans) ans = s1;
			else if(s2>s1 && s2>ans) ans = s2;
		}
		v.clear();
	}
	cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

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

mtoa = {}
for a in A:
    m = ntom[a]
    mtoa[m] = max(mtoa.get(m, 0), a)

ms = mtoa.keys()
dp = [None] * (N+1)
dp[0] = 0
for i in ms:
    dp[i] = 1
for i in range(2, N+1):
    x = [dp[i-x] for x in ms if i > x and dp[i-x]]
    if x:
        dp[i] = max(x) + 1

mms = sorted([(v, m) for m, v in mtoa.items()], reverse=True)
ans = ''
left = N
while left:
    for v,m in mms:
        if left >= m and dp[left - m] is not None and dp[left] == dp[left - m] + 1:
            left -= m
            ans += str(v)
            break
        
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
Z = list( set( C[a] for a in A))
Z.sort()
for i in range(2,N+1):
    for z in Z:
        if i > z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
s = N
ANS = [0]*10
while s != 0:
    _, b = dp[s]
    ANS[s-b] += 1
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans = ans + str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N * 2
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if min(pos, DP[pos], DP[pos] + 1 - DP[i]) >= 0:
            DP[i], ans[i] = DP[pos] + 1, j

S, pos = "", N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
Z = sorted( list( set( C[a] for a in A)))
for i in range(2,N+1):
    for z in Z:
        if i > z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
s = N
ANS = [0]*10
while s != 0:
    _, b = dp[s]
    ANS[s-b] += 1
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans = ans + str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if min(pos, DP[pos], DP[pos] + 1 - DP[i]) >= 0:
            DP[i], ans[i] = DP[pos] + 1, j

S, pos = "", N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
dic = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
a = list(map(int,input().split()))
l=[]
for a_ in a:
    l.append([a_,dic[a_]])
l = sorted(l,key=lambda x:x[1])
dp = [0]*(n+1)
for i in range(len(dp)):
    ind = []
    for j in range(len(l)):
        if l[j][1]<=i:
            ind.append(j)
    for j in ind:
        dp[i] = max(dp[i],dp[i-l[j][1]]+1)
l = sorted(l,key=lambda x:-x[0])
ans = []
key = n
for i in range(dp[n]):
    for k in range(len(l)):
        if dp[key-l[k][1]]==dp[key]-1 and not i==dp[n]-1:
            ans.append(l[k][0])
            key -= l[k][1]
            break
        elif dp[key-l[k][1]]==dp[key]-1 and key-l[k][1]==0:
            ans.append(l[k][0])
            key -= l[k][1]
            break
for i in ans:
    print(i,end="")
print()

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
Z = sorted( list( set( C[a] for a in A)))
for i in range(2,N+1):
    for z in Z:
        if i > z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
s = N
ANS = [0]*10
while s != 0:
    _, b = dp[s]
    ANS[s-b] += 1
    if s == b:
        break
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans += str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split(' '))
ai = 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}

used_numbers = dict()

def evaluate(l):
    if l == None:
        return -9999999999999999999999999999999
    if l == []:
        return 0
    return int(''.join(reversed([str(i) for i in sorted(l)])))

min_maches = min([required_maches[x] for x in ai])
def find(matches_count_to_use):
    if matches_count_to_use not in used_numbers:
        if matches_count_to_use < 0:
            used_numbers[matches_count_to_use] = None
        elif matches_count_to_use == 0:
            used_numbers[matches_count_to_use] = []
        else:
            candidates = list(filter(
                lambda x: find(matches_count_to_use - required_maches[x]) != None, ai))
            if len(candidates) == 0:
                used_numbers[matches_count_to_use] = None
            else:
                number_to_use = max(candidates,
                    key=lambda x: evaluate(find(matches_count_to_use - required_maches[x]) + [x]))
                prev = find(matches_count_to_use - required_maches[number_to_use])
                used_numbers[matches_count_to_use] = prev + [number_to_use]
                
    return used_numbers[matches_count_to_use]
    
print(evaluate(find(n)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from itertools import chain
from functools import reduce, lru_cache
from collections import OrderedDict, Counter, deque

import sys
sys.setrecursionlimit(1024)

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

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

mtoa = {}
for a in A:
    m = ntom[a]
    mtoa.setdefault(m, []).append(a)

ms = mtoa.keys()
dp = [None] * (N+1)
dp[0] = 0
for i in ms:
    dp[i] = 1
for i in range(2, N+1):
    x = [dp[i-x] for x in ms if i > x and dp[i-x]]
    if x:
        dp[i] = max(x) + 1

mms = sorted([(max(y),x) for x, y in mtoa.items()], reverse=True)
ans = ''
left = N
while left:
    for v,m in mms:
        if left >= m and dp[left - m] is not None and  dp[left] == dp[left - m] + 1:
            left -= m
            ans += str(v)
            break
        
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
C = [0,2,5,5,4,5,6,3,7,6]
dp = [(0,0)]*(N+1)
for a in A:
    dp[C[a]] = (1,0)
Z = sorted(list( set( C[a] for a in A)))
for i in range(2,N+1):
    for z in Z:
        if i >= z:
            if dp[i-z][0] == 1:
                dp[i] = (1, i-z)
                break
s = N
ANS = [0]*10
while s != 0:
    _, b = dp[s]
    ANS[s-b] += 1
    if s == b:
        break
    s = b
ans = ""
for i in range(9,0,-1):
    if ANS[C[i]] > 0:
        if i in A:
            ans += str(i)*ANS[C[i]]
            ANS[C[i]] = 0
print( ans)