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:
def mina(t, i, L, cnt, miL):
  t -= i
  cnt += 1
  miL.append(D[i])
  if t == 0:
    return cnt, miL
  elif t < 0:
    return 0, []
  else:
    for i in L:
      cntk, Lis = mina(t, i, L, cnt, miL)
      if cntk != 0:
        return cntk, Lis
    return 0, []

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

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

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

A.sort(reverse = True)
D = {}
L = []
for i in A:
  if t[i - 1] not in D:
    D[t[i - 1]] = i
    L.append(t[i - 1])

L.sort()

Lmin = N // L[0]
Lmod = N % L[0]

F = True
if Lmod != 0:
  while F:
    Lmin -= 1
    Lmod += L[0]
    t = Lmod
    for i in L[1:]:
      cnt, miL = mina(t, i, L[1:], 0, [])
      if cnt != 0:
        F = False
        break
  
Ans = [str(D[L[0]]) for i in range(Lmin)]
if Lmod != 0:
  miL.sort(reverse = True)
  top = []
  und = []
  for i in miL:
    if L[0] < i:
      top.append(str(i))
    else:
      und.append(str(i))
  Ans = top + Ans + und

print("".join(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]

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

USE=[M[a] for a in A]
USE=sorted(set(USE))

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)

i=1
j=1
for ij in range(2,19):
    for i in range(1,ij):
        j=ij-i
        for k in range(1,10):
            for l in range(1,10):
                if i in A and j in A and k in A and l in A and max(k,l)>max(i,j) and counter[i]>0 and counter[j]>0:
                    x=min(counter[i],counter[j])
                    counter[i]-=x
                    counter[j]-=x
                    counter[k]+=x
                    counter[l]+=x

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

print(ANS)

Submission status: Wrong Answer

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

max_vs = [''] * 10001
n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
if 2 in a and (3 in a or 5 in a):
        a.remove(2)
if 3 in a and 5 in a:
        a.remove(5)
if 6 in a and 9 in a:
        a.remove(6)
a.sort()
for i in range(1, n + 1):
        for v in a:
                if M[v] > i:
                        continue
                elif M[v] == i:
                        if max_vs[i] == '' or int(max_vs[i]) < v:
                                max_vs[i] = str(v)
                else:
                        if max_vs[i - M[v]] != '':
                                if (max_vs[i] == '') or (len(max_vs[i]) < len(str(v) + max_vs[i - M[v]])) or (len(max_vs[i]) == len(str(v) + max_vs[i - M[v]]) and max_vs[i] < str(v) + max_vs[i - M[v]]):
                                        max_vs[i] = str(v) + max_vs[i - M[v]]
print(max_vs[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]

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

USE=[M[a] for a in A]
USE=sorted(set(USE))

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)

i=1
j=1
for ij in range(2,19):
    for i in range(1,ij):
        j=ij-i
        for k in range(1,10):
            for l in range(1,10):
                if i in A and j in A and k in A and l in A and counter[i]>0 and counter[j]>0:
                    x=min(counter[i],counter[j])
                    counter[i]-=x
                    counter[j]-=x
                    counter[k]+=x
                    counter[l]+=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 -*-

from collections import defaultdict
import itertools

