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 = [int(x) - 1 for x in input().split()]
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
for a in range(9):
  if a not in A:
    match[a] = 0
match.reverse()
L = []
for m in range(2, 8):
  if m in match:
    L.append([m, 9 - match.index(m)])
DP = [[0, []] for i in range(N + 1)]
for i in range(1, N + 1):
  for m, l in L:
    if i >= m:
      a = DP[i - m][1] + [str(l)]
      b = int(''.join(sorted(a, reverse=True)))
      if b > DP[i][0]:
        DP[i] = [b, a]
print(DP[-1][0])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
numlist = list(map(int, input().split()))
numcost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costlist = []
for i in range(M):
    costlist.append([numlist[i],numcost[numlist[i]-1]])
costlist = sorted(costlist, key = lambda x:(x[1], x[0]))
#print(costlist)
ans = []
sub = N // costlist[0][1]
amari = N % costlist[0][1]
cos = costlist[0][1]
for i in range(sub):
    ans.append(costlist[0][0])
#print(ans, amari)
costlist.pop(0)
while amari != 0:
    ans.pop(-1)
    amari += cos
    #print(amari)
    for i in range(len(costlist)):
        if(amari >= costlist[-(i+1)][1]):
            ans.insert(0, costlist[-(i+1)][0])
            amari -= costlist[-(i+1)][1]
        #print(ans, costlist, amari)
