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: Wrong Answer

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)
C = g + l

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


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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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,0)]*(N+1)
for a in A:
    if C[a] <= N:
        dp[C[a]] = (1,0,1)
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
for i in range(2,N+1):
    for z in Z:
        if i > z:
            if dp[i-z][0] == 1:
                if dp[i-z][2] + 1 > dp[i][2]:
                    dp[i] = (1, i-z, dp[i-z][2]+1)

s = N
ANS = [0]*10
while s != 0:
    _, b, _ = dp[s]
    ANS[s-b] += 1
    s = b
ans = ""
A.sort( key = None, reverse = True)
for a in A:
    ans = ans + str(a)*ANS[C[a]]
    ANS[C[a]] = 0
print( ans)

Submission status: Wrong Answer

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)

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

Submission status: Wrong Answer

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 C[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 = ""
A.sort( key = None, reverse = True)
for a in A:
    ans = ans + str(a)*ANS[C[a]]
    ANS[C[a]] = 0
print( ans)

Submission status: Wrong Answer

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())
min_need = use_keys[0]
min_use = usable[min_need]
for na in use_keys[1:]:
    if na >= min_need * 2:
        del usable[na]

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)

md = dp[n]
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: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
t = list(map(int, input().split()))

n=s[0]
num=[2,5,5,4,5,6,3,7,6]
aru=[0,0,0,0,0,0,0,0,0,0]
for i in range(len(t)):
    aru[t[i]]+=1

use=[0,0,0,0,0,0,0,0,0]
k1=[2,3,4,5,5,5,6,6,7]
k2=[1,7,4,2,3,5,6,9,8]
for i in range(9):
    if(aru[k2[i]]==1):
        use[k1[i]]=k2[i]

maxd=0
[maxset,settemp]=[[],[]]

