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

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

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


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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
num=[0,2,5,5,4,5,6,3,7,6]
from collections import defaultdict
dp=defaultdict(int)
dp[0]=0
for i in range(1,1+n):
    for x in a:
        if i-num[x]>=0:
            dp[i]=max(dp[i],dp[i-num[x]]+1)
now=n
ans=''
for j in range(dp[n]):
    for x in a:
        if j==dp[n]-1:
            if now==num[x]:
                ans+=str(x)
                break
        elif now-num[x]<0:continue
        elif dp[now-num[x]]==dp[now]-1:
            ans+=str(x)
            now-=num[x]
            break
print(ans)
#https://img.atcoder.jp/abc118/editorial.pdf

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
def li(): return map(int, stdin.readline().split())
N, M = tuple(li())
nums = tuple(li())

def get_larger_digits_same_len(cur, d):
    sorted_cur = sorted(cur, reverse=True)
    sorted_d = sorted(d, reverse=True)
    for i, j in zip(sorted_cur, sorted_d):
        if i > j:
            return sorted_cur
        elif i < j:
            return sorted_d
    # case equal
    return cur

def test_get_larger_digits_same_len():
    a = [1, 2, 3]
    b = [1, 4, 3]
    ans = get_larger_digits_same_len(a, b)
    ans = tuple(ans)
    assert ans == (4, 3, 1)


def get_larger_digits(cur, digits, new_digit):
    d = digits[:]
    d.append(new_digit)
    if len(d) > len(cur):
        return d
    elif len(d) < len(cur):
        return cur
    else:
        # case equal lengths
        return get_larger_digits_same_len(cur, d)

def test_get_larger_digits1():
    a = [1, 3, 5]
    b = [1, 3, 5, 0]
    ans = get_larger_digits(a, b, 1)
    assert len(ans) == 5

def test_get_larger_digits_one_empty_list():
    a = []
    b = [1, 3, 5, 0]
    ans = get_larger_digits(a, b, 1)
    assert len(ans) == 5

cost_dict ={
        1: 2,
        2: 5,
        3: 5,
        4: 4,
        5: 5,
        6: 6,
        7: 3,
        8: 7,
        9: 6,
        }
# init
init = [[]] * 8 # idx from 0 to 7
for i in range(8):
    cur = []
    for num in nums:
        if i - cost_dict[num] < 0:
            continue
        elif i == cost_dict[num]:
            cur = get_larger_digits(cur, [], num)
        elif i > cost_dict[num] and init[i - cost_dict[num]]:
            cur = get_larger_digits(cur, init[i-cost_dict[num]], num)
    init[i] = cur

state = reversed(init)
state = list(state)

for _ in range(N-7):
    cur = []
    for num in nums:
        cost = cost_dict[num]
        cur = get_larger_digits(cur, state[cost-1], num)
    state = [cur] + state[:-1]
print("".join(map(str, sorted(state[0], reverse=True))))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

use_lis = [need_lis[i] for i in a]

use_lis.sort()

use_num_lis= []
for i in use_lis:
    if i ==2:
        use_num_lis.append(1)
    if i ==3:
        use_num_lis.append(7)
    if i==4:
        use_num_lis.append(4)
    if i==5:
        if 5 in a:
            use_num_lis.append(5)
        elif 3 in a:
            use_num_lis.append(3)
        else:
            use_num_lis.append(2)
    if i==6:
        if 9 in a:
            use_num_lis.append(9)
        else:
            use_num_lis.append(6)
    if i==7:
        use_num_lis.append(8)

