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:
N, M = map(int, input().split())
a_list = list(map(int, input().split()))

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
for i in range(2, N + 1):
    for j in range(M):
        if i - items[b_list[j]] >= 2:
            if dp[i - items[b_list[j]]] != 0:
                dp[i] = max(dp[i - items[b_list[j]]] * 10 + b_list[j], dp[i])

print(dp[N])

Submission status: Wrong Answer

Solution code:
arr = [0,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())),key = lambda x:arr[x])
dim = 0
num = 0
min_num = src[0]
for i in src:
    tmp = 1 + (N-arr[i])//arr[min_num]
    if dim <= tmp and num < i:
        dim = tmp
        num = i
s = str(num)
cnt = N - arr[num]
cnt_dim = 1
while(cnt_dim + 1 < dim):
    s += str(min_num)
    cnt -= arr[min_num]
    cnt_dim += 1
for i in src:
    if cnt == arr[i]:
        if i <= min_num:
            s += str(i)
            break
        else:
            s = s[:1] + str(i) + s[1:]
            break
print(s)

Submission status: Wrong Answer

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

setnum = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6} 
rset = {}
for i in a:
    if i in rset:
        if rset[setnum[i]] > i:
            rset[i] = setnum[i]
    else:
        rset[i] = setnum[i]

rset = sorted(rset.items(), reverse=True)
dp = [0] * (n + 1)
for i in rset:
    if n < i[1]:
        continue
    dp[i[1]] = i[0]
    for j in range(i[1], n + 1 - i[1]):
        if dp[j] != 0:
            dp[j + i[1]] = max(dp[j + i[1]], dp[j] * 10 + i[0])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
A = list(map(int, input().split()))
table = defaultdict(int)
for i, cost in zip(range(1, 10), [2,5,5,4,5,6,3,7,6]):
    if i in A:
        table[cost] = max(table[cost], i)
candy = sorted(table)
res = defaultdict(int)
for k in range(len(candy)):
    bits = 1
    for i in candy[k + 1:]:
        bits = bits | (bits << i)
    for i in range(1, len(format(bits, 'b'))):
        if bits & (1 << i):
            if N - i >= 0 and (N - i) % candy[k] == 0:
                res[table[candy[k]]] = ((N - i) // candy[k])
                N = i
                break
    if N == candy[k]:
        res[table[candy[k]]] = 1
        N = 0
#swap
t = min(res[7], res[8])
res[7] -= t
res[8] -= t
res[9] += t
res[4] += t
tmp = []
for i, d in res.items():
    tmp += [i] * d
print(''.join(map(str, sorted(tmp, reverse=True))))

Submission status: Wrong Answer

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

N, M = map(int, input().split())
A = list(input().split())
cands = [(a, numbers[a]) for a in A]

dp = {i: None for i in range(1, N+1)}
for c in cands:
    dp[c[1]] = int(c[0])
for i in range(2, N+1):
    for j in range(2, i):
        if dp[j] is not None and dp[i - j] is not None:
            if dp[i] is None:
                dp[i] = int(''.join(sorted(str(dp[j]) + str(dp[i - j]), reverse=True)))
            else:
                dp[i] = max(dp[i], int(''.join(sorted(str(dp[j]) + str(dp[i - j]), reverse=True))))
print(dp[N])

Submission status: Wrong Answer

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

ans = {2:1, 3 :7, 4:4, 5:5, 6:77, 7:8}

if N <= 7:
    print(ans[N])
    exit()


b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
for i in range(2, N+1):
    for j in range(M):
        if i - items[b_list[j]] >= 0:
                if dp[i - items[b_list[j]]] != 0:
                    dp[i] = max(dp[i - items[b_list[j]]] * 10 + a_list[j], dp[i])

print(dp[N])

Submission status: Wrong Answer

Solution code:
n_dic = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
n,m = map(int,input().split())
l = list(map(int,input().split()))
dic = {}
for i in l:
    if n_dic[i] not in dic or dic[n_dic[i]] < i:
        dic[n_dic[i]] = i
if n % min(dic) == 0:
    ans = str(dic[min(dic)]) * int(n / min(dic))
else:
    ans = str(dic[min(dic)]) * int(n / min(dic))
    sub = n - min(dic) * int(n / min(dic))
    ind = 0
    while sub > 0 and ind < len(ans):
        dif = 0
        v = int(ans[ind])
        for i in range(min(dic) + 1,min(dic) + sub + 1):
            if i in dic and int(dic[i]) > v:
                v = dic[i]
                dif = i - min(dic)
        sub -= dif
        ans = ans[:ind] + str(v) + ans[ind+1:]
        ind += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def check(n, lst):
    for x in lst:
        if n % x == 0:
            return True

    return False
    
N, M = map(int, input().split(' '))

a_lst = list(map(int, input().split(' ')))

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

n_lst = sorted([(dic[a], a) for a in a_lst], key=lambda x: x[0])
n_lst2 = [n for n, a in n_lst]

k_lst = []

for n in n_lst2:
    k = N // n
    N = N % n
    
    if k == 0:
        k_lst.append(k)
        continue
        
    while not check(N, n_lst2):
        N += n
        k -= 1
    k_lst.append(k)
    
nums = []
for i, x in enumerate(n_lst):
    nums.extend(list(str(x[1]) *  k_lst[i]))
    
print(''.join(sorted(nums, reverse=True)))

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]