ans.sort(reverse = True)
#print(amari)
print("".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
mt = [2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(str, input().split()))
a.sort(reverse=True)
b = ["", "", "", "", "", ""]
for i in range(m):
    if b[mt[int(a[i])-1] - 2] == "":
        b[mt[int(a[i])-1] - 2] = a[i]
if b[0] == "1":
    if n % 2 == 0:
        print("1" * (n // 2))
    elif b[1] != "":
        print(b[1] + "1" * (n // 2 - 1))
    elif b[3] != "":
        print(b[3] + "1" * (n // 2 - 2))
    else:
        print(b[5] + "1" * (n // 2 - 3))
elif b[1] == "7":
    if n % 3 == 0:
        print("7" * (n // 3))
    elif n % 3 == 1:
        if b[2] != "":
            print("7" * (n // 3 - 1) + "4")
        elif b[5] != "":
            print("8" + "7" * (n // 3 - 2))
        else:
            print("7" * (n // 3 - 3) + b[3] * 2)
    else:
        if b[3] != "":
            print("7" * (n // 3 - 1) + b[3])
        elif b[2] != "":
            print("7" * (n // 3 - 2) + "44")
        else:
            print("88" + "7" * (n // 3 - 4))
elif b[2] != "":
    if n % 4 == 0:
        print("4" * (n // 4))
    elif n % 4 == 1:
        if b[3] != "":
            if b[3] == "5":
                print("5" + "4" * (n // 4 - 1))
            else:
                print("4" * (n // 4 - 1) + b[3])
        elif b[4] == "6":
            print("86" + "4" * (n // 4 - 3))
        elif b[4] == "9":
            print("98" + "4" * (n // 4 - 3))
        else:
            print("888" + "4" * (n // 4 - 5))
    elif n % 4 == 2:
        if b[4] != "":
            print(b[4] + "4" * (n // 4 - 1))
        elif b[3] == "5":
            print("55" + "4" * (n // 4 - 2))
        elif b[3] != "":
            print("4" * (n // 4 - 2) + b[3] * 2)
        else:
            print("88" + "4" * (n // 4 - 3))
    else:
        if b[5] != "":
            print("8" + "4" * (n // 4 - 1))
        elif b[4] != "":
            if b[3] == "5":
                print(b[4] + "5" + "4" * (n // 4 - 2))
            else:
                print(b[4] + "4" * (n // 4 - 2) + b[3])
        elif b[3] == "5":
            print("555" + "4" * (n // 4 - 3))
        else:
            print("4" * (n // 4 - 3) + b[3] * 3)
elif b[3] != "":
    if n % 5 == 0:
        print(b[3] * (n // 5))
    elif n % 5 == 1:
        if b[4] != "":
            print(b[4] + b[3] * (n // 5 - 1))
        else:
            print(b[5] * 3 + b[3] * (n // 5 - 4))
    elif n % 5 == 2:
        if b[5] != "":
            print(b[5] + b[3] * (n // 5 - 1))
        else:
            print(b[4] * 2 + b[3] * (n // 5 - 2))
    elif n % 5 == 3:
        if b[4] == "":
            print(b[5] * 4 + b[3] * (n // 5 - 5))
        else:
            if b[5] == "":
                print(b[4] * 3 + b[3] * (n // 5 - 3))
            elif b[4] == "6":
                print(b[5] + b[4] + b[3] * (n // 5 - 2))
            else:
                print(b[4] + b[5] + b[3] * (n // 5 - 2))
    else:
        if b[5] != "":
            print("88" + b[3] * (n // 5 - 2))
        else:
            print(b[4] * 4 + b[3] * (n // 5 - 4))
elif b[4] != "":
    if n % 6 == 0:
        print(b[4] * (n // 6))
    elif b[4] == "6":
        print("8" * (n % 6) + "6" * (n // 6 - n % 6))
    else:
        print("9" * (n // 6 - n % 6) + "8" * (n % 6))
else:
    print("8"*(n//7))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n,m = li()
a = list(li())

use = {}
for ai in a:
    if dic[ai] not in use.keys():
        use.update({dic[ai]: ai})
    else:
        dic[ai] = max(dic[ai], ai)
        
# 最大順
desc = {}
edge = {}
for idx, num in enumerate(sorted(use.values(), reverse=True)):
    desc.update({idx: num})
    edge.update({idx: dic[num]})
    
        
# 遷移
INF = float('inf')
dp = [[-INF]*len(use) for _ in range(n+1)]
dp[0] = [0]*len(use)
for i in range(1, n+1):
    for idx in range(len(use)):
        modefied = False
        if i - edge[idx] < 0:
            continue
        
        if sum(dp[i]) < sum(dp[i-edge[idx]])+1:
            dp[i] = dp[i-edge[idx]].copy()
            dp[i][idx] += 1
            
            modefied = True

        elif sum(dp[i]) == sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            
            for orgi, tmpi in zip(dp[i], tmp):
                if orgi == tmpi:
                    continue
                
                elif orgi > tmpi:
                    break
                
                else:
                    dp[i] = tmp.copy()
                    modefied = True
                    break
                
        if modefied:
            break

ans = ""
for num, cnt in zip(desc.values(), dp[-1]):
    ans = ans + str(num)*cnt
    
print(ans)

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]]:
		if(a<A[i]):
			ans = str(A[i])+ans
		else:
			ans = ans+str(A[i])
		N = 0

if N==0:
	print(ans)
else:
	s = ""
	judge = False
	c = 0
	while judge==False:
		b = ans[-1:]
		ans = ans[:-1]
		c += 1
		N += num[int(b)]
		s = b+s
		for i in range(c):
			res = check(i+1,N,"")
			if res!="no":
				if s<res:
					ans = res+ans
				else:
					ans = ans+res
				judge = True
				break;
print(ans)

Submission status: Wrong Answer

Solution code:
import collections 

n, m = [int(s) for s in input().split()]
alist = [int(s) for s in input().split()]

conv = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
tp = [(1, 2), (2, 5), (3, 5), (4, 4), (5, 5), (6, 6), (7, 3), (8, 7), (9, 6)]
new_tp = []
for e in alist:
    for t in tp:
        if e == t[0]:
           new_tp.append(t)
# print(new_tp)
l = sorted(new_tp, key=lambda x: (-x[1], x[0]))
# l = sorted([conv[i] for i in alist])
# print(l)

stack = [(n, '')]

while len(stack) > 0:
# for i in range(20):
    rest, ans_rev = stack.pop()
    # print(rest, ans_rev)
    if rest == 0:
        print(''.join(sorted(ans_rev, key=lambda x: -int(x))))
        break
    if rest < 0:
        continue
    
    for i, tp in enumerate(l):
        # print(i, tp)
        stack.append((rest - tp[1], str(tp[0]) + ans_rev))

Submission status: Wrong Answer

Solution code:
mt = [2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(str, input().split()))
a.sort(reverse=True)
b = ["", "", "", "", "", ""]
for i in range(m):
    if b[mt[int(a[i])-1] - 2] == "":
        b[mt[int(a[i])-1] - 2] = a[i]
print(b)
if b[0] == "1":
    if n % 2 == 0:
        print("1" * (n // 2))
    elif b[1] != "":
        print(b[1] + "1" * (n // 2 - 1))
    elif b[3] != "":
        print(b[3] + "1" * (n // 2 - 2))
    else:
        print(b[5] + "1" * (n // 2 - 3))
elif b[1] == "7":
    if n % 3 == 0:
        print("7" * (n // 3))
    elif n % 3 == 1:
        if b[2] != "":
            print("7" * (n // 3 - 1) + "4")
        elif b[5] != "":
            print("8" + "7" * (n // 3 - 2))
        else:
            print("7" * (n // 3 - 3) + b[3] * 2)
    else:
        if b[3] != "":
            print("7" * (n // 3 - 1) + b[3])
        elif b[2] != "":
            print("7" * (n // 3 - 2) + "44")
        else:
            print("88" + "7" * (n // 3 - 4))
elif b[2] != "":
    if n % 4 == 0:
        print("4" * (n // 4))
    elif n % 4 == 1:
        if b[3] != "":
            if b[3] == "5":
                print("5" + "4" * (n // 4 - 1))
            else:
                print("4" * (n // 4 - 1) + b[3])
        elif b[4] == "6":
            print("86" + "4" * (n // 4 - 3))
        elif b[4] == "9":
            print("98" + "4" * (n // 4 - 3))
        else:
            print("888" + "4" * (n // 4 - 5))
    elif n % 4 == 2:
        if b[4] != "":
            print(b[4] + "4" * (n // 4 - 1))
        elif b[3] == "5":
            print("55" + "4" * (n // 4 - 2))
        elif b[3] != "":
            print("4" * (n // 4 - 2) + b[3] * 2)
        else:
            print("88" + "4" * (n // 4 - 3))
    else:
        if b[5] != "":
            print("8" + "4" * (n // 4 - 1))
        elif b[4] != "":
            if b[3] == "5":
                print(b[4] + "5" + "4" * (n // 4 - 2))
            else:
                print(b[4] + "4" * (n // 4 - 2) + b[3])
        elif b[3] == "5":
            print("555" + "4" * (n // 4 - 3))
        else:
            print("4" * (n // 4 - 3) + b[3] * 3)
elif b[3] != "":
    if n % 5 == 0:
        print(b[3] * (n // 5))
    elif n % 5 == 1:
        if b[4] != "":
            print(b[4] + b[3] * (n // 5 - 1))
        else:
            print(b[5] * 3 + b[3] * (n // 5 - 4))
    elif n % 5 == 2:
        if b[5] != "":
            print(b[5] + b[3] * (n // 5 - 1))
        else:
            print(b[4] * 2 + b[3] * (n // 5 - 2))
    elif n % 5 == 3:
        if b[4] == "":
            print(b[5] * 4 + b[3] * (n // 5 - 5))
        else:
            if b[5] == "":
                print(b[4] * 3 + b[3] * (n // 5 - 3))
            elif b[4] == "6":
                print(b[5] + b[4] + b[3] * (n // 5 - 2))
            else:
                print(b[4] + b[5] + b[3] * (n // 5 - 2))
    else:
        if b[5] != "":
            print("88" + b[3] * (n // 5 - 2))
        else:
            print(b[4] * 4 + b[3] * (n // 5 - 4))
elif b[4] != "":
    if n % 6 == 0:
        print(b[4] * (n // 6))
    elif b[4] == "6":
        print("8" * (n % 6) + "6" * (n // 6 - n % 6))
    else:
        print("9" * (n // 6 - n % 6) + "8" * (n % 6))
else:
    print("8"*(n//7))

Submission status: Wrong Answer

Solution code:
import math


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

MAX_N = int(1e4)
dp = [[-1 for i in range(10)] for i in range(MAX_N + 10)]
for j in range(1, 9 + 1):
    dp[0][j] = 0

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

for i in range(N + 1):
    for j in range(1, 9 + 1):
        if j not in A:
            continue

        if i < mc[j - 1]:
            continue

        for k in range(1, j + 1):
            tmp = dp[i - mc[j - 1]][k]
            if tmp == -1:
                continue
            if tmp == 0:
                dp[i][j] = max(dp[i][j], j)
            else:
                dp[i][j] = max(dp[i][j], tmp * 10 + j, (j * 10 ** (int(math.log10(tmp)) + 1) + tmp))

ans = 0
for j in range(1, 9 + 1):
    ans = max(ans, dp[N][j])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
aaa = list(map(int, input().split()))
pri = sorted((needs[a], -a) for a in aaa)
main_use_need, main_use = pri[0]
main_use = -main_use

use = {}
for u, a in pri:
    if u in use:
        continue
    if main_use_need * 2 <= u:
        continue
    use[u] = -a

dp = defaultdict(lambda: 0)
dp[n] = 0
for a in sorted(use.values(), reverse=True):
    updates = []
    na = needs[a]
    for k, base in dp.items():
        for i in range(1, k // na + 1):
            updates.append((k - na * i, base * (10 ** i) + int(str(a) * i)))
    for k, res in updates:
        dp[k] = max(dp[k], res)
print(dp[0])

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
A=list(map(int,input().split()))
n=[0,2,5,5,4,5,6,3,7,6]
num=[0]*8
for a in A:
    num[n[a]]=max(num[n[a]],a)
nums=[]
for i in range(8):
    if num[i]: nums.append((i,num[i]))

dp=[0]*(N+1)
start=nums[0][0]
for x,y in nums:
    try:
        dp[x]=y
    except IndexError: break
if start==N:
    print(nums[0][1])
    sys.exit()
for i in range(start+1,N+1):
    t=dp[i]
    for x,y in nums:
        if i-x>0:
            if dp[i-x]:
                dp[i]=max([dp[i],int(str(y)+str(dp[i-x])),dp[i-x]*10+y])
    if dp[i]!=0 and (N-i)%start==0: break
#print(i,dp[i])
if i==N: print(dp[N])
else:
    for s in str(dp[i]):
        if int(s)>nums[0][1]:
            print(str(dp[i])+str(nums[0][1])*((N-i)//start))
            sys.exit()
        if int(s)<nums[0][1]:
            print(str(nums[0][1])*((N-i)//start)+str(dp[i]))
            sys.exit()
    print(str(dp[i])+str(nums[0][1])*((N-i)//start))

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 c in cands:
        j = i - c[1]
        if j >= 1 and dp[j] is not None:
            if dp[i] is None:
                dp[i] = int(''.join(str(dp[j]) + c[0]))
            else:
                if len(str(dp[i])) <  len(str(dp[j]) + c[0]):
                    dp[i] = int(str(dp[j]) + c[0])
                elif len(str(dp[i])) ==  len(str(dp[j]) + c[0]):
                    dp[i] = max(dp[i], int(''.join(sorted(str(dp[j]) + c[0], reverse=True))))
print(''.join(sorted(str(dp[N]), reverse=True)))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
li = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[6,6],[8,7]]
use = []
Q = [0]*10
counter = 0
for i in li:
    if i[0] in A:
        use.append(i)
Q[use[0][0]] = (int(N//use[0][1]))
R = N%use[0][1]
while R != 0:
    if Q[use[counter][0]] == 0 or counter >= M-1:
        counter -= 1
    else:
        Q[use[counter][0]] -= 1
        R += use[counter][1]
        counter += 1
        Q[use[counter][0]] = int(R//use[counter][1])
        R = R%use[counter][1]
ans = ''
for i in [9,8,7,6,5,4,3,2,1]:
    ans = ans + str(i)*Q[i]
print(ans)

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(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 + b_list[j], dp[i])
print(dp[N])

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[9]:
                res = "99" + c * ((n - 12) // 5)
            elif enabled[8]:
                res = "8" + c * ((n - 7) // 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()

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

if enabled[6]:
    c = "6"
    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:
import collections 

n, m = [int(s) for s in input().split()]
alist = [int(s) for s in input().split()]

conv = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
tp = [(1, 2), (2, 5), (3, 5), (4, 4), (5, 5), (6, 6), (7, 3), (8, 7), (9, 6)]
new_tp = []
for e in alist:
    for t in tp:
        if e == t[0]:
           new_tp.append(t)
# print(new_tp)
l = sorted(new_tp, key=lambda x: (-x[1], -x[0]))
# l = sorted([conv[i] for i in alist])
# print(l)

stack = [(n, '')]

while len(stack) > 0:
# for i in range(20):
    rest, ans_rev = stack.pop()
    # print(rest, ans_rev)
    if rest == 0:
        print(''.join(sorted(ans_rev, key=lambda x: -int(x))))
        break
    if rest < 0:
        continue
    
    for i, tp in enumerate(l):
        # print(i, tp)
        stack.append((rest - tp[1], str(tp[0]) + ans_rev))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n,m = li()
a = list(li())

use = {}
for ai in a:
    if dic[ai] not in use.keys():
        use.update({dic[ai]: ai})
    else:
        dic[ai] = max(dic[ai], ai)
        
# 最大順
desc = {}
edge = {}
for idx, num in enumerate(sorted(use.values(), reverse=True)):
    desc.update({idx: num})
    edge.update({idx: dic[num]})
    
        
# 遷移
INF = float('inf')
dp = [[-INF]*len(use) for _ in range(n+1)]
dp[0] = [0]*len(use)
for i in range(1, n+1):
    for idx in range(len(use)):
        if i - edge[idx] < 0:
            continue
        
        if sum(dp[i]) < sum(dp[i-edge[idx]])+1:
            dp[i] = dp[i-edge[idx]].copy()
            dp[i][idx] += 1

        elif sum(dp[i]) == sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            
            for orgi, tmpi in zip(dp[i], tmp):
                if orgi == tmpi:
                    continue
                
                elif orgi > tmpi:
                    break
                
                else:
                    dp[i] = tmp.copy()
                    break

ans = ""
for num, cnt in zip(desc.values(), dp[-1]):
    ans = ans + str(num)*cnt
    
print(ans)

Submission status: Wrong Answer

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

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

match_num=[2,5,5,4,5,6,3,7,6]
match_num2=[]
for a in A:
    match_num2.append([match_num[a-1],a])
match_num2=sorted(match_num2,key=lambda x:x[1],reverse=True)
match_num2=sorted(match_num2,key=lambda x:x[0])

most=match_num2[0][1]
dig_num=N//match_num2[0][0]
dig_res=N%match_num2[0][0]

if dig_res==0:
    print(str(most)*dig_num)
else:
    match_num3=[]
    for i in range(M):
        if match_num2[i][0]>match_num2[0][0]:
            match_num3.append(match_num2[i])
    match_num3.append([match_num2[0][0],most])
    l=len(match_num3)
    res_pattern=[]
    min_dig=min(dig_res,dig_num)
    for i in range(l**min_dig):
        res=""
        r=0
        for j in range(min_dig):
            res+=str(match_num3[(i//(l**j))%l][1])
            r+=match_num3[(i//(l**j))%l][0]
        if r-min_dig*match_num2[0][0]==dig_res:
            res_pattern.append(res)
    max_res=0
    for res in res_pattern:
        max_res=max(int(res),max_res)
    if int(str(max_res)[0])>most:
        print(str(max_res)+str(most)*(dig_num-min_dig))
    else:
        print(str(most)*(dig_num-min_dig)+str(max_res))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
listA=list(map(int, input().split()))
listN=[1, 7, 4, 5, 3, 2, 9, 6, 8]
listM=[2, 3, 4, 5, 5, 5, 6, 6, 7]
index=0
listB=[]
listA2=[]
while index < len(listN):
    if listN[index] in listA:
        if listM[index] in listB:
            pass
        else:
            listB.append(listM[index])#use match number
            listA2.append(listN[index])#simple number
    index+=1
keta = n//listB[0]
if n%listB[0] == 0:
    print(str(listA2[0])*keta)
else:
    amari=n%listB[0]
    index2=1
    flag=1
    while index2 < keta and flag:
        index3=1
        while index3 < len(listB):
            if (amari+listB[0]*index2)%listB[index3]==0:
                number1 = int(str(listA2[index3]) *
                              index2+str(listA2[0])*(keta-index2))
                number2 = int(
                    str(listA2[0])*(keta-index2)+str(listA2[index3])*index2)
                print(max(number1, number2))
                flag=0
                break
            index3+=1
        index2+=1

Submission status: Wrong Answer

Solution code:
import itertools
N,M=map(int,input().split())
A=list(map(int,input().split()))
C=[2,5,5,4,5,6,3,7,6]
D=[C[a-1] for a in A]
L=N//min(D)
for i in reversed(range(1,L+1)):
    S=list(filter(lambda s:sum([C[x-1] for x in s])==N, itertools.product(A,repeat=i)))
    if len(S)>1:
        print("".join(map(str,max(S))))
        break

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
numbers = list(map(int, input().split()))
costs = [2,5,5,4,5,6,3,7,6] # <- 1,2,3,4,5,6,7,8,9
costmap = {}
for num in numbers:
  cost = costs[num-1]
  if cost in costmap and num < costmap[cost]:
    continue
  costmap[cost] = num

from functools import lru_cache
@lru_cache(None)
def recursive(remain=N):
  maxval = costmap[remain] if remain in costmap else 0
  for cost, num in costmap.items():
    if remain > cost:
      val = recursive(remain-cost) * 10 + num
      if val > maxval:
        maxval = val
  return maxval
 
print(recursive(N))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp = [[] for k in range(n+1)]

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

#dpの初期化
for i in range(m):
    if cost[a[i]] <= n:
        dp[cost[a[i]]]= [a[i]]


for i in range(0,n+1):
    for k in range(m):
        if i > cost[a[k]]:
            #print(cost[a[k]])
            tmp = copy.copy(dp[i-cost[a[k]]])
            tmp.append(a[k])
            tmp.sort(reverse = True)
            #print(i,tmp)
            if len(tmp) > len(dp[i]) and len(tmp) != 1:
                dp[i] = tmp
            elif len(tmp) == len(dp[i]) and len(tmp) != 1:
                big = 0
                for s in range(len(tmp)):
                    if tmp[s] > dp[i][s]:
                        big = 1
                        break
                if(big):
                    dp[i] = tmp
            #print(dp)

ans = ""
for cha in dp[n]:
    ans = ans + str(cha)
print(ans)