ok_lis=[]
for i in range(use_lis[0]**(len(use_lis)-1)):
    ind_lis=[]
    for j in range(len(use_lis)-2,-1,-1):
        #print(j)
        ind_lis.append(i//(use_lis[0]**j))
        i -= (i//(use_lis[0]**j))*(use_lis[0]**j)
    #print(ind_lis)
        
    count = 0
    for i in range(len(use_lis)-1):
        count += use_lis[i+1]*ind_lis[i]
    #print(count)
    if (n - count) %use_lis[0]==0:
        #print(n-count)
        rest = n-count
        ok_lis.append([int(rest/use_lis[0])]+ind_lis)

res=[]
for i in ok_lis:
    res.append(sum(i))
max_lis = [i for i in range(len(res)) if res[i]==max(res)]

answers_lis=[]
for i in max_lis:
    answer=''
    use = ok_lis[i]
    num_lis=use_num_lis
    
    for k in range(len(use)):
        
        ind = np.argmax(np.array(num_lis))
        #print(ind)
        if use[ind]>0:
            count=0
            for j in range(use[ind]):
                #print(type(count))
                count+=(10**j)*num_lis[ind]
            count =str(count)
                #print(type(count))
            answer+=count
        num_lis[ind]=0
    answers_lis.append(answer)
        
    use_num_lis= []
    for i in use_lis:
        if i ==2:
            use_num_lis.append(1)
        if i ==3:
            use_num_lis.append(7)
        if i==4:
            use_num_lis.append(4)
        if i==5:
            if 5 in a:
                use_num_lis.append(5)
            elif 3 in a:
                use_num_lis.append(3)
            else:
                use_num_lis.append(2)
        if i==6:
            if 9 in a:
                use_num_lis.append(9)
            else:
                use_num_lis.append(6)
        if i==7:
            use_num_lis.append(8)
        
    
    

print(int(max(answers_lis)))

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
from itertools import permutations
N,M = map(int, input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = list(map(int, input().split()))

p = []
for a in A:
    p.append( (cost[a], a) )
costp = sorted(p)


costX = [ z[0] for z in costp]
A = [ z[1] for z in costp]

dp = [""] * (N+1)

for c,a in zip(costX,A):
    i = N 
    if i-c >= 0:
        dp[i-c] = str(a)



for i in range(N-1, 1, -1):
    if len(dp[i]) == 0:
        continue
    
    for c,a in zip(costX,A):
        if i-c < 0: continue
        if dp[i-c] == "":
            dp[i-c] = str(a)

        elif dp[i-c] != "":
            # print([ int(dp[i-c]+str(a)),
            #                  int(str(a)+dp[i-c]), 
            #                  int(dp[i-c])
            #                 ])
            dp[i-c] =max(   int(dp[i]+str(a)),
                             int(str(a)+dp[i]), 
                        )
            dp[i-c] = str(dp[i-c])

        # for p in permutations( [dp[i], str(a)]):
        #     if i-c >= 0:
        #         if dp[i-c] == "":
        #             dp[i-c] = str(int( "".join(p)))
        #         else:
        #             dp[i-c] = str(max(int(dp[i-c]), int( "".join(p))))
    
print(dp[0])

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
from itertools import permutations
N,M = map(int, input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
A = list(map(int, input().split()))

p = []
for a in A:
    p.append( (cost[a], a) )
costp = sorted(p)


costX = [ z[0] for z in costp]
A = [ z[1] for z in costp]

dp = [""] * (N+1)

for c,a in zip(costX,A):
    i = N 
    if i-c >= 0:
        dp[i-c] = str(a)



for i in range(N-1, 1, -1):
    if len(dp[i]) == 0:
        continue
    
    for c,a in zip(costX,A):
        if i-c < 0: continue
        if dp[i-c] == "":
            dp[i-c] = str(a)

        elif dp[i-c] != "":
            # print([ int(dp[i-c]+str(a)),
            #                  int(str(a)+dp[i-c]), 
            #                  int(dp[i-c])
            #                 ])
            dp[i-c] =max(   int(dp[i]+str(a)),
                             int(str(a)+dp[i]), 
                             int(dp[i-c])
                             )
            dp[i-c] = str(dp[i-c])

        # for p in permutations( [dp[i], str(a)]):
        #     if i-c >= 0:
        #         if dp[i-c] == "":
        #             dp[i-c] = str(int( "".join(p)))
        #         else:
        #             dp[i-c] = str(max(int(dp[i-c]), int( "".join(p))))
    
print(dp[0])

Submission status: Wrong Answer

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

digits = [0]
pre = [None]
for i in range(1, n + 1):
    res = -10 ** 5
    p = None
    for hon in hons:
        if i < hon:
            continue
        dig = digits[i - hon] + 1
        if dig > res:
            res = dig
            p = i - hon
    digits.append(res)
    pre.append(p)

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
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():
    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], N)
            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, N):
    if remainder == 0:
        return str(main_num), 1
    d = match_table[main_num]
    best = 0
    penalty = 99
    digit = 0
    while digit < 7:
        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 and extra_sum <= N:
                cand_best = int(i)
                cand_penalty = -(remainder - extra_sum) // d
                #print(best, cand_best, cand_penalty, cand_penalty - len(i), penalty - len(str(best)))
                if cand_penalty - len(i) < penalty - len(str(best)):
                    best = cand_best
                    penalty = cand_penalty
                elif cand_penalty - len(i) == penalty - len(str(best)):
                    if cand_best / exp(len(i)) > best / exp(len(str(best))) :
                        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))