def match(i):
    ANS=0
    for s in str(i):
        ANS+=M[int(s)]

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

        if len(ANSLIST)>=5:
            print(max(ANSLIST))
            sys.exit()
    elif NOW>N:
        return
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
#print(A)
A.sort(key=lambda x:M[x])
#print(A)

dfs("",0)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

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

b = list(map(int,input().split()))
honsuu = [-1,2,5,5,4,5,6,3,7,6]
enabled = [False] * 10
for bb in b:
    enabled[bb] = True
if (enabled[6] & enabled[9]):
     enabled[6] = False;
if (enabled[5] & (enabled[2] | enabled[3])):
     enabled[2] = enabled[3] = False;
if (enabled[2] & enabled[3]):
     enabled[2] = False

a = []
for i in range(10):
    if (enabled[i]):
        a.append(i)

if enabled[1]:
    if n % 2 == 1:
        if enabled[7]:
            res = "7" + ((n - 3) // 2) * "1"
        elif enabled[5]:
            res = "5" + ((n - 5) // 2) * "1"
        elif enabled[3]:
            res = "3" + ((n - 5) // 2) * "1"
        elif enabled[2]:
            res = "2" + ((n - 5) // 2) * "1"
        else:
            res = "8" + ((n - 7) // 2) * "1"
        print(res)
    else:
        print("1" * (n // 2))
    exit()

if enabled[7]:
    if n % 3 == 1:
        if enabled[4]:
            res = "7" * ((n - 4) // 3) + "4"
        elif enabled[8]:
            res = "8" + "7" * ((n - 7) // 3)
        elif enabled[5]:
            res = "7" * ((n - 10) // 3) + "55"
        elif enabled[3]:
            res = "7" * ((n - 10) // 3) + "33"
        elif enabled[2]:
            res = "7" * ((n - 10) // 3) + "22"
        print(res)
    elif n % 3 == 0:
        print("7" * (n // 3))
    else:
        if enabled[5]:
            res = "7" * ((n - 5) // 3) + "5"
        elif enabled[3]:
            res = "7" * ((n - 5) // 3) + "3"
        elif enabled[2]:
            res = "7" * ((n - 5) // 3) + "2"
        elif enabled[4]:
            res = "7" * ((n - 8) // 3) + "44"
        elif enabled[8]:
            res = "88" + "7" * ((n - 14) // 3)
        print(res)
    exit()

if enabled[4]:
    if n % 4 == 0:
        print("4" * (n // 4))
    elif n % 4 == 1:
        if enabled[5]:
            res = "5" + "4" * ((n - 5) // 4)
        elif enabled[3]:
            res = "4" * ((n - 5) // 4) + "3"
        elif enabled[2]:
            res = "4" * ((n - 5) // 4) + "2"
        elif enabled[8]:
            if enabled[9]:
                res = "98" + ((n - 13) // 4) * "4"
            elif enabled[6]:
                res = "86" + ((n - 13) // 4) * "4"
            else:
                res = "888" + ((n - 21) // 4) * "4"
        print(res)
    elif n % 4 == 2:
        if enabled[9]:
            res = "9" + "4" * ((n - 6) // 4)
        elif enabled[6]:
            res = "6" + "4" * ((n - 6) // 4)
        elif enabled[5]:
            res = "55" + "4" * ((n - 10) // 4)
        elif enabled[3]:
            res = "4" * ((n - 10) // 4) + "33"
        elif enabled[2]:
            res = "4" * ((n - 10) // 4) + "22"
        elif enabled[8]:
            res = "88" + ((n - 14) // 4) * "4"
        print(res)
    else:
        if enabled[8]:
            res = "8" + "4" * ((n - 7) // 4)
        elif enabled[9]:
            if enabled[5]:
                res = "95" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "9" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "9" + "4" * ((n - 11) // 4) + "2"
        elif enabled[6]:
            if enabled[5]:
                res = "65" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "6" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "6" + "4" * ((n - 11) // 4) + "2"
        elif enabled[5]:
            res = "555" + "4" * ((n - 15) // 4)
        elif enabled[3]:
            res = "4" * ((n - 15) // 4) + "333"
        else:
            res = "4" * ((n - 15) // 4) + "222"
        print(res)
    exit()

for i in [5, 3, 2]:
    c = str(i)
    if enabled[i]:
        if n % 5 == 0:
            print(c * (n // 5))
        elif n % 5 == 1:
            if enabled[9]:
                res = "9" + c * ((n - 6) // 5)
            elif enabled[6]:
                res = "6" + c * ((n - 6) // 5)
            else:
                res = "888" + c * ((n - 21) // 5)
            print(res)
        elif n % 5 == 2:
            if enabled[8]:
                res = "8" + c * ((n - 7) // 5)
            elif enabled[9]:
                res = "99" + c * ((n - 12) // 5)
            else:
                res = "66" + c * ((n - 12) // 5)
            print(res)
        elif n % 5 == 3:
            if enabled[9]:
                res = "999" + c * ((n - 18) // 5)
            elif enabled[6]:
                if enabled[8]:
                    res = "86" + c * ((n - 13) // 5)
                else:
                    res = "666" + c * ((n - 18) // 5)
            else:
                res = "8888" + c * ((n - 28) // 5)
            print(res)
        else:
            if enabled[9]:
                res = "9999" + c * ((n - 24) // 5)
            elif enabled[8]:
                res = "88" + c * ((n - 14) // 5)
            else:
                res = "6666" + c * ((n - 24) // 5)
            print(res)
        exit()

for i in [9, 6]:
    c = str(i)
    if enabled[i]:
        if n % 6 == 0:
            print(c * (n // 6))
        elif n % 6 == 1:
            print("8" + c * ((n - 7) // 6))
        elif n % 6 == 2:
            print("88" + c * ((n - 14) // 6))
        elif n % 6 == 3:
            print("888" + c * ((n - 21) // 6))
        elif n % 6 == 4:
            print("8888" + c * ((n - 28) // 6))
        else:
            print("88888" + c * ((n - 35) // 6))
        exit()

print("8" * (n // 7))

Submission status: Wrong Answer

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

Alist = [int(x) for x in input().split()]

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

items = {}
for a in Alist:
    items[a] = matchDict[a]

# 必要マッチ数の少ない順にソート
items = sorted(items.items(), key=lambda x: (x[1], -x[0]))

cache = 0
delList = []
for k, v in items:
    if cache == v:
        delList.append((k,v))
    else:
        cache = v
for x in delList:
    items.remove(x)

# 何桁作る？
mininum, mini = items[0]
keta = N // mini
amari = N % mini

result = str(mininum) * keta
# 余りに応じて数値調整
if amari != 0:
    items = sorted(items, key=lambda x: (x[0], x[1]))

    while True:
        for k,v in items:
            if mininum == k:
                continue
            if v <= mini+amari:
                if k > mininum:
                    result = result[:-1]
                    result = str(k) + result
                elif mininum > k:
                    result = result[:-1] + str(k)
                amari = amari - (v - mini)
        if amari == 0:
            break

print(result)

Submission status: Wrong Answer

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

a = -1
cnt = 100

def check(n,r,S):
	if n==0:
		if r==0:
			return(S)
		else:
			return("no")
	for i in range(len(A)):
		if r-num[A[i]]>=0:
			s = check(n-1,r-num[A[i]],S+str(A[i]))
			if s!="no":
				return(s)
	return("no")

for i in range(len(A)):
	if cnt>=num[A[i]]:
		a = A[i]
		cnt = num[A[i]]
ans = ""
while N-cnt>=0:
	ans = ans+str(a)
	N -= cnt
A.sort()
A.reverse()
for i in range(len(A)):
	if N==num[A[i]]:
		ans = str(A[i])+ans
		N = 0
if N==0:
	print(ans)
else:
	judge = False
	c = 0
	while judge==False:
		ans = ans[:-1]
		c += 1
		N += cnt
		res = check(c,N,"")
		if res!="no":
			ans = res+ans
			judge = True
			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

# honsuu list
ns = []
# honsuu-> disit list
n2d = {}
for a in li:
    ns.append(di[a])
    if di[a] not in n2d or n2d[di[a]] < a:
        n2d[di[a]] = a
ns.sort(reverse=True)

from collections import Counter, deque
cnt = Counter()
Q = deque()
Q.append((tuple(), n))
while len(Q) > 0:
    lis, remain = Q.pop()
    if remain == 0:
        break
    for hon in ns:
        if remain - hon >= 0:
            Q.append((lis + (hon,), remain - hon))

digits = [n2d[n] for n in lis]
digits.sort(reverse=True)

print(*digits, sep='')

Submission status: Wrong Answer

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)


b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
for i in range(2, N+1):
    for j in range(M):
        if i - items[b_list[j]] >= 0:
                if dp[i - items[b_list[j]]] != 0:
                    dp[i] = max(dp[i - items[b_list[j]]] * 10 + a_list[j], dp[i])

print(dp[N])

Submission status: Wrong Answer

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

for i in a:
    L += [ (i, table[i-1]) ]

rm = []

for i in range(len(L)):
    for j in range(i+1, len(L)):
        if L[i][1] == L[j][1]:
            rm += [ min(L[i][0], L[j][0]) ]

for i in a:
    if i not in rm:
        L2 += [ (i, table[i-1]) ]

ans = []
L2.sort(key=lambda x: x[1])

while True:
    if n > L2[0][1]:
        ans += [ L2[0][0] ]
        n -= L2[0][1]
    else:
        break
cnt = 0
cost = L2[0][1]
L2.sort(key=lambda x: -x[1])

while n != 0:
    for i in L2:
        if 1 <= i[1] - cost <= n:
            n -= i[1]
            n += cost 
            ans = ans[1:]
            ans += [ i[0] ]
    # print (ans)

ans.sort(reverse=True)
print ("".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

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

b = list(map(int,input().split()))
honsuu = [-1,2,5,5,4,5,6,3,7,6]
enabled = [False] * 10
for bb in b:
    enabled[bb] = True
if (enabled[6] & enabled[9]):
     enabled[6] = False;
if (enabled[5] & (enabled[2] | enabled[3])):
     enabled[2] = enabled[3] = False;
if (enabled[2] & enabled[3]):
     enabled[2] = False

a = []
for i in range(10):
    if (enabled[i]):
        a.append(i)

if enabled[1]:
    if n % 2 == 1:
        if enabled[7]:
            res = "7" + ((n - 3) // 2) * "1"
        else:
            res = ""
            if enabled[5]:
                res += "5"
            elif enabled[3]:
                res += "3"
            else:
                res += "2"
            res += ((n - 5) // 2) * "1"
        print(res)
    else:
        print("1" * (n // 2))
    exit()

if enabled[7]:
    if n % 3 == 1:
        if enabled[4]:
            res = "7" * ((n - 4) // 3) + "4"
        elif enabled[8]:
            res = "8" + "7" * ((n - 7) // 3)
        elif enabled[5]:
            res = "7" * ((n - 10) // 3) + "55"
        elif enabled[3]:
            res = "7" * ((n - 10) // 3) + "33"
        elif enabled[2]:
            res = "7" * ((n - 10) // 3) + "22"
        print(res)
    elif n % 3 == 0:
        print("7" * (n // 3))
    else:
        if enabled[5]:
            res = "7" * ((n - 5) // 3) + "5"
        elif enabled[3]:
            res = "7" * ((n - 5) // 3) + "3"
        elif enabled[2]:
            res = "7" * ((n - 5) // 3) + "2"
        elif enabled[4]:
            res = "7" * ((n - 8) // 3) + "44"
        elif enabled[8]:
            res = "88" + "7" * ((n - 14) // 3)
        print(res)
    exit()

if enabled[4]:
    if n % 4 == 0:
        print("4" * (n // 4))
    elif n % 4 == 1:
        if enabled[5]:
            res = "5" + "4" * ((n - 5) // 4)
        elif enabled[3]:
            res = "4" * ((n - 5) // 4) + "3"
        elif enabled[2]:
            res = "4" * ((n - 5) // 4) + "2"
        elif enabled[8]:
            if enabled[9]:
                res = "98" + ((n - 13) // 4) * "4"
            elif enabled[6]:
                res = "86" + ((n - 13) // 4) * "4"
            else:
                res = "888" + ((n - 21) // 4) * "4"
        print(res)
    elif n % 4 == 2:
        if enabled[9]:
            res = "9" + "4" * ((n - 6) // 4)
        elif enabled[6]:
            res = "6" + "4" * ((n - 6) // 4)
        elif enabled[5]:
            res = "55" + "4" * ((n - 10) // 4)
        elif enabled[3]:
            res = "4" * ((n - 10) // 4) + "33"
        elif enabled[2]:
            res = "4" * ((n - 10) // 4) + "22"
        elif enabled[8]:
            res = "88" + ((n - 14) // 4) * "4"
        print(res)
    else:
        if enabled[8]:
            res = "8" + "4" * ((n - 7) // 4)
        elif enabled[9]:
            if enabled[5]:
                res = "95" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "9" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "9" + "4" * ((n - 11) // 4) + "2"
        elif enabled[6]:
            if enabled[5]:
                res = "65" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "6" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "6" + "4" * ((n - 11) // 4) + "2"
        elif enabled[5]:
            res = "555" + "4" * ((n - 15) // 4)
        elif enabled[3]:
            res = "4" * ((n - 15) // 4) + "333"
        else:
            res = "4" * ((n - 15) // 4) + "222"
        print(res)
    exit()

for i in [5, 3, 2]:
    c = str(i)
    if enabled[i]:
        if n % 5 == 0:
            print(c * (n // 5))
        elif n % 5 == 1:
            if enabled[9]:
                res = "9" + c * ((n - 6) // 5)
            elif enabled[6]:
                res = "6" + c * ((n - 6) // 5)
            else:
                res = "888" + c * ((n - 21) // 5)
            print(res)
        elif n % 5 == 2:
            if enabled[8]:
                res = "8" + c * ((n - 7) // 5)
            elif enabled[9]:
                res = "99" + c * ((n - 12) // 5)
            else:
                res = "66" + c * ((n - 12) // 5)
            print(res)
        elif n % 5 == 3:
            if enabled[9]:
                res = "999" + c * ((n - 18) // 5)
            elif enabled[6]:
                if enabled[8]:
                    res = "86" + c * ((n - 13) // 5)
                else:
                    res = "666" + c * ((n - 18) // 5)
            else:
                res = "8888" + c * ((n - 28) // 5)
            print(res)
        else:
            if enabled[9]:
                res = "9999" + c * ((n - 24) // 5)
            elif enabled[8]:
                res = "88" + c * ((n - 14) // 5)
            else:
                res = "6666" + c * ((n - 24) // 5)
            print(res)
        exit()

for i in [9, 6]:
    c = str(i)
    if enabled[i]:
        if n % 6 == 0:
            print(c * (n // 6))
        elif n % 6 == 1:
            print("8" + c * ((n - 7) // 6))
        elif n % 6 == 2:
            print("88" + c * ((n - 14) // 6))
        elif n % 6 == 3:
            print("888" + c * ((n - 21) // 6))
        elif n % 6 == 4:
            print("8888" + c * ((n - 28) // 6))
        else:
            print("88888" + c * ((n - 35) // 6))
        exit()

print("8" * (n // 7))

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+1)]
dp[0][0]=1
dp2=[0 for i in range(N+1)]
for i in range(M):
    a=X[i][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]
#print(dp[M])
t=N%X[0][0]
s=-1
for j in range(t,N+1,X[0][0]):
    if dp[M][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:
N, M = map(int, input().split())
A = list(map(int, input().split()))
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)

dp = [[0 for _ in range(10)] for _ in range(N + 1)]
dp2 = [-100 for _ in range(N + 1)]
dp2[0] = 0

for i in range(2, N+1):
    x = -1
    opt = -1
    for a in A:
        c = C[a]
        if i >= c and (dp2[i - c] > opt or (dp2[i - c] == opt and a > x)):
            x = a
            opt = dp2[i - c]
    dp2[i] = dp2[i - C[x]] + 1
    c = C[x]
    for a in A:
        if x == a:
            dp[i][a] = dp[i - c][a] + 1
        else:
            dp[i][a] = dp[i - c][a]

ans = ''.join(str(a) * dp[N][a] for a in sorted(A, reverse=True))
print(ans)

Submission status: Wrong Answer

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

Alist = [int(x) for x in input().split()]

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

items = {}
for a in Alist:
    items[a] = matchDict[a]

# 必要マッチ数の少ない順にソート
items = sorted(items.items(), key=lambda x: (x[1], -x[0]))

cache = 0
delList = []
for k, v in items:
    if cache == v:
        delList.append((k,v))
    else:
        cache = v
for x in delList:
    items.remove(x)

# 何桁作る？
mininum, mini = items[0]
keta = N // mini
amari = N % mini

result = str(mininum) * keta
# 余りに応じて数値調整
if amari != 0:
    items = sorted(items, key=lambda x: (x[0], x[1]))

    for k,v in items:
        if mininum == k:
            continue
        if v <= mini+amari:
            if k > mininum:
                result = result[:-1]
                result = str(k) + result
            elif mininum > k:
                result = result[:-1] + str(k)
            amari = amari - (v - mini)

        if amari == 0:
            break

print(result)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ma = [2,5,5,4,5,6,3,7,6]
lis = list(map(int,input().split()))
mma = [1,7,4,5,3,2,9,6,8]
nuu = [0 for i in range(9)]
ans = ""
if n >= 9:
    for i in range(9):
        if mma[i] in lis:
            nn = n-9
            n = 9
            cou = nn // ma[mma[i]-1]
            n += nn % ma[mma[i]-1]
            nuu[mma[i]-1] += cou
            break
lis.sort(reverse = True)
score = {("",0)}
for i in range(m):
    gone = set()
    for num,nu in score:
        for j in range((n - nu)// ma[lis[i]-1] + 1):
            gone.add((num + str(lis[i]) * j,nu + ma[lis[i]-1] * j))
    score = gone
an = 0
for num,nu in score:
    if nu == n:
        try:
            an = max(an,int(num))
        except:
            continue
for i in range(len(str(an))):
    nuu[int(str(an)[i])-1] += 1
anans = ""
for i in range(9):
    anans += str(9-i) * nuu[-(i+1)]
print(anans)

Submission status: Wrong Answer

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

dp = ["x"] * (n + 1)
dp[0] = ""
for i in range(n):
    for a in aa:
        if i + 1 - NUM[a] >= 0 and dp[i + 1 - NUM[a]] != "x":
            tmp = dp[i + 1 - NUM[a]] + str(a)
            tmp = "".join(sorted(tmp, reverse=True))
            if int(tmp) > (0 if dp[i] == "x" else int(dp[i])):
                dp[i + 1] = tmp
print(dp[n])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
A = list(map(int, input().split()))
table = defaultdict(int)
for i, cost in zip(range(1, 10), [2,5,5,4,5,6,3,7,6]):
    if i in A:
        table[cost] = max(table[cost], i)
candy = sorted(table)

res = []
for k in range(len(candy)):
    bits = 1
    for i in candy[k + 1:]:
        bits = bits | (bits << i)
    for i in range(1, len(format(bits, 'b'))):
        if bits & (1 << i):
            if N - i >= 0 and (N - i) % candy[k] == 0:
                res += [table[candy[k]]] * ((N - i) // candy[k])
                N = i
                break
    if N == candy[k]:
        res += [table[candy[k]]]
        N = 0
print(''.join(map(str, sorted(res, reverse=True))))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
import bisect
import random
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return list(input())
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
a,b = LI()
if b % a == 0:
    print(a+b)
else:
    print(b-a)
"""

#B
"""
n,m = LI()
lis = [0 for i in range(m)]
for i in range(n):
    k = LI()
    for j in k[1:]:
        lis[j-1] += 1
ans = 0
for i in lis:
    if i == n:ans += 1
print(ans)
"""

#C
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = II()
a = LI()
ans = a[0]
for i in range(1,n):
    ans = gcd(ans,a[i])
print(ans)
"""

#D
n,m = LI()
a = LI()
f = [0,2,5,5,4,5,6,3,7,6]
for i in range(m):
    a[i] = [a[i],f[a[i]]]
dp = [[] for i in range(n+10)]
for i in a:
    dp[i[1]] = [i[0]]
for i in range(n+1):
    for j in a:
        if i-j[1] >= 0 and len(dp[i-j[1]]) > 0:
            if len(dp[i]) < len(dp[i-j[1]])+1:
                dp[i] = dp[i-j[1]]+[j[0]]
                dp[i].sort()
                dp[i] = dp[i][::-1]
            else:
                if len(dp[i]) == len(dp[i-j[1]])+1:
                    d = sorted(dp[i-j[1]]+[j[0]])
                    d = d[::-1]
                    k = [dp[i],d]
                    k.sort()
                    if k[1] == d:
                        dp[i] = d
ans = 0
k = 1
l = len(dp[-1])
for i in range(l):
    ans += k*dp[-1][l-i-1]
    k *= 10
print(ans)

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

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

Alist = [int(x) for x in input().split()]

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

items = {}
for a in Alist:
    items[a] = matchDict[a]
# 必要マッチ数の少ない順にソート
items = sorted(items.items(), key=lambda x: (x[1], -x[0]))

# 何桁作る？
mininum, mini = items[0]
keta = N // mini
amari = N % mini

result = str(mininum) * keta
# 余りに応じて数値調整
if amari != 0:
    items = sorted(items, key=lambda x: (x[0], x[1]))

    for k,v in items:
        if mininum == k:
            continue
        if v <= mini+amari:
            if k > mininum:
                result = result[:-1]
                result = str(k) + result
            elif mininum > k:
                result = result[:-1] + str(k)
            amari = amari - (v - mini)

        if amari == 0:
            break

print(result)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ma = [2,5,5,4,5,6,3,7,6]
lis = list(map(int,input().split()))
mma = [1,7,4,5,3,2,9,6,8]
ans = ""
if n >= 9:
    for i in range(9):
        if mma[i] in lis:
            nn = n-9
            n = 9
            cou = nn // ma[mma[i]-1]
            n += nn % ma[mma[i]-1]
            ans += str(mma[i]) * cou
            break
lis.sort(reverse = True)
score = {("",0)}
for i in range(m):
    gone = set()
    for num,nu in score:
        for j in range((n - nu)// ma[lis[i]-1] + 1):
            gone.add((num + str(lis[i]) * j,nu + ma[lis[i]-1] * j))
    score = gone
an = 0
for num,nu in score:
    if nu == n:
        try:
            an = max(an,int(num))
        except:
            continue
s = (ans + str(an))
nuu = [0 for i in range(9)]
for i in range(len(s)):
    nuu[int(s[i])-1] += 1
anans = ""
for i in range(9):
    anans += str(9-i) * nuu[-(i+1)]
print(anans)