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 copy import deepcopy
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    l = [2,5,5,4,5,6,3,7,6]
    d = {}
    for i in A:
        if l[i-1] not in d:
            d[l[i-1]] = i
        else:
            if d[l[i-1]] < i:
                d[l[i-1]] = i
    d2 = list(d)
    d2.sort()
    s = [[[-1] * (len(d2)) for _ in range(len(d2))] for _ in range(N+1)]
    dp = [[0] * (len(d2)) for _ in range(N+1)]
    for w in range(N+1):
        if w % d2[0] == 0:
            dp[w][0] = w // d2[0]
            s[w][0] = [0] * (len(d2))
            s[w][0][0] = w // d2[0]
    for i in range(1, len(d2)):
        for w in range(N+1):
            if w < d2[i]:
                continue
            elif max(dp[w-d2[i]]) > 0:
                x = dp[w-d2[i]].index(max(dp[w-d2[i]]))
                if dp[w][i-1] > dp[w-d2[i]][x] + 1:
                    dp[w][i] = dp[w][i-1]
                    s[w][i] = deepcopy(s[w][i-1])
                else:
                    dp[w][i] = dp[w-d2[i]][x] + 1
                    s[w][i] = deepcopy(s[w-d2[i]][x])
                    s[w][i][i] += 1
            elif w == d2[i]:
                dp[w][i] = 1
                s[w][i] = [0] * len(d2)
                s[w][i][i] = 1
            else:
                dp[w][i] = dp[w][i-1]
                s[w][i] = deepcopy(s[w][i-1])
    m = 0
    m2 = 0
    q = 0
    ll = None
    for i in s[-1]:
        if sum(i) > m:
            m = sum(i)
            ll = i
            m2 = 0
            for j, v in enumerate(i):
                if v > 0:
                    m2 += v * d[d2[j]]
                    q = max(q, d[d2[j]])
        elif sum(i) == m:
            m3 = 0
            qt = 0
            for j, v in enumerate(i):
                if v > 0:
                    m3 += v * d[d2[j]]
                    qt = max(q, d[d2[j]])
            if m3 > m2:
                m2 = m3
                ll = i
                q = qt
            elif m3 == m2 and qt > q:
                m2 = m3
                ll = i
                q = qt
    d3 = {}
    for i, v in enumerate(ll):
        if v > 0:
            d3[d[d2[i]]] = v
    d4 = list(d3)
    d4.sort(reverse=True)
    r = ''
    for i in d4:
        r += str(i) * d3[i]
    print(int(r))
main()

Submission status: Wrong Answer

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

def main():
    nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    As = {}
    for a in A:
        As[nums[a]] = max(a, As.get(nums[a], 0))
    A = sorted(list(As.values()), key=lambda x: nums[x])

    def helper(n, A):
        if n == 0:
            return []
        if n < 0:
            return None
        for i in A:
            s = helper(n - nums[i], A)
            if s is None:
                continue
            return s + [i]
        return None
            
    print(''.join(str(i) for i in sorted(helper(N, A), reverse=True)))

main()

Submission status: Wrong Answer

Solution code:
required_match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

def solve():
  N,M = map(int, input().split())
  A = list(map(int, input().split()))
  A.sort(reverse=True)
  w = [required_match[a] for a in A]
  # print(A,w)
  dp = [[0 for _ in range(N+1)] for _ in range(M+1)]
  for i in range(0, M):
    for j in range(1, N+1):
      if j < w[i]:
        dp[i+1][j] = dp[i][j]
      elif j-w[i] == 0 or dp[i+1][j-w[i]] >= 1:
        dp[i+1][j] = max(dp[i][j], dp[i+1][j-w[i]]+1) # 後ろにつけたら自動で辞書順にされてる
      else:
        dp[i+1][j] = dp[i][j]
  
  # print(dp)
  # print(dp[M][N])
  # DPテーブルの右側でdp[M][N]になっているものを分解して、最大のものを選ぶ  高々9*N回で終わる
  start_M = M
  candidate = []
  while dp[start_M][N] == dp[M][N]: 
    # O(9)
    m = start_M
    n = N
    ret = ''
    while n > 0:
      # 左に移動する
      if n - w[m-1] < 0:
        break
      if dp[m][n] == dp[m][n-w[m-1]]+1:
        ret = str(A[m-1])+ret
        n = n-w[m-1]
      else:
        break
      
      # 上に移動する
      while m >= 1 and dp[m][n] == dp[m-1][n]:
        m -= 1

      # print(dp[m][n], dp[m-1][n])
      # print(m, n, ret)

    if n == 0:
      candidate.append(ret)

    start_M -= 1
  # print(candidate)
  print(max(candidate))
  