def exp(x):
    n = 1
    for i in range(x):
        n *= 10
    return n

if __name__ == '__main__':
    main()

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

now = ans
l = len(now)
if N==0:
	print(ans)
else:
	ans = '0'
	judge = False
	c = 0
	while c<=min(7,l-1):
		b = now[-1:]
		now = now[:-1]
#		print(ans)
		c += 1
		N += num[int(b)]
		for i in range(c):
			res = check(c-i,N,"")
			if res!="no":
				s1 = now+res
				s2 = res+now
				if len(ans)>len(s1):
					continue
				if s1<s2 and ans<s2:
					ans = s2
				elif s2<=s1 and ans<s1:
					ans = s1
				judge = True
print(ans)

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]

'''
N=10
M = 4
A=[3,4,5,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 = [[-1,[0]*nc] for i in [0]*(N+1)]

dp[0] = [0,[0]*nc]

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):
				dp[i] = (dp[i-c][0] + 1, temp)
			elif 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:
# これはWAの提出です。REの箇所を確かめるためにやります。
N, M = map(int, input().split())
Costs = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
A = sorted(list(map(int, input().split())), reverse=True)  # 大きい順に


# dp[i]:= マッチ棒をn本使って得られる最大桁数(-infはマッチ棒が使いきれないことを表す)
dp = [-float('inf')] * (N + 1)
dp[0] = 0

# 蟻本P.60みたいなことをします
for a in A:
    cost = Costs[a]
    for j in range(N + 1):
        if cost > j:
            continue
        dp[j] = max(dp[j], dp[j - cost] + 1)

print('x')
# # dpの復元
# ans = ""
# marker = N  # いま何本残っているか
# while dp[marker]:  # 0本になるまで回す
#     for a in A:  # 大きな数字から見ていく
#         cost = Costs[a]
#         # marker本ある状態から、マッチ棒をcost本使う数字aを使わなければ、marker本使った場合の桁数-1になる場合、
#         # 数字aを使ったことがわかる
#         if dp[marker - cost] == dp[marker] - 1:
#             ans += str(a)
#             marker = marker - cost
#             break
# 
# print(ans)

Submission status: Wrong Answer

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

digits = [0]
pre = [None]
for i in range(1, n + 1):
    res = -999
    p = None
    for j in range(i):
        if i - j in hons and digits[j] + 1 > res:
            res = digits[j] + 1
            p = j
    digits.append(res)
    pre.append(p)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
listA = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
dp = [-1]*10010
dp[0] = 0
for j in range(1, N+1):
	for a in listA:
		if j-c[a] >= 0:
			dp[j] = max(dp[j], a*10 + dp[j-c[a]])
print(dp[N])

Submission status: Wrong Answer

Solution code:
def printing(a_start, a_2, n):
    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)

    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            # print(n % a_start[1], a_3[i][1] % a_start[1])
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Wrong Answer

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

digits = [0]
pre = [None]
for i in range(1, n + 1):
    res = -1
    p = None
    for j in range(i):
        if i - j in hons and digits[j] + 1 > res:
            res = digits[j] + 1
            p = j
    digits.append(res)
    pre.append(p)

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]

def makenum(x,y):
    res = 0
    for i in range(y):
        res = res* 10 + x
    return res
    
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                copy = dp[i-use[j]][:]
                copy[j] += 1
                kouho.append(copy)
    if kouho == []: #空の場合
        continue #何もしない
    else:
        usearray = []
        usenum = 0
        for array in kouho:
            tmpnum = 0
            for k in range(9,0,-1):
                tmpnum = tmpnum * (10**array[k]) + makenum(k,array[k])
            if tmpnum > usenum:
                usearray = array
                usenum = usenum
        dp[i] = usearray
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


def get_int_list():
    return [int(i) for i in input().split()]


def get_char_list():
    return list(input().strip())


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


DECREASE_LEN = -1


def bigger_nums(base_num, rem, availables):
    ret = []
    for i in sorted(filter(lambda x: x > base_num, availables), reverse=True):
        if required_match[i] - required_match[base_num] <= rem:
            ret.append(i)
    return ret


def smaller_nums(base_num, rem, availables):
    ret = []
    for i in sorted(filter(lambda x: x < base_num, availables)):
        if 0 < required_match[i] - required_match[base_num] <= rem:
            ret.append(i)
    return ret


def loop(n, base_num, min_cost, availables, changes, rem, max_len, decrease_len, cnt):
    if rem == 0:
        ret = [base_num] * (max_len - decrease_len)
        for i, num in enumerate(changes):
            if num < base_num:
                ret[-1-i] = num
            else:
                ret[i] = num
        return ''.join(map(lambda x: str(x), ret))
    if cnt == max_len - decrease_len:
        return loop(n, base_num, min_cost, availables, [], n % min_cost + min_cost * (decrease_len + 1), max_len, decrease_len + 1, 0)
    nums = bigger_nums(base_num, rem, availables)
    for v in nums:
        ret = loop(n, base_num, min_cost, availables, changes + [v], rem - (required_match[v] - required_match[base_num]), max_len, decrease_len, cnt + 1)
        if ret:
            return ret
    nums = smaller_nums(base_num, rem, availables)
    for v in nums:
        ret = loop(n, base_num, min_cost, availables, changes + [v], rem - (required_match[v] - required_match[base_num]), max_len, decrease_len, cnt + 1)
        if ret:
            return ret
    return loop(n, base_num, min_cost, availables, [], n % min_cost + min_cost * (decrease_len + 1), max_len, decrease_len + 1, 0)


def main():
    n, m = get_int_list()
    availables = get_int_list()

    availables.sort(key=lambda x: required_match[x])
    base_num = availables[0]
    min_cost = required_match[base_num]
    max_len = n // min_cost
    rem = n % min_cost
    assert rem < 7

    print(loop(n, base_num, min_cost, availables, [], rem, max_len, 0, 0))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

if __name__ == '__main__':
    n, m = map(int, input().split())
    a = sorted(input().split(), reverse=True)

    dp = [-10007] * (n + 1)
    dp[0] = 0
    for i in a:
        step = mp[int(i)]
        for j in range(step, n + 1):
            dp[j] = max(dp[j - step] + 1, dp[j])

    print(dp)
    i = n
    while i > 0:
        for x in a:
            step = mp[int(x)]
            if i >= step and dp[i - step] == dp[i] - 1:
                sys.stdout.write(x)
                i -= step
                break
    print()

Submission status: Wrong Answer

Solution code:
def printing(a_start, a_2, n):
        a_3 = []
        mod_list = []
        for i in range(len(a_2)):
            if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
                a_3.append(a_2[i])
                mod_list.append(a_2[i][1] % a_start[1])
        a_3.sort(key=lambda x: x[1], reverse=True)
        #print(a_3, a_start)

        ans = ""
        while n % a_start[1] != 0:
            for i in range(len(a_3)):
                 #print(n % a_start[1], a_3[i][1] % a_start[1])
                 if n % a_start[1] >= a_3[i][1] % a_start[1]:
                     n -= a_3[i][1]
                     ans += str(a_3[i][0])
                     break
        ans = ans + str(a_start[0]) * (n // a_start[1])
        ans_list = sorted([ans[i] for i in range(len(ans))], reverse = True)
        print("".join(ans_list))


def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0,2,5,5,4,5,6,3,7,6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Wrong Answer

Solution code:
import math

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=0
    for j in A:
        tmp1=-100000000000000000000
        if(i-num[j]>=0):
            if(dp[i-num[j]]!=0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            else:
                tmp1=j
                tmp1_keta=1
            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
    dp.append(tmp)
    keta.append(tmp_keta)
ans=dp[N]
print(ans)

Submission status: Wrong Answer

Solution code:

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

# NUM_DICT = {
#     '2': [1],
#     '3': [7],
#     '4': [4],
#     '5': [2, 3, 5],
#     '6': [6, 9],
#     '7': [8]
# }
# NUMs = sorted(map(int, NUM_DICT.keys()))

N, M = map(int, raw_input().split())
As = map(int, raw_input().split())

num_dict = {}
for a in As:
    num = NUMs[a]
    if str(num) not in num_dict.keys():
        num_dict[str(num)] = a
    elif num_dict[str(num)] < a:
        num_dict[str(num)] = a
nums = sorted(map(int, num_dict))

#print nums, num_dict

remove = []
for i in nums:
    for j in nums:
        if i + j in nums:
            remove.append(i + j)
        if j > i and j % i == 0:
            remove.append(j)
nums = sorted(list(set(nums) - set(remove)))

#print nums

#print zip(nums, int_nums)

def divide(n, l):
    if len(l) == 1:
        if n % l[0] == 0:
            return True, [ n / l[0]]
        else:
            return False, []
    own_num = n // l[0]
    while own_num >= 0:
        pos, rest = divide(n - l[0] * own_num, l[1:])
        if pos:
            return True, [own_num] + rest
        own_num -= 1
    return False, []

dummy, int_nums = divide(N, nums)

i = ''
for m, n in zip(nums, int_nums):
    i += str(num_dict[str(m)]) * n

print ''.join(sorted(i, reverse=True))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
use = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [[0] * 10 for i in range(n+1)]
for i in range(1,n+1):
    kouho = []
    for j in a:
        if i - use[j] >= 0:
            if dp[i-use[j]] == [0] * 10 and i - use[j] != 0: # マッチの数が合わない場合
                continue #何もしない
            else:
                copy = dp[i-use[j]][:]
                copy[j] += 1
                kouho.append(copy)
    if kouho == []: #空の場合
        continue #何もしない
    else:
        usearray = []
        accnum = "0"
        for array in kouho:
            tmpnum = ""
            for k in range(9,0,-1):
                tmpnum += (str(k) * array[k])
            if int(tmpnum) > int(accnum):
                usearray = array
                accnum = tmpnum
        dp[i] = usearray
ans = ""
for i in range(9,0,-1):
    ans += (str(i) * dp[n][i])
print(0)

Submission status: Wrong Answer

Solution code:
INF = 10**10
arr = [10,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i+arr[j]] = max(dp[i+arr[j]],dp[i] + 1)
dim = dp[N]
ans  = '0'
'''while(dim > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] + 1 == dp[N]:
            ans += str(i)
            N -= arr[i]
            dim -= 1
            break'''
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
tmp=0
tmp1=0
for i in range(1,N+1):
    tmp=0
    for j in A:
        tmp1=-100000000000000000000
        if(i-num[j]>=0):
            if(dp[i-num[j]]!=0):
                tmp1=dp[i-num[j]]+j*(10**int(math.log10(dp[i-num[j]]) + 1))
            else:
                tmp1=j
            if(tmp1>tmp):
                tmp=tmp1
    dp.append(tmp)
ans=dp[N]
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:0, 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 = list(sorted(d.keys()))
    ans = ''
    if n % k[0] == 0:
        ans += str(d[k[0]][0]) * (n // k[0])
    else:
        p = n % k[0]
        s = []
        for i in range(9, 0, -1):
            if i > len(k):
                continue
            for j in list(itertools.combinations(k, i)):
                if p == sum(j) % k[0]:
                    s.append(list(j))
        tans = [None] * len(s)
        for idx, i in enumerate(s):
            i.sort(reverse=True)
            _tans = ''.join([str(d[w][0]) for w in i])
            _tans += str(d[k[0]][0]) * ((n - sum(i)) // k[0])
            _tans = list(_tans)
            _tans.sort(reverse=True)
            tans[idx] = (''.join(_tans))
        ans = 0
        for i in tans:
            ans = max(ans, int(i))
        ans = str(ans)
    ans = list(ans)
    ans.sort(reverse=True)
    print(''.join(ans))


if __name__=="__main__":
    solve()