for ii in range(6**5):
    i=[(ii%(6**(k+1)))//(6**k) for k in range(5)]
    flag=0
    for i1 in range(5):
        if(i[i1]>0 and use[i1+3]==0):
            flag+=1
    if(flag==0):
        d = 3*i[0]+4*i[1]+5*i[2]+6*i[3]+7*i[4]
        total = d
        for i1 in range(6):
            j=(5-i1)+2
            if((n-total)>=0 and (n-total)%j==0 and use[j]!=0):
                d+=(n-total)//j
                if((n-total)//j > 0):
                    settemp=[use[j] for i2 in range((n-total)//j)]
                else:
                    settemp=[]
                for i3 in range(5):
                    if(i[i3]>0):
                        settemp.extend([use[i3+3] for i2 in range(i[i3])])
        if(maxd<=len(settemp)):
            maxd=len(settemp)
            settemp.sort(reverse=True)
            maxset=settemp
        elif(maxd==len(settemp)):
            settemp.sort(reverse=True)
            for i1 in range(len(settemp)):
                if(maxset[i1]>settemp[i1]):
                    break
                elif(maxset[i1]<settemp[i1]):
                    maxset=settemp
                    maxd=len(settemp)
                    break

ans=""
for i in range(len(maxset)):
    ans+=str(maxset[i])
print(ans)

Submission status: Wrong Answer

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 = 1
  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: Wrong Answer

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 C[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 i in A:
        ans = ans + str(i)*ANS[C[i]]
        ANS[C[i]] = 0
print( ans)

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
t = list(map(int, input().split()))

n=s[0]
num=[2,5,5,4,5,6,3,7,6]
aru=[0,0,0,0,0,0,0,0,0,0]
for i in range(len(t)):
    aru[t[i]]+=1

use=[0,0,0,0,0,0,0,0,0]
k1=[2,3,4,5,5,5,6,6,7]
k2=[1,7,4,2,3,5,6,9,8]
for i in range(9):
    if(aru[k2[i]]==1):
        use[k1[i]]=k2[i]

maxd=0
[maxset,settemp]=[[],[]]

for ii in range(4**5):
    i=[(ii%(4**(k+1)))//(4**k) for k in range(5)]
    flag=0
    for i1 in range(5):
        if(i[i1]>0 and use[i1+3]==0):
            flag+=1
    if(flag==0):
        d = 3*i[0]+4*i[1]+5*i[2]+6*i[3]+7*i[4]
        total = d
        for i1 in range(6):
            j=(5-i1)+2
            if((n-total)>=0 and (n-total)%j==0 and use[j]!=0):
                d+=(n-total)//j
                if((n-total)//j > 0):
                    settemp=[use[j] for i2 in range((n-total)//j)]
                else:
                    settemp=[]
                for i3 in range(5):
                    if(i[i3]>0):
                        settemp.extend([use[i3+3] for i2 in range(i[i3])])
        if(maxd<=len(settemp)):
            maxd=len(settemp)
            settemp.sort(reverse=True)
            maxset=settemp
        elif(maxd==len(settemp)):
            settemp.sort(reverse=True)
            for i1 in range(len(settemp)):
                if(maxset[i1]>settemp[i1]):
                    break
                elif(maxset[i1]<settemp[i1]):
                    maxset=settemp
                    maxd=len(settemp)
                    break

ans=""
for i in range(len(maxset)):
    ans+=str(maxset[i])
print(ans)

Submission status: Wrong Answer

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 C[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: Wrong Answer

Solution code:
s = list(map(int, input().split()))
t = list(map(int, input().split()))

n=s[0]
num=[2,5,5,4,5,6,3,7,6]
aru=[0,0,0,0,0,0,0,0,0,0]
for i in range(len(t)):
    aru[t[i]]+=1

use=[0,0,0,0,0,0,0,0,0]
k1=[2,3,4,5,5,5,6,6,7]
k2=[1,7,4,2,3,5,6,9,8]
for i in range(9):
    if(aru[k2[i]]==1):
        use[k1[i]]=k2[i]

maxd=0
[maxset,settemp]=[[],[]]

for ii in range(3**5):
    i=[(ii%(3**(k+1)))//(3**k) for k in range(5)]
    flag=0
    for i1 in range(5):
        if(i[i1]>0 and use[i1+3]==0):
            flag+=1
    if(flag==0):
        d = 3*i[0]+4*i[1]+5*i[2]+6*i[3]+7*i[4]
        total = d
        for i1 in range(6):
            j=(5-i1)+2
            if((n-total)>=0 and (n-total)%j==0 and use[j]!=0):
                d+=(n-total)//j
                if((n-total)//j > 0):
                    settemp=[use[j] for i2 in range((n-total)//j)]
                else:
                    settemp=[]
                for i3 in range(5):
                    if(i[i3]>0):
                        settemp.extend([use[i3+3] for i2 in range(i[i3])])
        if(maxd<=len(settemp)):
            maxd=len(settemp)
            settemp.sort(reverse=True)
            maxset=settemp
        elif(maxd==len(settemp)):
            settemp.sort(reverse=True)
            for i1 in range(len(settemp)):
                if(maxset[i1]>settemp[i1]):
                    break
                elif(maxset[i1]<settemp[i1]):
                    maxset=settemp
                    maxd=len(settemp)
                    break

ans=""
for i in range(len(maxset)):
    ans+=str(maxset[i])
print(ans)

Submission status: Wrong Answer

Solution code:
s = list(map(int, input().split()))
t = list(map(int, input().split()))

n=s[0]
num=[2,5,5,4,5,6,3,7,6]
aru=[0,0,0,0,0,0,0,0,0,0]
for i in range(len(t)):
    aru[t[i]]+=1

use=[0,0,0,0,0,0,0,0,0]
k1=[2,3,4,5,5,5,6,6,7]
k2=[1,7,4,2,3,5,6,9,8]
for i in range(9):
    if(aru[k2[i]]==1):
        use[k1[i]]=k2[i]

maxd=0
[maxset,settemp]=[[],[]]

for ii in range(3**5):
    i=[(ii%(3**(k+1)))//(3**k) for k in range(5)]
    flag=0
    for i1 in range(5):
        if(i[i1]>0 and use[i1+3]==0):
            flag+=1
    if(flag==0):
        d = 3*i[0]+4*i[1]+5*i[2]+6*i[3]+7*i[4]
        total = d
        for i1 in range(6):
            j=(5-i1)+2
            if((n-total)>=0 and (n-total)%j==0 and use[j]!=0):
                d+=(n-total)//j
                if((n-total)//j > 0):
                    settemp=[use[j] for i2 in range((n-total)//j)]
                else:
                    settemp=[]
                for i3 in range(5):
                    if(i[i3]>0):
                        settemp.extend([use[i3+3] for i2 in range(i[i3])])
        if(maxd<=len(settemp)):
            maxd=len(settemp)
            settemp.sort(reverse=True)
            maxset=settemp
        elif(maxd==len(settemp)):
            settemp.sort(reverse=True)
            for i1 in range(len(settemp)):
                if(maxset[i1]>settemp[i1]):
                    break
                elif(maxset[i1]<settemp[i1]):
                    maxset=settemp
                    maxd=len(settemp)
                    break
                 
print("maxset",maxset)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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

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

match = (0, 2, 5, 5, 4, 5, 6, 3, 7, 6)
dp = [0]+[float('inf')]*N

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

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

Submission status: Wrong Answer

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

#Asの中に同じマッチ棒の数の数字があれば最大のものしか考えない
all_num_match = sorted([(i,j) for i,j in zip(range(1,10),[2,5,5,4,5,6,3,7,6]) if i in As],key=lambda x:(-x[1],-x[0]))
match_num = {}
for tup in all_num_match:
    if tup[1] not in match_num:
        match_num[tup[1]] = tup[0]

#N本のマッチをちょうど使い切る中で数字をたくさん選びたい
#再帰を使って、割り切れたときに戻っていくアルゴリズムにした
def choice_matches(N,matches):
    if matches:
        min_match = matches[0]
        if N % min_match == 0:
            return {min_match: int(N/min_match)}
        else:
            max_digit = N // min_match
            i = max_digit - 1
            while True:
                sub_dic = choice_matches(N - min_match * i,matches[1:])
                if sub_dic:
                    dic = {min_match:i}
                    dic.update(sub_dic)
                    return dic
                else:
                    i -= 1
                    if i < 0:
                        return {}
    else:
        return {}

matches = sorted(list(match_num.keys()))
use_matches = choice_matches(N,matches)
use_matches = sorted([(i,j) for i,j in use_matches.items()],key=lambda x:x[0]) #(マッチの本数,数字の数)

#一番大きい数字から左に並べていく
numbers = sorted([match_num[i] for i,j in use_matches for k in range(j)],reverse=True)
numbers = ''.join([str(i) for i in numbers])
print(numbers)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

INF = 1000000

N,M = map(int, input().split())
match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A = list(map(int, input().split()))

match = {a:match[a] for a in A}

dp = []

for i in range(N+1):
    if i == 0:
        dp.append(0)
    else:
        tmp = [dp[i-m] for m in match.values() if i-m >= 0]
        if tmp == []:
            dp.append(-float('inf'))
        else:
            dp.append(max(tmp)+1)
print(dp)
s = ''
nums = list(match.keys())
nums.sort(reverse=True)
print(nums)
while(True):
    for num in nums:
        if N - match[num] >= 0 and dp[N - match[num]] == dp[N] - 1:
            s = s + str(num)
            N-=match[num]
            break
    if N == 0:
        break

print(s)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

#まず最高何桁の数にできるか考えよう.

SET_A=set(A)

ANSLIST=[0]
def dfs(i,NOW):
    if ANSLIST[0]!=0:
        return
    ANS=0
    if NOW==N:
        L=sorted(list(i),reverse=True)
        #print(L)
        
        ANSLIST[0]=int(("".join(L)))
        return

    elif NOW>N:
        return 
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
A.sort(key=lambda x:M[x])
dfs("",0)

x=ANSLIST[0]
stx=str(x)
from collections import Counter
counter=Counter(stx)


import itertools
for i,j,k in list(itertools.combinations(range(1,10),3)):
    for l,m,n in list(itertools.combinations(range(1,10),3)):
        if i in SET_A and j in SET_A and k in SET_A and l in SET_A and m in SET_A and n in SET_A and M[i]+M[j]+M[k]==M[l]+M[m]+M[n] and \
           counter[str(i)]>0 and counter[str(j)]>0 and counter[str(k)]>0 and (n>k or (n==k and m>j) or (n==k and m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)],counter[str(k)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x
                    counter[str(k)]-=x
                    counter[str(l)]+=x
                    counter[str(m)]+=x
                    counter[str(n)]+=x

for i,j in list(itertools.combinations(range(1,10),2)):
    for l,m in list(itertools.combinations(range(1,10),2)):
        if i in SET_A and j in SET_A and l in SET_A and m in SET_A and M[i]+M[j]==M[l]+M[m] and \
           counter[str(i)]>0 and counter[str(j)]>0 and (m>j or (m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x

                    counter[str(l)]+=x
                    counter[str(m)]+=x



ANS=""
for i in range(9,-1,-1):
    ANS+=str(i)*counter[str(i)]

print(ANS)

Submission status: Wrong Answer

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

num_base = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num_set = set([0])
for i in range(m):
    num_set.add(num_base[a[i]])

def f(x):
    """数xを作るために必要なマッチ棒の本数を返す関数

    :type x: str
    :param x: マッチ棒で作る数
    :rtype: int
    :return: xを作るために必要なマッチ棒の本数
    """

    num_base = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    ret = 0
    for i in range(len(x)):
        ret += num_base[int(x[i])]

    return ret


def max_num(x, y):
    """xとyの大きいほうを返す関数。
    1.文字列の長さが長い方が大きい
    2.文字列の長さが等しいとき、文字列として比較して大きい方が大きい

    :type x: str
    :param x: マッチ棒で作る数
    :type y: str
    :param y: マッチ棒で作る数
    :rtype: str
    :return: 大きい方の数
    """

    if len(x) > len(y):
        return x
    elif len(y) > len(x):
        return y
    else:
        if x > y:
            return x
        else:
            return y


dp = [""] * (n + 1)
for j in range(2, n + 1):
    for i in range(m):
        match = f(str(a[i]))


        if j >= match:
            if j - match <= max(num_set):
                if (j - match) in num_set:
                    dp[j] = max_num(dp[j], dp[j - match] + str(a[i]))
                    dp[j] = max_num(dp[j], str(a[i]) + dp[j - match])
            else:
                dp[j] = max_num(dp[j], dp[j - match] + str(a[i]))
                dp[j] = max_num(dp[j], str(a[i]) + dp[j - match])

print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

#まず最高何桁の数にできるか考えよう.

SET_A=set(A)

ANSLIST=[0]
def dfs(i,NOW):
    if ANSLIST[0]!=0:
        return
    ANS=0
    if NOW==N:
        L=sorted(list(i),reverse=True)
        #print(L)
        
        ANSLIST[0]=int(("".join(L)))
        return

    elif NOW>N:
        return 
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
A.sort(key=lambda x:M[x])
dfs("",0)

x=ANSLIST[0]
stx=str(x)
from collections import Counter
counter=Counter(stx)


import itertools
for i,j,k in list(itertools.combinations(range(1,10),3)):
    for l,m,n in list(itertools.combinations(range(1,10),3)):
        if M[i]+M[j]+M[k]==M[l]+M[m]+M[n] and \
           counter[str(i)]>0 and counter[str(j)]>0 and counter[str(k)]>0 and (n>k or (n==k and m>j) or (n==k and m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)],counter[str(k)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x
                    counter[str(k)]-=x
                    counter[str(l)]+=x
                    counter[str(m)]+=x
                    counter[str(n)]+=x

ANS=""
for i in range(9,-1,-1):
    ANS+=str(i)*counter[str(i)]

print(ANS)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

INF = 1000000

N,M = map(int, input().split())
match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A = list(map(int, input().split()))

match = {a:match[a] for a in A}

dp = []

for i in range(N+1):
    if i == 0:
        dp.append(0)
    else:
        tmp = [dp[i-m] for m in match.values() if i-m >= 0]
        if tmp == []:
            dp.append(-float('inf'))
        else:
            dp.append(max(tmp)+1)

s = ''
nums = list(match.keys())
print(nums)
while(True):
    for num in nums:
        if N - match[num] >= 0 and dp[N - match[num]] == dp[N] - 1:
            s = s + str(num)
            N-=match[num]
            break
    if N == 0:
        break

print(s)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

#まず最高何桁の数にできるか考えよう.

SET_A=set(A)

ANSLIST=[0]
def dfs(i,NOW):
    if ANSLIST[0]!=0:
        return
    ANS=0
    if NOW==N:
        L=sorted(list(i),reverse=True)
        #print(L)
        
        ANSLIST[0]=int(("".join(L)))
        return

    elif NOW>N:
        return 
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
A.sort(key=lambda x:M[x])
dfs("",0)

x=ANSLIST[0]
stx=str(x)
from collections import Counter
counter=Counter(stx)


import itertools
for i,j,k in list(itertools.combinations(range(1,10),3)):
    for l,m,n in list(itertools.combinations(range(1,10),3)):
        if i in SET_A and j in SET_A and k in SET_A and l in SET_A and m in SET_A and n in SET_A and M[i]+M[j]+M[k]==M[l]+M[m]+M[n] and \
           counter[str(i)]>0 and counter[str(j)]>0 and counter[str(k)]>0 and (n>k or (n==k and m>j) or (n==k and m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)],counter[str(k)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x
                    counter[str(k)]-=x
                    counter[str(l)]+=x
                    counter[str(m)]+=x
                    counter[str(n)]+=x

ANS=""
for i in range(9,-1,-1):
    ANS+=str(i)*counter[str(i)]

print(ANS)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

#まず最高何桁の数にできるか考えよう.

SET_A=set(A)

ANSLIST=[0]
def dfs(i,NOW):
    if ANSLIST[0]!=0:
        return
    ANS=0
    if NOW==N:
        L=sorted(list(i),reverse=True)
        #print(L)
        
        ANSLIST[0]=int(("".join(L)))
        return

    elif NOW>N:
        return 
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
A.sort(key=lambda x:M[x])
dfs("",0)

x=ANSLIST[0]
stx=str(x)
from collections import Counter
counter=Counter(stx)


import itertools
for i,j,k in list(itertools.combinations(range(1,10),3)):
    for l,m,n in list(itertools.combinations(range(1,10),3)):
        if i in SET_A and j in SET_A and k in SET_A and l in SET_A and m in SET_A and n in SET_A and max(k,l)>max(i,j) and M[i]+M[j]+M[k]==M[l]+M[m]+M[n] and \
           counter[str(i)]>0 and counter[str(j)]>0 and counter[str(k)]>0 and (n>k or (n==k and m>j) or (n==k and m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)],counter[str(k)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x
                    counter[str(k)]-=x
                    counter[str(l)]+=x
                    counter[str(m)]+=x
                    counter[str(n)]+=x

ANS=""
for i in range(9,-1,-1):
    ANS+=str(i)*counter[str(i)]

print(ANS)

Submission status: Wrong Answer

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

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


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

  costs = list(map(int, input().split()))
  costs = [(c, COSTS[c]) for c in costs]
  costs.sort(key=lambda x:x[1])

  num, cost = costs[0]
  nums = [num] * (remain // cost)
  remain -= cost * len(nums)

  if remain != 0:
    new_costs = []
    exists = set([0])

    for n, c in costs:
      nc = c - cost

      if nc <= remain and nc not in exists:
        new_costs.append((n, nc))

    #max_repeat = min(remain // min(v[1] for v in new_costs), len(nums))
    #rep_nums_list = []

    #for repeat in range(1, max_repeat + 1):
    #  for idxs in itertools.product(range(len(new_costs)), repeat=repeat):
    #    nc = sum(new_costs[i][1] for i in idxs)

    #    if nc != remain:
    #      continue

    #    rep_nums_list.append([new_costs[i][0] for i in idxs])

    #max_nums = [0] * len(nums)

    #for rep_nums in rep_nums_list:
    #  uns = [v for v in rep_nums if v > num]
    #  lns = [v for v in rep_nums if v < num]
    #  new_nums = nums[:]

    #  if len(uns) > 0:
    #    new_nums = uns + new_nums[len(uns):]

    #  if len(lns) > 0:
    #    new_nums = new_nums[:-len(lns)] + lns

    #  if new_nums > max_nums:
    #    max_nums = new_nums

    #nums = max_nums

  print(''.join(str(v) for v in nums), flush=True)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ucost = set([cost[a] for a in A])

DP = [-1000000]*(N+1)
for a in A:
    if cost[a] <= N:
        DP[cost[a]] = 1

for i in range(N):
    v = DP[i]
    for a in A:
        c = cost[a]
        if i + c > N:
            break
        DP[i+c] = max(DP[i+c], v+1)
DP[0] = 0
rA = A[::-1]


t = N
ans = 0
while t:
    for a in rA:
        if t - cost[a] < 0:
            continue
        if DP[t] == DP[t - cost[a]] + 1:
            ans = 10*ans + a
            t -= cost[a]
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
li = list(map(int, input().split()))
di = {}
for i, d in enumerate([2,5,5,4,5,6,3,7,6], 1):
    di[i] = d
li.sort(reverse=True)
hons = set(di[a] for a in li)
dd = {}
for a in li:
    hon = di[a]
    if hon not in dd:
        dd[hon] = a

h2d = [-float('inf')] * (n + 1)
h2d[0] = 0
pre = [None] * (n + 1)
for i in range(1, n + 1):
    for hon in hons:
        if i < hon:
            continue
        dig = h2d[i - hon] + 1
        if dig > h2d[i]:
            h2d[i] = dig
            pre[i] = i - hon

ans = []
while n > 0:
    ans.append(dd[n - pre[n]])
    n = pre[n]
ans.sort(reverse=True)
print(*ans, sep='')

Submission status: Wrong Answer

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

ccc.sort(reverse = True)
p = dp[a]
q = a - cc[0][1]*p
co = [cc[0][0] for i in range(p)]
for i in range(p):
	for j in range(b):
		if ccc[j][0] > cc[0][0] and q >= ccc[j][1] - cc[0][1]:
			co[i] = ccc[j][0]
			q -= ccc[j][1] - cc[0][1]
			break
 
for i in range(p):
	for j in range(b):
		if q >= cc[j][1] - k[co[-(i+1)]-1] and cc[j][1] > k[co[-(i+1)]-1]:
			q -= cc[j][1] - k[co[-(i+1)]-1]
			co[-(i+1)] = cc[j][0]
 
co = map(str,co)
aaa = ''.join(co)
print(aaa)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ucost = set([cost[a] for a in A])

DP = [-1000000]*(N+1)
DP[0] = 0
for a in A:
    if cost[a] <= N:
        DP[cost[a]] = 1

for i in range(N):
    v = DP[i]
    for a in A:
        c = cost[a]
        if i + c > N:
            break
        DP[i+c] = max(DP[i+c], v+1)
rA = A[::-1]


t = N
ans = 0
while t:
    for a in rA:
        if t - cost[a] < 0:
            continue
        if DP[t] == DP[t - cost[a]] + 1:
            ans = 10*ans + a
            t -= cost[a]
            break
print(ans)