solve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

num=[inf,2,5,5,4,5,6,3,7,6]

n,m=LI()
a=sorted(LI())[::-1]
set_a=set(str(a))
num_av=[num[i] for i in a]
mm=min(num_av)
for i in a:
    if mm==num[i]:
        max_a=i
        break


def chodo(x):
    pos=[0]*100
    for i in range(1,x+1):
        cnt=0
        for j in str(i):
            if j not in set_a:
                cnt=inf
                break
            cnt+=num[int(j)]
        if cnt!=inf:
            pos[cnt]=max(pos[cnt],i)
    return pos

C=chodo(2000000)

t=n//num[max_a]
r=n%num[max_a]

if r==0:
    ans=str(max_a)*t
else:
    for i in range(100):
        T=t-i
        R=r+i*num[max_a]
        if C[R]==0:
            continue
        else:
            q=[str(max_a)]*T+[x for x in str(C[R])]
            ans=''.join(sorted(q)[::-1])
            break

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

num=[inf,2,5,5,4,5,6,3,7,6]

n,m=LI()
a=sorted(LI())[::-1]
set_a=set(str(a))
num_av=[num[i] for i in a]
mm=min(num_av)
for i in a:
    if mm==num[i]:
        max_a=i
        break


def chodo(x):
    pos=[0]*100
    for i in range(1,x+1):
        cnt=0
        for j in str(i):
            if j not in set_a:
                cnt=inf
                break
            cnt+=num[int(j)]
        if cnt!=inf:
            pos[cnt]=max(pos[cnt],i)
    return pos

C=chodo(100000)

t=n//num[max_a]
r=n%num[max_a]

if r==0:
    ans=str(max_a)*t
else:
    for i in range(100):
        T=t-i
        R=r+i*num[max_a]
        if C[R]==0:
            continue
        else:
            q=[str(max_a)]*T+[x for x in str(C[R])]
            ans=''.join(sorted(q)[::-1])
            break

print(ans)

Submission status: Wrong Answer

Solution code:
ntom = {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 = [int(x) for x in input().split()]

A2 = sorted([(ntom[a], a) for a in A])
A3 = [a[1] for a in A2]

if 6 in A3 and 9 in A3:
    A3.remove(6)
if 2 in A3 and (3 in A3 or 5 in A3):
    A3.remove(2)
if 3 in A3 and 5 in A3:
    A3.remove(3)


ans = []
s = 0
while s != N:
    if s < N:
        ans.append(A3[0])
        s += ntom[A3[0]]
    elif s > N:
        while True:
            L = ans.pop()
            s -= ntom[L]
            if L == A3[-1]:
                pass
            else:
                
                ans.append(A3[A3.index(L) + 1])
                s += ntom[A3[A3.index(L) + 1]]
                break

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

Submission status: Wrong Answer

Solution code:
ntom = {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 = [int(x) for x in input().split()]

A2 = sorted([(ntom[a], a) for a in A])
A3 = [a[1] for a in A2]

ans = []
s = 0
while s != N:
    if s < N:
        ans.append(A3[0])
        s += ntom[A3[0]]
    elif s > N:
        while True:
            L = ans.pop()
            s -= ntom[L]
            if L == A3[-1]:
                pass
            else:
                ans.append(A3[A3.index(L) + 1])
                s += ntom[A3[A3.index(L) + 1]]
                break

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

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]#各数に使うマッチ棒の本数
a=[]#使う数字でけ格納するリスト
for i in map(int,input().split()):
    a.append([i,x[i-1]])#数と使う本数をリストで入力
    #ここでタプルにするとソートできない
a.sort(reverse=True)
#tuple(a)#タプルにしても実行時間、メモリーに大きな変化なし
#ソートしないと、大きい数字が先に来ないので間違う
#(OK)print(a)使える数字だけ
dp=[0]*(n+1)
#dp[i]：ちょうどi本使った時に表せる最大の数
#ループの順番が、いまひとつ、腑に落ちない
#大きい数字から先に試す。マッチの本数は徐々に増やす。
for i in range(m):
#外側ループが使用できる数、最初１番大きい数字、その後、使える数字が増える
    #print(i)
    for j in range(n+1):#マッチ棒は0からnまで使える
        #print(j,dp[j])
        if j==0 or dp[j]!=0:
        #(NG)if dp[j]!=0: 「jの範囲を1始め」でもNG
            if j+a[i][1]<=n:#マッチ棒が使用範囲内なら
                print(dp[j+a[i][1]],dp[j]*10+a[i][0])
                #print(max(dp[j+a[i][1]],dp[j]*10+a[i][0]))
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
#この更新はDP典型。右１項が左と同じ。右は両項とも、前から使っているj本に
#新しく使うi番目を使った　本数での数を表している。
print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]#各数に使うマッチ棒の本数
a=[]#使う数字でけ格納するリスト
for i in map(int,input().split()):
    a.append([i,x[i-1]])#数と使う本数をリストで入力
    #ここでタプルにするとソートできない