def solve():
    t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dt = {0:None, 1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

    n, m = map(int, input().split())
    al = [int(i) for i in input().split()]
    al.sort(reverse=True)
    d = defaultdict(list)
    for i in al:
        d[dt[i]].append(i)
    k = sorted(d.keys())
    ans = ''
    if n % k[0] == 0:
        ans += str(d[k[0]][0]) * (n // k[0])
    else:
        p = n % k[0]
        s = []
        k1 = k[1:]
        for i in range(5, 0, -1):
            if i > len(k1):
                continue
            for j in list(itertools.combinations(k1, i)):
                l = [dt[k] for k in j]
                if p == sum(l) % k[0]:
                    s.append(list(j))
        mt, ma, mx = 10 ** 20, [0] * 5, 0
        for i in s:
            i.sort(reverse=True)
            a = int(''.join([str(d[k][0]) for k in i]))
            if len(ma) > len(i):
                mt = a
                mx = sum([dt[k] for k in i])
                ma = i
            elif ma > i:
                mt = a
                mx = sum([dt[k] for k in i])
                ma = i
        ans += str(mt)
        ans += str(d[k[0]][0]) * ((n - mx) // k[0])
    ans = list(ans)
    ans.sort(reverse=True)
    print(''.join(ans))


if __name__=="__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin
n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]
if 1 in a:
    minm = 2
elif 7 in a:
    minm = 3
elif 4 in a:
    minm = 4
elif 2 in a:
    minm = 5
elif 3 in a:
    minm = 5
elif 5 in a:
    minm = 5
elif 6 in a:
    minm = 6
elif 9 in a:
    minm = 6
elif 8 in a:
    minm = 7
order = n // minm
amari = n % minm
output = ''
for i in range(order):
    amari += minm
    if amari >= 6 and 9 in a:
        output += '9'
        amari -= 6
    elif amari >= 7 and 8 in a:
        output += '8'
        amari -= 7
    elif amari >= 3 and 7 in a:
        output += '7'
        amari -= 3
    elif amari >= 6 and 6 in a:
        output += '6'
        amari -= 6
    elif amari >= 5 and 5 in a:
        output += '5'
        amari -= 5
    elif amari >= 4 and 4 in a:
        output += '4'
        amari -= 4
    elif amari >= 5 and 3 in a:
        output += '3'
        amari -= 5
    elif amari >= 5 and 2 in a:
        output += '2'
        amari -= 5
    elif amari >= 2 and 1 in a:
        output += '1'
        amari -= 2
print(output)

Submission status: Wrong Answer

Solution code:
import sys

match_table = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
search_table = [1, 7, 4, 5, 3, 2, 9, 6, 8]

def main():
    sys.setrecursionlimit(100) # recursion limit hack
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    buf = input()
    buflist = buf.split()
    A = list(sorted(list(map(int, buflist))))
    # remove unnecessary number
    if 2 in A and (3 in A or 5 in A):
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 6 in A and 9 in A:
        A.remove(6)
    # main part
    for i in search_table:
        if i in A:
            extra_number, penalty = generate_extra_number(A, i, N % match_table[i])
            num_to_print = ""
            for j in range(N // match_table[i] - penalty):
                num_to_print += str(i)
            if int(extra_number[0]) >= i:
                num_to_print = extra_number + num_to_print
            else:
                num_to_print = num_to_print + extra_number
            print(num_to_print)
            return

def generate_extra_number(A, main_num, remainder):
    if remainder == 0:
        return str(main_num), 1
    d = match_table[main_num]
    best = 0
    penalty = 99
    digit = 0
    while digit < 5:
        digit += 1
        for i in num_generator(A, digit, ""):
            extra_sum = sum([match_table[int(x)] for x in i])
            if (remainder - extra_sum) % d == 0:
                cand_best = int(i)
                cand_penalty = -(remainder - extra_sum) // d
                if cand_penalty < penalty:
                    best = cand_best
                    penalty = cand_penalty
    return str(best), penalty

def num_generator(A, digit, num):
    if digit == 0:
        yield num
    else:
        for i in reversed(A):
            yield from num_generator(A, digit-1, num + str(i))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import copy

def main():
    n, m = list(map(int, input().split()))
    num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    la = list(map(int, input().split()))
    use = sorted(list(set(num[a] for a in la)))
    convert = {}
    for d in sorted(la):
        convert[num[d]] = d
    dp = [[0, 0, 0, 0, 0, 0, 0] for _ in range(n+10)]
    dp[0][0] = 1
    for i in range(n):
        if dp[i][0] == 0:
            continue
        s1 = sum(dp[i][1:]) + 1
        for dd in sorted(convert.values()):
            d = num[dd]
            tmp = dp[i+d][1:]
            s2 = sum(tmp)
            if s1 >= s2:
                dp[i+d] = copy.deepcopy(dp[i])
                dp[i+d][d-1] += 1
                dp[i+d][0] = 1
    ans = ""
    anss = []
    for i, cnt in enumerate(dp[n][1:]):
        d = i+2
        if cnt == 0:
            continue
        anss.append((convert[d], cnt))
    for d, cnt in sorted(anss, reverse=True):
        ans += str(d) *cnt
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

match_table = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
search_table = [1, 7, 4, 5, 3, 2, 9, 6, 8]

def main():
    sys.setrecursionlimit(100) # recursion limit hack
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    buf = input()
    buflist = buf.split()
    A = list(sorted(list(map(int, buflist))))
    # remove unnecessary number
    if 2 in A and (3 in A or 5 in A):
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 6 in A and 9 in A:
        A.remove(6)
    # main part
    for i in search_table:
        if i in A:
            extra_number, penalty = generate_extra_number(A, i, N % match_table[i])
            num_to_print = ""
            for j in range(N // match_table[i] - penalty):
                num_to_print += str(i)
            if int(extra_number[0]) >= i:
                num_to_print = extra_number + num_to_print
            else:
                num_to_print = num_to_print + extra_number
            print(num_to_print)
            return

def generate_extra_number(A, main_num, remainder):
    if remainder == 0:
        return str(main_num), 1
    d = match_table[main_num]
    best = 0
    penalty = 99
    digit = 0
    while digit < 5:
        digit += 1
        for i in num_generator(A, digit, ""):
            extra_sum = sum([match_table[int(x)] for x in i])
            if (remainder - extra_sum) % d == 0:
                cand_best = int(i)
                cand_penalty = -(remainder - extra_sum) // d
                print(cand_best, cand_penalty)
                if cand_penalty < penalty:
                    best = cand_best
                    penalty = cand_penalty
    return str(best), penalty

def num_generator(A, digit, num):
    if digit == 0:
        yield num
    else:
        for i in reversed(A):
            yield from num_generator(A, digit-1, num + str(i))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input(' ').split(' '))
A = list(map(int,input().split(' ')))
c_all = [2,5,5,4,5,6,3,7,6]

def comp(S,T):
	for s,t in zip(S,T):
		if s < t:
			return True
		if s > t :
			return False
	return True

A.sort()
dic = {i:[] for i in c_all}
cost = []
for n in A:
	dic[c_all[n-1]].append(n)
	if not n in cost:
		cost.append(c_all[n-1])

cost = cost[::-1]
nc = len(cost)

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

for i in range(1,N+1):
	for j, c in enumerate(cost):
		if i - c < 0:
			continue
		#dp[i] = max(dp[i],dp[i-c]+1)
		if dp[i][0] <= dp[i-c][0] +1 :
			temp = [x for x in dp[i-c][1]]
			temp[j]+=1
			if (dp[i][0] < dp[i-c][0]+1) or comp(dp[i][1], temp):
				dp[i] = (dp[i-c][0]+1,temp)

c_ans = dp[N][1]
cand = {}
for i,j in zip(cost,c_ans):
	if j != 0:
		cand[max(dic[i])]=j
ans = ''
for i in range(9,0,-1):
	if i in cand:
		ans += str(i)*cand[i]
print(ans)

Submission status: Wrong Answer

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


N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
cand = [(ai, number[ai]) for ai in A]
cand = sorted(cand, key=lambda x: x[1])


dp = [[[] for i in range(N + 1)] for j in range(M)]

for i in range(N + 1):
    if i % cand[0][1] == 0:
        dp[0][i] = [cand[0][0]] * (i // cand[0][1])

for j in range(1, M):
    for i in range(N + 1):
        key, value = cand[j]
        dp[j][i] = dp[j - 1][i]

        if i == value:
            dp[j][i] = [key]

        if i - value >= 0 and dp[j - 1][i - value] != []:
            temp = [key] + dp[j - 1][i - value]
            temp1 = int("".join(map(str, sorted(temp, reverse=True))))
            temp2 = 0
            if dp[j][i] != []:
                temp2 = int("".join(map(str, sorted(dp[j][i], reverse=True))))
            if temp1 > temp2:
                dp[j][i] = temp


        # temp3 = int("".join(map(str, dp[j][i].sort(reverse=True))))




temp = dp[M - 1][N]
temp.sort(reverse=True)

print("".join(map(str, temp)))

Submission status: Wrong Answer

Solution code:
import numpy as np

costs=np.array([6,2,5,5,4,5,6,3,7,6],dtype=np.int)

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

cost_table = np.vstack((costs[A],A)).transpose()
tb1=np.array(sorted(list(cost_table),key=lambda x:(x[0],-x[1])))
tb2=np.array(sorted(list(cost_table),key=lambda x:(-x[1],x[0])))

c = tb1[0,0]
d = tb1[0,1]
tb1[:,0] -= c
tb2[:,0] -= c

n = N // c
r = N % c

dd = np.ones(n,dtype=np.int)*d

upperlist=[]
lowerlist=[]
while r > 0:
    k = np.where(tb2[:,0] <= r)[0][0]
    if tb2[k,1] > d:
        upperlist.append(tb2[k,1])
        r -= tb2[k,0]
    else:
        k = np.where(tb1[:,0] <= r)[0][-1]
        lowerlist.append(tb1[k,1])
        r -= tb1[k,0]

for u in upperlist:
    print(u,end='')
for i in range(n-len(lowerlist)-len(upperlist)):
    print(dd[i],end='')
for u in lowerlist:
    print(u,end='')

Submission status: Wrong Answer

Solution code:
from sys import stdin

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

n,m = list(map(int, stdin.readline().rstrip().split()))
a = list(map(int, stdin.readline().rstrip().split()))
sorted_a = sorted(a, reverse=True)

uses = [USE[i-1] for i in sorted_a]
min_use = min(uses)
min_use_idx = uses.index(min_use)

uses_left = uses[:min_use_idx]
uses_right = sorted(uses[min_use_idx+1:], reverse=True)

q, mod = divmod(n,min_use)

itr = 0
while (True):
	change = []
	q = q - itr
	mod = mod + min_use*itr
	for i in uses_left:
		if i-min_use == 0:
			continue
		while (True):	
			if mod - (i - min_use) >= 0:
				mod -= i - min_use
				change.append(i)
			else:
				break
	if mod == 0:
		break
	for i in uses_right:
		if i-min_use == 0:
			continue
		while (True):	
			if mod - (i - min_use) >= 0:
				mod -= i - min_use
				change.append(i)
			else:
				break
	if mod == 0:
		break
	itr += 1

ans = [min_use]*(q - len(change))
ans.extend(change)
ans = sorted([sorted_a[uses.index(x)] for x in ans], reverse=True)
print(''.join([ str(x) for x in ans]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(m) for m in input().split()]
a.sort(reverse=True)
dp = []
for i in range(10 * n):
    dp.append(0)

b = [0,2,5,5,4,5,6,3,7,6]
for i in range(1, n + 1):
    for j in range(len(a)):
        if i - b[a[j]] >= 0:
            dp[i] = max(dp[i], dp[i - b[a[j]]] + a[j])
        else:
            pass
    if i != n:
        dp[i] *= 10

print(dp[n])

Submission status: Wrong Answer

Solution code:
def inv(x, ava):
    if x == 2:
        if 1 in ava:
            return 1
        else:
            return -1
    if x == 3:
        if 7 in ava:
            return 7
        else:
            return -1
    if x == 4:
        if 4 in ava:
            return 4
        else:
            return -1
    if x == 5:
        if 5 in ava:
            return 5
        if 3 in ava:
            return 3
        if 2 in ava:
            return 2
        else:
            return -1
    if x == 6:
        if 9 in ava:
            return 9
        if 6 in ava:
            return 6
        else:
            return -1
    if x == 7:
        if 8 in ava:
            return 8
        else:
            return -1
n, m = map(int, input().split())
ava = list(map(int, input().split()))
dp = [[] for _ in range(n+1)]
number = [inv(x,ava) for x in range(2,8)]
avapre = []
for i in range(6):
    if number[i] != -1:
        avapre.append(i+2)
avapresort = sorted(avapre,key = lambda x: number[x-2])
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):
    if i < avapre[0]:
        dp[i] = -1
    else:
        dp[i] = -1
        for pre in avapre:
            if i - pre >= 0:
                dp[i] = max(dp[i], dp[i-pre]+1)
i = n
while(i > 0):
    for pre in avapresort:
        if i - pre >= 0 and dp[i] == dp[i-pre] + 1:
            print(number[pre-2], end='')
            i -= pre
            break
print()

Submission status: Wrong Answer

Solution code:
B=[-1,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
X=sorted([(B[int(i)],-int(i)) for i in input().split()])
Y=[0 for i in range(10)]
dp=[[0 for j in range(N+1)] for i in range(M)]
dp[0][0]=1
dp2=[0 for i in range(N+1)]
for i in range(M-1):
    a=X[i+1][0]
    tmp=[0 for k in range(a)]
    for j in range(N+1):
        if dp[i][j]==1:
            tmp[j%a]=1
        if tmp[j%a]==1:
            dp[i+1][j]=1
            if dp2[j]==0:
                dp2[j]=-X[i+1][1]
#print(dp[M])
t=N%X[0][0]
s=-1
for j in range(t,N+1,X[0][0]):
    if dp[-1][j]==1:
        s=j
        break
#print(dp2)
R=[]
for i in range((N-s)//X[0][0]):
    R.append(-X[0][1])
L=[]
while(s>0):
    L.append(dp2[s])
    s-=B[dp2[s]]
#print(L)
#print(X)
for i in L:
    R.append(i)
#print(Y)
R.sort(reverse=True)
ans=""
for i in R:
    ans=ans+str(i)
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
tik = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[8,7],[6,6]]
dic = {"1":2,"7":3,"4":4,"5":5,"3":5,"2":5,"9":6,"8":7,"6":6}

n,k = map(int, input().split())
x = list(map(int, input().split()))
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    ko = str(q[j][0])
                    dp[i+q[j][1]] = min(str(q[j][0]),str(dp[i+q[j][1]]))

                else:
                    ko = str(dp[i])+str(q[j][0])
                    dp[i+q[j][1]] = min(str(dp[i])+str(q[j][0]), str(dp[i+q[j][1]]))
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(dp[n])
s.sort()
s = s[::-1]
print(''.join(s))

Submission status: Wrong Answer

Solution code:
from collections import OrderedDict
match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}

# n, m = map(int, input().split())
# num_list = map(int, input().split())

# n = 20
# m = 4
# num_list = [3, 7, 8, 4]

n, m = 15, 3
num_list = [5, 4, 6]


# 使う数字選択
num_dict = OrderedDict()
tmp = {val: match[val] for val in num_list}
for k, v in sorted(tmp.items(), key=lambda x: -x[0]):
    if k == 2:
        if 5 in num_dict.keys() or 3 in num_dict.keys():
            continue
    elif k == 3:
        if 5 in num_dict.keys():
            continue
    elif k == 6:
        if 9 in num_dict.keys():
            continue
    num_dict[k] = v

match_dict = OrderedDict()
for k, v in sorted(num_dict.items(), key=lambda x: x[1]):
    match_dict[k] = v

ret_dict = {}
n_match = n
# 桁が割り切れる場合
for k, v in match_dict.items():
    q, mod = divmod(n_match, v)

    if mod == 0:
        ret_dict[k] = q
        break
    else:
        ret_dict[k] = q - 1
        n_match = mod + v

for k, v in sorted(ret_dict.items(), key=lambda x: -x[0]):
    for _ in range(v):
        print("{}".format(k), end="")

Submission status: Wrong Answer

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

[n, m] = list(map(int, input().split(' ')))
available_num_list = list(map(int, input().split(' ')))
available_use_match_list = list(map(lambda x: use_match_list[x - 1], available_num_list))


def find_match_max_num(match_num, count, num_list):
    match_index_list = []
    for _ in range(count):
        start_index = match_index_list[-1] if len(match_index_list) > 0 else -1
        remain_match_index = available_use_match_list.index(match_num, start_index + 1)
        match_index_list.append(remain_match_index)
    return max(list(map(lambda x: num_list[x], match_index_list)))


def calc_min_match(n, m, num_list):
    min_match_count = available_use_match_list.count(min(available_use_match_list))
    main_num = find_match_max_num(min(available_use_match_list), min_match_count, available_num_list)
    main_match = use_match_list[main_num - 1]

    # print(available_use_match_list)
    # print(main_num)
    # print('start\n')

    answer = ''
    if n % main_match == 0:
        answer = str(main_num) * (n // main_match)
        print(answer)
        return

    # １桁見直す
    remain_match = n % main_match + main_match
    remain_match_count = available_use_match_list.count(remain_match)
    if remain_match_count > 0:
        remain_main_num = find_match_max_num(remain_match, min_match_count, available_num_list)
        if main_num > remain_main_num:
            answer = str(main_num) * (n // main_match - 1) + str(remain_main_num)
        else:
            answer = str(remain_main_num) + str(main_num) * (n // main_match - 1)
        # print(remain_main_num)

    print(answer)


calc_min_match(n, m, available_num_list)

Submission status: Wrong Answer

Solution code:
def solve():
    N, M = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    A = sorted(A, reverse=True)

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

    dp = [[0] * (N+1) for _ in range(M+1)]
    prev = [[-1] * (N+1) for _ in range(M+1)]

    for i in range(0, M):
        m = digit_to_num[A[i]]  # match
        for n in range(0, N+1):
            if n - m >= 0:
                if dp[i][n] < dp[i+1][n-m] + 1:
                    dp[i+1][n] = dp[i+1][n-m] + 1
                    prev[i+1][n] = n - m
                else:
                    dp[i+1][n] = dp[i][n]
                    prev[i+1][n] = n
            else:
                dp[i+1][n] = dp[i][n]
                prev[i+1][n] = n
    # print(dp[M][N])

    # hukugen
    n = N
    chosen = []
    # print(dp[M])
    # print(prev[M][N])
    # print(prev[M])

    i = M-1
    while i >= 0:
        # print(i, n, A[i], m)
        m = digit_to_num[A[i]]
        if n == 0:
            chosen.append(A[i])
            break
        if prev[i+1][n] == n-m:
            chosen.append(A[i])
            # print("hit", A[i])
        else:
            i -= 1
        n = prev[i+1][n]

    # print(A)
    chosen = sorted(chosen, reverse=True)
    # print(len(chosen))
    return "".join(map(str, chosen))


def main():
    print(solve())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def usefull(A):
    u = [1, 7, 4, 5, 3, 2, 9, 6, 8]
    for i in u:
        if i in A:
            return i
def parse(inp):
    N, M = map(int, next(inp).split())
    A = list(map(int, next(inp).split()))
    return N, A   

def main(N, A):
    use = [1, 7, 4, 5, 3, 2, 9, 6, 8]
    use = [u for u in use if u in A]
    cost = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    ret = []
    for u in use:
        if cost[u] <= N:
            n = N // cost[u]
            N -= n * cost[u]
            ret = ret + [u] * n
        else:
            break
    for i in range(len(ret)):
        for u in use:
            c = cost[u] - cost[ret[i]]
            if N >= c and u > ret[i]:
                ret[i] = u
                N -= c
                
    for i in range(len(ret)-1, -1, -1):
        for u in sorted(A):
            c = cost[u] - cost[ret[i]]
            if 0 <= c <= N:
                ret[i] = u
                N -= c
                
    print("".join(map(str, ret)))

    
main(*parse(sys.stdin))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
tik = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[8,7],[6,6]]
dic = {"1":2,"7":3,"4":4,"5":5,"3":5,"2":5,"9":6,"8":7,"6":6}

n,k = map(int, input().split())
x = list(map(int, input().split()))
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    ko = str(q[j][0])
                    dp[i+q[j][1]] = max(str(q[j][0]),str(dp[i+q[j][1]]))

                else:
                    ko = str(dp[i])+str(q[j][0])
                    dp[i+q[j][1]] = max(str(dp[i])+str(q[j][0]), str(dp[i+q[j][1]]))
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(dp[n])
s.sort()
s = s[::-1]
print(''.join(s))

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = [int(n) for n in input().split()]
A = sorted([int(n) for n in input().split()])
B = [2, 5, 5, 4, 5, 6, 3, 7, 6]
C = [B[a - 1] for a in A]

keta = N // min(C)

a = ""

for i in range(keta):
    res = N - min(C) * (keta - i)
    if res == 0:
        b = A[C.index(min(C))]
        a += "{}".format(b)
    else:
        if min(C) + res > max(C):
            b = A[C.index(max(C))]
        else:
            c = max([c for c in C if c <= min(C) + res])
            b = A[C.index(c)]
        a += "{}".format(b)

print(a)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input(' ').split(' '))
A = list(map(int,input().split(' ')))
c_all = [2,5,5,4,5,6,3,7,6]

def comp(S,T):
	for s,t in zip(S,T):
		if s < t:
			return True
		if s > t :
			return False
	return True

A.sort()
dic = {i:[] for i in c_all}
cost = []
for n in A:
	dic[c_all[n-1]].append(n)
	if not n in cost:
		cost.append(c_all[n-1])

cost = cost[::-1]
nc = len(cost)

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

for i in range(1,N+1):
	for j, c in enumerate(cost):
		if i - c < 0:
			continue
		#dp[i] = max(dp[i],dp[i-c]+1)
		if dp[i][0] <= dp[i-c][0] +1 :
			temp = [x for x in dp[i-c][1]]
			temp[j]+=1
			if (dp[i][0] < dp[i-c][0]+1) or comp(dp[i][1], temp):
				dp[i] = (dp[i-c][0]+1,temp)

print(dp[N])
c_ans = dp[N][1]
cand = {}
for i,j in zip(cost,c_ans):
	if j != 0:
		cand[max(dic[i])]=j
ans = ''
for i in range(9,0,-1):
	if i in cand:
		ans += str(i)*cand[i]
print(ans)

Submission status: Wrong Answer

Solution code:
mat = [2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(int, input().split()))

yuanzu = []
for i in a:
    yuanzu.append((mat[i-1], i))
yuanzu.sort()

d = []
for i in range(len(yuanzu)-1):
    if yuanzu[i][0] == yuanzu[i+1][0]:
        d.append(yuanzu[i])
for i in d:
    yuanzu.remove(i)
# print(yuanzu)

ans = []
num = [0] * len(yuanzu)

def dfs(depth, s):
    global ans
    if ans:
        return
    if depth >= len(yuanzu):
        return
    if s == 0:
        # print(num)
        ans = num.copy()
        return
    for num[depth] in range(s // yuanzu[depth][0], -1, -1):
        dfs(depth + 1, s - num[depth] * yuanzu[depth][0])
        if ans:
            return
    return


dfs(0, n)
res = []
for i in range(len(ans)):
    res.append((yuanzu[i][1], ans[i]))
res.sort(reverse=True)
print(''.join([str(res[i][0])*res[i][1] for i in range(len(res))]))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
K = [0, 2, 5, 5, 4, 5 ,6, 3, 7, 6]
dp = [[-1,[]]for i in range(50000)]
def clc(B):
    B.sort(reverse=True)
    res = 0
    for b in B:
        res *= 10
        res += b
    return res
for i in range(N):
    for a in A:
        li = dp[i][1].copy()
        li.append(a)
        score = clc(li)
        if dp[i+K[a]][0] < score:
            dp[i+K[a]][1] = li
            dp[i+K[a]][0] = score
print(clc(dp[N][1]))

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
hon=[2,5,5,4,5,6,3,7,6]
a=list(map(int, input().split()))
s=sorted(set([hon[i-1] for i in a]))
t=[0]*10
for i in range(9):
    if i+1 in a:t[hon[i]]=i+1
if len(s)>1:x=s[0]*s[1]+1
else:x=n
dp=[[-100]*(x+1) for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(x+1):
        if j%s[i-1]==0:
            dp[i][j]=max(dp[i][j],j//s[i-1])
        for k in range(1,j+1):
            if (j-k)%s[i-1]==0:
                dp[i][j]=max(dp[i][j],(j-k)//s[i-1]+dp[i-1][k])
ans=[]
if n>x:
    ans+=[min(s)]*-(-(n-x)//min(s))
    n=n+(-(n-x)//min(s))*min(s)
from itertools import product
s2=[s[0]]
s2=[s[0]]
for i in s[1:]:
    for j in s2:
        if i%j==0:
            break
    else:
        s2.append(i)
for i in product(s2,repeat=dp[-1][n]):
    if sum(i)==n:break
ans+=list(i)
import bisect
ansf=[]
for i in ans:
    bisect.insort_left(ansf,t[i])
print(*ansf[::-1],sep='')