a.sort(reverse=True)
#tuple(a)#タプルにしても実行時間、メモリーに大きな変化なし
#ソートしないと、大きい数字が先に来ないので間違う
#(OK)print(a)使える数字だけ
dp=[0]*(n+1)
#dp[i]：ちょうどi本使った時に表せる最大の数
#ループの順番が、いまひとつ、腑に落ちない
for i in range(m):
#外側ループが使用できる数、最初１番大きい数字、その後、使える数字が増える
    for j in range(n+1):#マッチ棒は0からnまで使える
        if j==0 or dp[j]!=0:
        #(NG)if dp[j]!=0: 「jの範囲を1始め」でもNG
            if j+a[i][1]<=n:#マッチ棒が使用範囲内なら
                print(dp[j+a[i][1]],dp[j]*10+a[i][0])
                #print(max(dp[j+a[i][1]],dp[j]*10+a[i][0]))
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
#この更新はDP典型。右１項が左と同じ。右は両項とも、前から使っているj本に
#新しく使うi番目を使った　本数での数を表している。
print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]#各数に使うマッチ棒の本数
a=[]#使う数字でけ格納するリスト
for i in map(int,input().split()):
    a.append([i,x[i-1]])#数と使う本数をリストで入力
    #ここでタプルにするとソートできない
a.sort(reverse=True)
tuple(a)
#ソートしないと、大きい数字が先に来ないので間違う
#(OK)print(a)使える数字だけ
dp=[0]*(n+1)
#dp[i]：ちょうどi本使った時に表せる最大の数
#ループの順番が、いまひとつ、腑に落ちない
for i in range(m):#外側ループが使用できる数
    for j in range(n+1):#マッチ棒は0からnまで使える
        if j==0 or dp[j]!=0:
        #(NG)if dp[j]!=0: 「jの範囲を1始め」でもNG
            if j+a[i][1]<=n:#マッチ棒が使用範囲内なら
                print(dp[j+a[i][1]],dp[j]*10+a[i][0])
                #print(max(dp[j+a[i][1]],dp[j]*10+a[i][0]))
                dp[j+a[i][1]]=max(dp[j+a[i][1]],dp[j]*10+a[i][0])
#この更新はDP典型。右１項が左と同じ。右は両項とも、前から使っているj本に
#新しく使うi番目を使った　本数での数を表している。
print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

def solve(k, n, cnt):
    if n==0: return True
    if n<0: return False
    if k >= len(p): return False

    ma = n // p[k][1]

    for c in range(ma, -1, -1):
        cnt[k] = c;
        if (solve(k+1, n-p[k][1]*c, cnt)):
            return True
    cnt[k] = 0;
    return False

sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
a = list()

m = [0,2,5,5,4,5,6,3,7,6]
p = []
for a in map(int, input().split()):
    p.append((a, m[a]))
p.sort(reverse=True)
p.sort(key=itemgetter(1))

cnt = [0] * len(p)
solve(0, n, cnt)

ans = []
for i, c in enumerate(cnt):
    ans += [p[i][0]] * c
ans.sort(reverse=True)
print(''.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
mi=a[0]
for i in range(1,m):
    if mi[1]>a[i][1] or (mi[1]==a[i][1] and a[i][0]>mi[0]):
        mi=a[i]
a=[a[i] for i in range(m) if a[i][0]>=mi[0]]
m=len(a)
b=sorted(a,key=lambda x:x[1])
c=sorted(a,reverse=True)#最後にmi
d1=n//mi[1]#桁数
ans=[mi[0]]*d1
d2=n%mi[1]#後使えるのはどれくらいか
now=0#ansのどこを変えようとしているのか
for i in range(m-1):
    y=d2//(c[i][1]-mi[1])
    if y!=0:
        for j in range(now,now+y):
            ans[j]=c[i][0]
        now+=y
        d2-=(c[i][1]-mi[1])*y
    if d2==0:
        break
cnt=0
for i in range(d1):
    cnt=cnt*10+ans[i]
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[2,5,5,4,5,6,3,7,6]
a=[]
for i in map(int,input().split()):
    a.append([i,x[i-1]])
mi=a[0]
for i in range(1,m):
    if mi[1]>a[i][1] or (mi[1]==a[i][1] and a[i][0]>mi[0]):
        mi=a[i]
a=[a[i] for i in range(m) if a[i][0]>=mi[0]]
m=len(a)
b=sorted(a,key=lambda x:x[1])
c=sorted(a,reverse=True)#最後にmi
d1=n//mi[1]#桁数
ans=[mi[0]]*d1
d2=n%mi[1]#後使えるのはどれくらいか
now=0#ansのどこを変えようとしているのか
for i in range(m-1):
    y=d2//(c[i][1]-mi[1])
    if y!=0:
        for j in range(now,now+y):
            ans[j]=c[i][0]
        now+=y
        d2-=(c[i][1]-mi[1])*y
    if d2==0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:

import queue
from collections import defaultdict
import copy

N,M=map(int,input().split())
A=list(map(int,input().split()))
ma=[2,5,5,4,5,6,3,7,6]
BA=[[0,0] for _ in range(M)] #(必要本数，-1*数字)
for i in range(M):
    BA[i][1]=-1*A[i]
    BA[i][0]=ma[A[i]-1]
    
BA.sort()

#同じ本数使うものを消去
can=[]
ii=0
while ii <len(BA):
    if BA[ii][0] in can:
        BA.pop(ii)
    else:
        can.append(BA[ii][0])
        ii+=1
M=len(BA)#Mの書き換え

diff=[0]*M#数字変更の際に追加で必要な本数
for i in range(M):
    diff[i]=BA[i][0]-BA[0][0]
    BA[i][1]=BA[i][1]*-1#(必要本数，数字)に直しておく

fi=BA[0]###
#BA.sort(key=lambda x: x[1]*-1)#数字の大きいもの順


    
p=[1]*(N+1)
for i in range(N):
    p[i+1]=p[i]*10

#数字のセットL(sort済み)から作れる最大の数値を出力
def set_to_num(L):
    ans=0
    for i in range(len(L)):
        ans+=L[i]*p[i]
    return ans

#2つの配列を合わせる
def make_set(ori,L):
    for i in range(len(L)):
        ori[i]=L[i]
    ori.sort()
    return ori
    

#dd用hash
def make_h(L):
    h=0
    for i in range(len(L)):
        h+=p[i]*L[i]
    return h
    
    
ans=-1
Max_dig=N//fi[0]

for d in range(Max_dig):#減らす桁数
    dig=Max_dig-d
    rem=N-fi[0]*dig
    temp=[fi[1]]*dig
    dd = defaultdict(int)
    q=queue.Queue()
    q.put((rem,[]))#残り本数，入れ替える数字
    
    while not q.empty():
        rem2,L=q.get()
        if rem2==0:
            LL=make_set(temp,L)
            ans=max(ans,set_to_num(LL))
        else:
            for i in range(1,M):#変更候補の数字を見ていく.0番は自身
                if rem2>=diff[i]:
                    LL=copy.deepcopy(L)
                    LL.append(BA[i][1])
                    LL.sort()
                    h=make_h(LL)
                    if dd[h]==0:
                        q.put((rem2-diff[i],LL))
                        dd[h]=1
    if ans!=-1:
        break
        
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [2, 5, 5, 4, 5, 6, 3, 7, 6]
INF = 10 ** 8
C = []
for i in range(1, 10):
    if i in A:
        C.append([B[i - 1], -i])
    else:
        C.append([INF, -i])
C.sort()
t = 0
for idx, (m, a) in enumerate(C):
    if t < m:
        t = m
    else:
        C[idx][0] = INF
C.sort()

cnt = [0] * 9
a1 = C[0][0]
for i1 in range(N // a1, -1, -1):
    cnt[0] = i1
    N2 = N - a1 * i1
    a2 = C[1][0]
    for i2 in range(N2 // a2, -1, -1):
        cnt[1] = i2
        N3 = N2 - a2 * i2
        a3 = C[2][0]
        for i3 in range(N3 // a3, -1, -1):
            cnt[2] = i3
            N4 = N3 - a3 * i3
            a4 = C[3][0]
            for i4 in range(N4 // a4, -1, -1):
                cnt[3] = i4
                N5 = N4 - a4 * i4
                a5 = C[4][0]
                for i5 in range(N5 // a5, -1, -1):
                    cnt[4] = i5
                    N6 = N5 - a5 * i5
                    a6 = C[5][0]
                    for i6 in range(N6 // a6, -1, -1):
                        cnt[5] = i6
                        N7 = N6 - a6 * i6
                        a7 = C[6][0]
                        for i7 in range(N7 // a7, -1, -1):
                            cnt[6] = i7
                            N8 = N7 - a7 * i7
                            a8 = C[7][0]
                            for i8 in range(N8 // a8, -1, -1):
                                cnt[7] = i8
                                N9 = N8 - a8 * i8
                                a9 = C[8][0]
                                for i9 in range(N9 // a9, -1, -1):
                                    cnt[8] = i9
                                    N10 = N9 - a9 * i9
                                    if N10 == 0:
                                        num = []
                                        for k in range(9):
                                            num.append((C[k][1], cnt[k]))
                                        num.sort()
                                        ans = ''
                                        for n, cnt in num:
                                            ans = ans + str(-n) * cnt
                                        print(int(ans))
                                        exit()

Submission status: Wrong Answer

Solution code:
from itertools import product
e = [10,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = sorted(map(int, input().split()))
d = {}
for i in a:
    if e[i] not in d:
        d[e[i]] = i
    elif d[e[i]] < i:
        d[e[i]] = i

dd = sorted([[i[0] + j[0],i[1] * 10 + j[1]] for i,j in product(d.items(), d.items())] + [[k,v] for k,v in d.items()])
d = {}
for k,v in dd:
     if k not in d:
         d[k] = v
     elif d[k] < v:
        d[k] = v
dd = [[k,v] for k,v in sorted(d.items())]
# [print(k,v) for k,v in dd]
# print()
if 2 in d:
    kk = 2
    vv = 1
elif 3 in d:
    kk = 3
    vv = 7
else:
    kk = 10000
    vv = 0
    for match_num,num in dd:
        if kk >= match_num and vv < num:
            kk = match_num
            vv = num
        elif kk * 2 > match_num and vv * len(str(vv)) + vv < num:
            kk = match_num
            vv = num
k = kk * 3
ans = []
while n - kk >= k:
    ans.append(vv)
    n -= kk

vvv = 0
uu = 0
u = 0
# print(ans, n)
for i,j,k in product(dd,dd,dd):
    k_len = len(str(k[1]))
    j_len = len(str(j[1]))
    #if i[0] + j[0] + k[0] == n:
    #    print(i,j,k, i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1])
    if i[0] + j[0] + k[0] == n and i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1] > vvv:
        vvv = i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1]
        uu = i[1] * 10**(j_len) + j[1]
        u = k[1]
    if i[0] + j[0] == n and i[1] * 10**(j_len) + j[1] > vvv:
        vvv = i[1] * 10**(j_len) + j[1]
        uu = i[1]
        u = j[1]
    if i[0] == n and i[1] > vvv:
        vvv = i[1]
        uu = i[1]
if u == 0:
    print(uu)
else:
    tmp = ''.join(map(str, ans)) if ans else ''
    print(str(uu) + tmp + str(u))
    # print(vv,uu,u)

Submission status: Wrong Answer

Solution code:
from itertools import product
e = [10,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = sorted(map(int, input().split()))
d = {}
for i in a:
    if e[i] not in d:
        d[e[i]] = i
    elif d[e[i]] < i:
        d[e[i]] = i

dd = sorted([[i[0] + j[0],i[1] * 10 + j[1]] for i,j in product(d.items(), d.items())] + [[k,v] for k,v in d.items()])
d = {}
for k,v in dd:
     if k not in d:
         d[k] = v
     elif d[k] < v:
        d[k] = v
dd = [[k,v] for k,v in sorted(d.items())]
# [print(k,v) for k,v in dd]
# print()
if 2 in d:
    kk = 2
    vv = 1
elif 3 in d:
    kk = 3
    vv = 7
else:
    kk = 10000
    vv = 0
    for match_num,num in dd:
        if kk > match_num and vv < num:
            kk = match_num
            vv = num
        elif kk * 2 >= match_num and vv * len(str(vv)) + vv < num:
            kk = match_num
            vv = num
k = kk * 3
ans = []
while n - kk >= k:
    ans.append(vv)
    n -= kk

vvv = 0
uu = 0
u = 0
# print(ans, n)
for i,j,k in product(dd,dd,dd):
    k_len = len(str(k[1]))
    j_len = len(str(j[1]))
    #if i[0] + j[0] + k[0] == n:
    #    print(i,j,k, i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1])
    if i[0] + j[0] + k[0] == n and i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1] > vvv:
        vvv = i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1]
        uu = i[1] * 10**(j_len) + j[1]
        u = k[1]
    if i[0] + j[0] == n and i[1] * 10**(j_len) + j[1] > vvv:
        vvv = i[1] * 10**(j_len) + j[1]
        uu = i[1]
        u = j[1]
    if i[0] == n and i[1] > vvv:
        vvv = i[1]
        uu = i[1]
if u == 0:
    print(uu)
else:
    tmp = ''.join(map(str, ans)) if ans else ''
    print(str(uu) + tmp + str(u))
    # print(vv,uu,u)

Submission status: Wrong Answer

Solution code:
from itertools import product
e = [10,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = sorted(map(int, input().split()))
d = {}
for i in a:
    if e[i] not in d:
        d[e[i]] = i
    elif d[e[i]] < i:
        d[e[i]] = i

dd = sorted([[i[0] + j[0],i[1] * 10 + j[1]] for i,j in product(d.items(), d.items())] + [[k,v] for k,v in d.items()])
d = {}
for k,v in dd:
     if k not in d:
         d[k] = v
     elif d[k] < v:
        d[k] = v
dd = [[k,v] for k,v in sorted(d.items())]
# [print(k,v) for k,v in dd]
# print()
if 2 in d:
    kk = 2
    vv = 1
elif 3 in d:
    kk = 3
    vv = 7
else:
    kk = 10000
    vv = 0
    for match_num,num in dd:
        if kk > match_num and vv < num:
            kk = match_num
            vv = num
        elif kk * 2 > match_num and vv * len(str(vv)) + vv < num:
            kk = match_num
            vv = num
k = kk * 3
ans = []
while n - kk >= k:
    ans.append(vv)
    n -= kk

vvv = 0
uu = 0
u = 0
# print(ans, n)
for i,j,k in product(dd,dd,dd):
    k_len = len(str(k[1]))
    j_len = len(str(j[1]))
    #if i[0] + j[0] + k[0] == n:
    #    print(i,j,k, i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1])
    if i[0] + j[0] + k[0] == n and i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1] > vvv:
        vvv = i[1] * 10**(j_len+k_len) + j[1] * 10**k_len + k[1]
        uu = i[1] * 10**(j_len) + j[1]
        u = k[1]
    if i[0] + j[0] == n and i[1] * 10**(j_len) + j[1] > vvv:
        vvv = i[1] * 10**(j_len) + j[1]
        uu = i[1]
        u = j[1]
    if i[0] == n and i[1] > vvv:
        vvv = i[1]
        uu = i[1]
if u == 0:
    print(uu)
else:
    tmp = ''.join(map(str, ans)) if ans else ''
    print(str(uu) + tmp + str(u))
    # print(vv,uu,u)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
A = list(map(int,input().split()))
dec = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
B = [dec[A[i]] for i in range(m)]
B.sort()

dp_keta = [[-1 for _ in range(n+1)] for _ in range(m+1)]
for i in range(m+1):
	dp_keta[i][0] = 0

for i in range(1,m+1):
	for j in range(n+1):
		a = 0
		b = 0
		c = 0

		if j % B[i-1] == 0:
			a = j // B[i-1]
		b = dp_keta[i-1][j]
		if j >= B[i-1] and dp_keta[i-1][j-B[i-1]] != 0:
			c = dp_keta[i-1][j-B[i-1]]+1

		dp_keta[i][j] = max(a,b,c)

cond = dp_keta[-1]
keta = dp_keta[-1][-1]

A.sort(reverse = True)
ans = ""
res = n
for i in range(keta):
	if i == keta-1:
		for num in A:
			if dec[num] == res:
				ans += str(num)
				break
	else:
		for num in A:
			if res - dec[num] >= 0 and cond[res-dec[num]] == keta-i-1:
				ans += str(num)
				res -= dec[num]
				break


print(ans)

Submission status: Wrong Answer

Solution code:
cnt = [0,2,5,5,4,5,6,3,7,6]

n,m = map(int, input().split( ))
a = list(map(int, input().split( )))
a.sort(reverse = True)
main = 0
hon = 10
for ai in a:
    if hon > cnt[ai]:
        main = ai
        hon = cnt[ai]
    elif hon == cnt[ai] and main<ai:
        main = ai
        hon = cnt[ai]

rem = n%hon
dig = n//hon
#print(rem,dig)
while rem:
    for ai in a:
        if rem%cnt[ai] == 0:
            print(str(main)*dig+str(ai)*(rem//cnt[ai]))
            exit()
    rem += hon
    dig -= 1

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
cost = [0,2,5,5,4,5,6,3,7,6]
Acost = []
for i in A:
  Acost.append(cost[i])
micos = min(Acost)
minum = A[Acost.index(micos)]
keta = N // micos
amari = N % micos
ansstr = [minum]*keta
for i in range(keta-1, -1, -1):
  if amari == 0:
    break
  for j in range(len(A)):
    if (Acost[j]-micos)<=amari and A[j]>minum:
      ansstr[i]=A[j]
      amari -= Acost[j]-micos
      break
for i in range(keta):
  if amari == 0:
    break
  for j in range(len(A)):
    cc = 0
    cos = 0
    if (Acost[j]-micos)<=amari and A[j]<minum:
      if Acost[j]>cos:
        cos = Acost[j]
        cc = j
  if cc >0 :
    ansstr[i]=A[cc]
    amari -= Acost[cc]-micos
ans = 0
for i in range(keta):
  ans += ansstr[i] * (10**i)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
cost = [0,2,5,5,4,5,6,3,7,6]
Acost = []
for i in A:
  Acost.append(cost[i])
micos = min(Acost)
minum = A[Acost.index(micos)]
keta = N // micos
amari = N % micos
ansstr = [minum]*keta
print(A,Acost)
for i in range(keta-1, -1, -1):
  if amari == 0:
    break
  for j in range(len(A)):
    if (Acost[j]-micos)<=amari and A[j]>minum:
      ansstr[i]=A[j]
      amari -= Acost[j]-micos
      break
for i in range(keta):
  if amari == 0:
    break
  for j in range(len(A)):
    cc = 0
    cos = 0
#    print(i,j,Acost[j],micos,amari,A[j],minum)
    if (Acost[j]-micos)<=amari and A[j]<minum:
      if Acost[j]>cos:
        cos = Acost[j]
        cc = j
  if cc >0 :
    ansstr[i]=A[cc]
    amari -= Acost[cc]-micos
ans = 0
for i in range(keta):
  ans += ansstr[i] * (10**i)
print(ans)