Problem:


Score : 400 points

Problem Statement

Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:

Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9).

The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6, respectively.

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

There exists an integer that can be formed by exactly N matchsticks under the conditions.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

The output may not fit into a 64-bit integer type.

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Wrong Answer

Solution code:
from itertools import product
from operator import itemgetter

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [6,2,5,5,4,5,6,3,7,6] # B[i]がiを作るのに必要なマッチ棒の数

# 最小マッチ数で貪欲に桁数を稼ぐ
# 同じマッチの数があればより大きい数を選ぶ。5本なら2よりも4。->OK
# それでピッタリN本つかえなかったら、一回返してもらってそれでピッタリの数を探す

# とおもったらサンプル3が強い。 稼いだあまりを補充したときに、数字を貪欲にとっていくケースがある…
# 桁数仮定して構成できるか？をチェックしたほうがよさそう。5000程度だし、Nでかなり縛られるだろうし。
# 単純貪欲がうまくいかねー
# 構築できちゃったものがみつかったとき、それが最大桁なんだったら、ここで全探索してしまえばよいんだが怪しいなあ

# 構成するときにはマッチの本数順ではなく、数字の大きさ順で左からならべること！
# N=10000程度なので、桁は5000桁程度。ListにぶちこんでSortして結合でよい -> OK

cand = []
for a in A:
  # match_cost, number
  cand.append([B[a], a])
  
cand.sort(key=itemgetter(1),reverse=True)
cand.sort(key=itemgetter(0))

#print(cand)

m,n = cand[0]
# nが連続する数
seqk = N//m - 1
# あまり
res = N%m + m

keta = 1
zan = 0
while seqk >= 0:
  zan = 0
  for pat in product(A,repeat=keta):
    #print(pat)
    matti_wk = 0
    for p in pat:
      matti_wk += B[p]
    if matti_wk == res:

      zan = max(zan, int("".join(map(str,pat))))
  if zan > 0:
    break
  else:
    keta += 1
    seqk -= 1
    res += m
#print(seqk, zan)

ANS = [n] * seqk
for chr in str(zan):
  ANS.append(int(chr))
  
ANS.sort(reverse=True)
print("".join(map(str,ANS)))

Submission status: Wrong Answer

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

#1 2 3 4 5 6 7 8 9
#2 5 5 4 5 6 3 7 6

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

cost2v={}
use=[]

for aa in a:
    if cost[aa] in cost2v:
        cost2v[cost[aa]]=max(cost2v[cost[aa]],aa)
    else:
        cost2v[cost[aa]]=aa
        use.append(cost[aa])

use.sort()
keta=n//use[0]
amari=n%use[0]

if amari==0:
    print(str(cost2v[use[0]])*keta)
    exit()
else:
    i=1
    ans=[]
    flag=0
    tmp=amari+use[0]*1
    for item in use:
        if item==tmp:
            
            if cost2v[item]>cost2v[use[0]]:
                print(str(cost2v[item])+str(cost2v[use[0]])*(keta-1))
                exit()
            else:
                print(str(cost2v[use[0]])*(keta-1)+str(cost2v[item]))
                exit()

    tmp=amari+use[0]*2
    for item1 in use:
        for item2 in use:
            if item1+item2==tmp:
                if cost2v[item1]>=cost2v[item2] and cost2v[item2]>cost2v[use[0]]:
                    print(str(cost2v[item1])+str(cost2v[item2])+str(cost2v[use[0]])*(keta-2))
                    exit()
                if cost2v[item2]>=cost2v[item1] and cost2v[item1]>cost2v[use[0]]:
                    print(str(cost2v[item2])+str(cost2v[item1])+str(cost2v[use[0]])*(keta-2))
                    exit()
                
                if cost2v[item1]>cost2v[use[0]] and cost2v[use[0]]>cost2v[item2]:
                    print(str(cost2v[item1])+str(cost2v[use[0]])*(keta-2)+str(cost2v[item2]))
                    exit()
                if cost2v[item2]>cost2v[use[0]] and cost2v[use[0]]>cost2v[item1]:
                    print(str(cost2v[item2])+str(cost2v[use[0]])*(keta-2)+str(cost2v[item1]))
                    exit()
                
                if cost2v[use[0]] >cost2v[item1]and cost2v[item1]>=cost2v[item2]:
                    print(str(cost2v[use[0]])*(keta-2)+str(cost2v[item1])+str(cost2v[item2]))
                    exit()
                if cost2v[use[0]] >cost2v[item2]and cost2v[item2]>=cost2v[item1]:
                    print(str(cost2v[use[0]])*(keta-2)+str(cost2v[item2])+str(cost2v[item1]))
                    exit()

Submission status: Wrong Answer

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

#1 2 3 4 5 6 7 8 9
#2 5 5 4 5 6 3 7 6

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

cost2v={}
use=[]

for aa in a:
    if cost[aa] in cost2v:
        cost2v[cost[aa]]=max(cost2v[cost[aa]],aa)
    else:
        cost2v[cost[aa]]=aa
        use.append(cost[aa])

use.sort()
keta=n//use[0]
amari=n%use[0]

if amari==0:
    print(str(cost2v[use[0]])*keta)
    exit()
else:
    i=1
    ans=[]
    flag=0
    tmp=amari+use[0]*1
    
    for item in use:
        if item==tmp:
            if cost2v[item]>cost2v[use[0]]:
                print(str(cost2v[item])+str(cost2v[use[0]])*(keta-1))
                exit()

    tmp=amari+use[0]*2
    for item1 in use:
        for item2 in use:
            if item1+item2==tmp:
                if cost2v[item1]>=cost2v[item2] and cost2v[item2]>cost2v[use[0]]:
                    print(str(cost2v[item1])+str(cost2v[item2])+str(cost2v[use[0]])*(keta-2))
                    exit()
                if cost2v[item2]>=cost2v[item1] and cost2v[item1]>cost2v[use[0]]:
                    print(str(cost2v[item2])+str(cost2v[item1])+str(cost2v[use[0]])*(keta-2))
                    exit()
                
                if cost2v[item1]>cost2v[use[0]] and cost2v[use[0]]>cost2v[item2]:
                    print(str(cost2v[item1])+str(cost2v[use[0]])*(keta-2)+str(cost2v[item2]))
                    exit()
                if cost2v[item2]>cost2v[use[0]] and cost2v[use[0]]>cost2v[item1]:
                    print(str(cost2v[item2])+str(cost2v[use[0]])*(keta-2)+str(cost2v[item1]))
                    exit()
                
                if cost2v[use[0]] >cost2v[item1]and cost2v[item1]>=cost2v[item2]:
                    print(str(cost2v[use[0]])*(keta-2)+str(cost2v[item1])+str(cost2v[item2]))
                    exit()
                if cost2v[use[0]] >cost2v[item2]and cost2v[item2]>=cost2v[item1]:
                    print(str(cost2v[use[0]])*(keta-2)+str(cost2v[item2])+str(cost2v[item1]))
                    exit()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

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

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

# たとえば2と3を両方作れるときに、2を作るメリットはない。
if 2 in A and 3 in A:
  A.remove(2)
if 2 in A and 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)

# ある本数を使ったときに、作った桁数が大きいほうが有利
# 使った本数でダイクストラ

INF = 10 ** 9
dp = [INF] * (N + 1) # 作った桁数
ans = [""] * (N + 1) # 作った文字

import heapq
# 使った本数, 作った数(最後に降順に並べ替える)
q = [(0, 0,"")]
heapq.heapify(q)
while q:
  digit, used, strnum = heapq.heappop(q)
  keta = len(strnum)
  #print("used",used,"num",num)
  if used > N:
    continue
#  if dp[keta] < used:
    # その桁数を作るのに使った本数
#    continue
  dp[keta] = used
  ans[keta] = strnum
  if used == N:
    break
  for a in A:
    heapq.heappush(q,(digit - 1, used + dic[a],strnum + str(a)))

#print(dp)
#print(ans)
for i in range(len(dp) - 1, -1, -1):
  if dp[i] == N:
    print("".join(sorted(ans[i],reverse = True)))
    break

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

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

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

# たとえば2と3を両方作れるときに、2を作るメリットはない。
if 2 in A and 3 in A:
  A.remove(2)
if 2 in A and 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)

# ある本数を使ったときに、作った桁数が大きいほうが有利
# 使った本数でダイクストラ

dp = [-1] * (N + 1)
dp[0] = 0
import heapq
# 桁数, 使った本数, 作った数(最後に降順に並べ替える)
q = [(0,0,"")]
heapq.heapify(q)
while q:
  digit, used, num = heapq.heappop(q)
  #print("used",used,"num",num)
  if used > N:
    continue
  if dp[used] > len(num):
    # すでに作った数より桁数が小さい
    continue
  dp[used] = len(num)
  if used == N:
    print("".join(sorted(num,reverse = True)))
    break
  for a in A:
    heapq.heappush(q,(digit - 1,used + dic[a],num + str(a)))

#print(dp)
#print(dp[N])

Submission status: Wrong Answer

Solution code:
nd = [0,2,5,5,4,5,6,3,7,6]
dic = {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())
a= list(map(int,input().split()))
numset = set()
hasnum = {}
for c in a:
    numset.add(dic[c])
    hasnum[dic[c]] = hasnum.get(dic[c],[])+[c]
sel = []
def dfs(n,presel,path):
    global sel
    for c in numset:
        if c<presel:pass
        elif n<c:pass
        elif n==c:
            if len(sel)==0:sel.append(path+[c])
            else:
                if len(sel[0]) < len(path)+1:
                    sel=[]
                    sel.append(path+[c])
                elif len(sel[0]) < len(path)+1:
                    sel.append(path+[c])
        else:dfs(n-c,c,path+[c])

smallest = 9
smallestnum = 9
for ac in a:
    if nd[ac] < smallest:
        smallest=nd[ac]
        smallestnum=ac
yoyaku = 0
if n>100:
    while n>10:
        n -= smallest
        yoyaku +=1
dfs(n,0,[])
ans = []
ansstr = ''
for alist in sel:
    subans = []
    for c in alist:
        subans.append(str(max(hasnum[c])))
    ans.append(sorted(subans,reverse=True))
for l in ans:
    newl = l + [str(smallestnum)]*yoyaku
    tempstr = ''.join(sorted(newl,reverse=True))
    if ansstr < tempstr:ansstr = tempstr
print(ansstr)

Submission status: Wrong Answer

Solution code:
# match matching
import bisect
import sys
input = sys.stdin.readline
compare = [10**i for i in range(5*10**3+1)]
N, M = map(int, input().split())
ok = list(map(int, input().split()))
ok.sort()
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]
data = {a[i]: b[i] for i in range(9)}
dp = [[0 for i in range(N+1)] for j in range(M+1)]


def find(X):
    return bisect.bisect_right(compare, X)


for i in range(M):
    for cnt in range(N+1):
        for num in ok[:i]:
            cost = data[num]
            if cnt > cost:
                K = dp[i+1][cnt-cost]
                if K > 0:
                    dp[i+1][cnt] = max(K + num*10 ** find(K), dp[i+1][cnt])
                    continue
                else:
                    dp[i+1][cnt] = max(K, dp[i+1][cnt])
                    continue
            elif cnt == cost:
                dp[i+1][cnt] = max(num, dp[i+1][cnt])
                continue
            else:
                dp[i+1][cnt] = max(dp[i][cnt], dp[i+1][cnt])
                continue
ans = dp[M][N]
print(ans)

Submission status: Wrong Answer

Solution code:
# match matching
from math import log10, floor
N, M = map(int, input().split())
ok = list(map(int, input().split()))
ok.sort()
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]

data = {a[i]: b[i] for i in range(9)}

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


def find(X):
    return floor(log10(X))+1


def main():
    for i in range(M):
        for cnt in range(N+1):
            for j in range(M):
                num = ok[j]
                cost = data[num]
                if cnt > cost:
                    if dp[i + 1][cnt-cost] > 0:
                        dp[i+1][cnt] = max(dp[i+1][cnt-cost] + num*10 ** find(dp[i+1][cnt-cost]), dp[i+1][cnt])
                    else:
                        dp[i+1][cnt]=max(dp[i+1][cnt-cost], dp[i+1][cnt])
                elif cnt == cost:
                    dp[i+1][cnt]=max(num, dp[i+1][cnt])
                else:
                    dp[i+1][cnt]=max(dp[i][cnt], dp[i+1][cnt])
    ans=dp[M][N]
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

num_to_hon = [0, 2,5,5,4,5,6,3,7,6]
hon_to_num_dic = {}
for a in al:
    hon = num_to_hon[a]
    hon_to_num_dic.setdefault(hon,0)
    hon_to_num_dic[hon] = max(a, hon_to_num_dic[hon])


dp = [{'keta':0, 'num_cnts':[0]*10} for _ in range(n+10)]
for hon, num in hon_to_num_dic.items():
    dp[hon]['keta'] = 1
    dp[hon]['num_cnts'][num] += 1


for i in range(n):
    i_keta = dp[i]['keta']
    if i_keta == 0: continue
    # print('#######', i)
    # print(dp[i])
    for hon, num in hon_to_num_dic.items():
        i_num_cnts = dp[i]['num_cnts'][:]
        i_keta = dp[i]['keta']
        i_num_cnts[num] += 1
        next_dp = {'keta': i_keta+1, 'num_cnts':i_num_cnts[:]}
        # if i_keta == 0 and dp[i+hon]['keta'] > 0:
        #     continue
        if next_dp['keta'] > dp[i+hon]['keta']:
            dp[i+hon] = next_dp
            # print()
        elif next_dp['keta'] == dp[i+hon]['keta']:
            for comp_num in range(9,0,-1):
                if i_num_cnts[comp_num] > dp[i]['num_cnts'][comp_num]:
                    dp[i+hon] = next_dp
                    break
                elif  i_num_cnts[comp_num] < dp[i]['num_cnts'][comp_num]:
                    break

# print(dp[10])
# print(dp[11])
# print(dp[n])
# print(hon_to_num_dic)
ans = []
for num in range(9,0,-1):
    ans.extend([str(num)]*dp[n]['num_cnts'][num])

print(''.join(ans))

Submission status: Wrong Answer

Solution code:
def main():
    n, m, *a = map(int, open(0).read().split())
    t = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    a.sort(reverse=True)
    b = {}
    for i in a:
        x = t[i]
        if b.get(x) is not None:
            a.remove(i)
        else:
            b[i] = 0

    b = [t[i] for i in a]
    dp = [-float('Inf')] * (n + 10)
    dp[0] = 0
    for i in range(2, n + 1):
        dp[i] = max(dp[i - j] + 1 for j in b)

    nums = []
    for i in range(dp[n], 0, -1):
        for x in a:
            if dp[n - t[x]] == i - 1:
                nums.append(x)
                n -= t[x]
                break

    ans = ''.join(map(str, nums))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def create_integer_string(counts):
    res = ""

    for i in range(9, 0, -1):
        count = counts[i]
        res += str(i) * count

    return res


def main():
    from copy import copy

    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    pat = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    match_nums = dict()

    for x in a:
        match_num = pat[x]
        match_nums[match_num] = x

    dp = [0] * (n + 1)
    dp_c = [[0] * 10 for _ in range(n + 1)]

    for i in range(n + 1):
        for match_num, val in match_nums.items():
            if i + match_num > n:
                continue
            if i > 0 and dp[i] == 0:
                continue
            if dp[i + match_num] < dp[i] + 1:
                dp[i + match_num] = dp[i] + 1
                dp_c[i + match_num] = copy(dp_c[i])
                dp_c[i + match_num][val] += 1
            elif dp[i + match_num] == dp[i] + 1:
                counts_cur = copy(dp_c[i + match_num])
                cur = create_integer_string(counts_cur)
                counts_new = copy(dp_c[i])
                counts_new[val] += 1
                new = create_integer_string(counts_new)
                if new > cur:
                    dp[i + match_num] = dp[i] + 1
                    dp_c[i + match_num] = copy(dp_c[i])
                    dp_c[i + match_num][val] += 1

    for i in range(n + 1):
        counts = dp_c[i]
        print(i, create_integer_string(counts))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def create_integer_string(counts):
    res = ""

    for i in range(9, 0, -1):
        count = counts[i]
        res += str(i) * count

    return res

def main():
    from copy import copy

    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    pat = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    match_nums = dict()

    for x in a:
        match_num = pat[x]
        match_nums[match_num] = x

    dp = [0] * (n + 1)
    dp_c = [[0] * 10 for _ in range(n + 1)]

    for i in range(n + 1):
        for match_num, val in match_nums.items():
            if i + match_num > n:
                continue
            if i > 0 and dp[i] == 0:
                continue
            if dp[i + match_num] < dp[i] + 1:
                dp[i + match_num] = dp[i] + 1
                dp_c[i + match_num] = copy(dp_c[i])
                dp_c[i + match_num][val] += 1
            elif dp[i+match_num] == dp[i]:
                counts_cur = copy(dp_c[i+match_num])
                cur = create_integer_string(counts_cur)
                counts_new = copy(dp_c[i])
                counts_new[val] += 1
                new = create_integer_string(counts_new)
                if new > cur:
                    dp[i + match_num] = dp[i] + 1
                    dp_c[i + match_num] = copy(dp_c[i])
                    dp_c[i + match_num][val] += 1

    counts = dp_c[n]

    print(create_integer_string(counts))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from copy import copy

    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    pat = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    match_nums = dict()

    for x in a:
        match_num = pat[x]
        match_nums[match_num] = x

    dp = [0] * (n + 1)
    dp_c = [[0] * 10 for _ in range(n + 1)]
    dp_t = [0] * (n + 1)

    for i in range(n + 1):
        for match_num, val in match_nums.items():
            if i + match_num > n:
                continue

            if i > 0 and dp[i] == 0:
                continue
            if dp[i + match_num] < dp[i] + 1:
                dp[i + match_num] = dp[i] + 1
                dp_c[i + match_num] = copy(dp_c[i])
                dp_c[i + match_num][val] += 1
                dp_t[i + match_num] = val

    counts = dp_c[n]
    ans = ""

    for i in range(9, 0, -1):
        count = counts[i]
        ans += str(i) * count

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from copy import copy

    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    num = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    match_nums = set([num[i] for i in a])

    dp = [0] * (n + 1)
    dp_c = [[0] * 8 for _ in range(n + 1)]

    for i in range(n + 1):
        for match_num in match_nums:
            if i + match_num > n:
                continue
            if dp[i + match_num] < dp[i] + 1:
                dp[i + match_num] = dp[i] + 1
                dp_c[i + match_num] = copy(dp_c[i])
                dp_c[i + match_num][match_num] += 1

    counts = dp_c[n]
    ans = ""

    for x in a[::-1]:
        match_num = num[x]
        count = counts[match_num]
        ans += str(x) * count
        counts[match_num] = 0

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  n,m = map(int,readline().split())
  a = list(map(int,readline().split()))
  d5 = False
  d9 = False

  if 5 in a:
    d5 = True
  if 9 in a:
    d9 = True
  chk = set()
  for i in a:
    if d5 and (i == 2 or i == 3):
      continue
    if d9 and i == 6:
      continue
    chk.add(i)

  dp = [-float('inf')]*(n+1)
  dp[0] = 0
  f = [0,2,5,5,4,5,6,3,7,6]

  for i in range(2,n+1):
    for j in chk:
      F = f[j]
      if F <= i:
        dp[i] = max(dp[i-F]*10+j,dp[i])

  print(dp)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  n,m = map(int,readline().split())
  a = list(map(int,readline().split()))
  d2 = False
  d5 = False
  d9 = False

  if 2 in a:
    d2 = True
  if 5 in a:
    d5 = True
  if 9 in a:
    d9 = True
  chk = set()
  for i in a:
    if d2 and (i == 9 or i == 6 or i == 4):
      continue
    if d5 and (i == 2 or i == 3):
      continue
    if d9 and i == 6:
      continue
    chk.add(i)

  dp = [-float('inf')]*(n+1)
  dp[0] = 0
  f = [0,2,5,5,4,5,6,3,7,6]

  for i in range(2,n+1):
    for j in chk:
      F = f[j]
      if F <= i:
        dp[i] = max(dp[i-F]*10+j,dp[i])

  print(dp[n])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a_list = sorted(list(map(int,input().split())),reverse=True)
#print(a_list)
match_list = {
    2:[1],
    3:[7],
    4:[4],
    5:[2,3,5],
    6:[6,9],
    7:[8]
}
number_match = {
    1:2,
    2:5,
    3:5,
    4:4,
    5:5,
    6:6,
    7:3,
    8:7,
    9:6
}
matchs = sorted([[a,number_match[a]] for a in a_list],key=lambda x: x[1],reverse=True)
max_digits = 0
max_num = 0
for a,_ in matchs:
    if max_digits <= n//number_match[a]:
        max_num = a
        max_digits = n//number_match[a]
ans = [max_num]*max_digits
remain_match = n - max_digits*number_match[max_num]
#print(ans)

while remain_match > 0:
    remain_match += number_match[max_num]
    max_append = max_num
    for a in a_list:
        if remain_match == number_match[a] :
            max_append = a
            break
        elif max_append == max_num and number_match[a]< remain_match:
            max_append = a
    remain_match -= number_match[max_append]
    ans = ans[1:]+[max_append]
ans = sorted(ans,reverse=True)

out = ""
for num in ans:
    out += str(num)
print(out)

Submission status: Wrong Answer

Solution code:
#123456789
#255456376
n, m = map(int, input().split())
a = list(map(int , input().split()))
a.sort()
t = [2,5,5,4,5,6,3,7,6]
cost = []
for i in range(m):
    cost.append(t[a[i]-1])
#print(a)
#print(cost)
min_c = min(cost)
d = n // min_c # 最大桁数
s = n % min_c # 最大桁まで作った余りの本数
#print(d, s)

chg = []
while s > 0:
    #print(s, chg)
    for i in reversed(range(m)):
        if min_c + s == cost[i]:
            chg.append(a[i])
            s = 0
            break
    for i in reversed(range(m)):
        if min_c < cost[i] and cost[i] < min_c + s:
            chg.append(a[i])
            s = min_c + s - cost[i]
            break

#print(chg)
min_chr = ''
for i in reversed(range(m)):
    if min_c == cost[i]:
        min_chr = a[i]
        break

ans = chg + ([min_chr] * (d - len(chg)))
ans.sort(reverse=True)
print(''.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
#123456789
#255456376
n, m = map(int, input().split())
a = list(map(int , input().split()))
a.sort()
t = [2,5,5,4,5,6,3,7,6]
cost = []
for i in range(m):
    cost.append(t[a[i]-1])
#print(a)
#print(cost)
min_c = min(cost)
d = n // min_c # 最大桁数
s = n % min_c # 最大桁まで作った余りの本数
#print(d, s)

chg = []
while s > 0:
    #print(s, chg)
    for i in reversed(range(m)):
        if min_c + s == cost[i]:
            chg.append(a[i])
            s = 0
            break
    for i in reversed(range(m)):
        if min_c < cost[i] and cost[i] < min_c + s:
            chg.append(a[i])
            s = min_c + s - cost[i]
            continue

#print(chg)
min_chr = ''
for i in reversed(range(m)):
    if min_c == cost[i]:
        min_chr = a[i]
        break

ans = chg + ([min_chr] * (d - len(chg)))
ans.sort(reverse=True)
print(''.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def main():
    C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * (N + 1)
    K = {a: C[a - 1] for a in A}
    for i in range(1, min(K)):
        dp[i] = -1

    for i in range(min(K), N + 1):
        try:
            dp[i] = max(max(dp[i - v] * 10 + k, int(str(k) + str(dp[i-v])) if dp[i-v] > 0 else k) for k, v in K.items() if i - v >= 0 and dp[i - v] >= 0)
        except ValueError:
            dp[i] = -1
    print(dp[N])
main()

Submission status: Wrong Answer

Solution code:
def main():
    C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * (N + 1)
    K = {a: C[a - 1] for a in A}
    for i in range(1, min(K)):
        dp[i] = -1

    for i in range(min(K), N + 1):
        try:
            dp[i] = max(dp[i - v] * 10 + k for k, v in K.items() if i - v >= 0 and dp[i - v] >= 0)
        except ValueError:
            dp[i] = -1
    print(dp[N])
main()

Submission status: Wrong Answer

Solution code:
def num_to_match(n):
    if n == 1:
        return 2
    elif n == 7:
        return 3
    elif n == 4:
        return 4
    elif n in [2, 3, 5]:
        return 5
    elif n in [6, 9]:
        return 6
    else:
        return 7


def max_length(N, match):
    match = set(match)
    dp = [0 for _ in range(N + 1)]
    for n in range(1, N + 1):
        max_l = 0
        for m in match:
            if n - m >= 0:
                max_l = max([max_l, 1 + dp[n - m]])
        dp[n] = max_l
    return dp


def main():
    N, _ = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    A.sort(reverse=True)
    match = list(map(num_to_match, A))
    max_l = max_length(N, match)
    digits = [0 for _ in range(max_l[N])]
    n_match = N
    for i in range(max_l[N]):
        for a in A:
            ma = num_to_match(a)
            if max_l[n_match] > 1:
                if max_l[n_match - ma] == max_l[n_match] - 1:
                    digits[i] = a
                    n_match -= ma
                    break
            else:
                if ma == n_match:
                    digits[i] = a
                    n_match -= ma
                    break
    ans = 0
    for d in digits:
        ans *= 10
        ans += d
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[[] for i in range(0,10)]
for i in range(0,M):
    if 1 in A:
        B[2].append(1)
    if 2 in A:
        B[5].append(2)
    if 3 in A:
        B[5].append(3)
    if 4 in A:
        B[4].append(4)
    if 5 in A:
        B[5].append(5)
    if 6 in A:
        B[6].append(6)
    if 7 in A:
        B[3].append(7)
    if 8 in A:
        B[7].append(8)
    if 9 in A:
        B[6].append(9)


dp=['n' for i in range(0,max(10,N+1))]
for i in range(0,min(N+1,10)):
    if  i==1:
        if 1 in A:
            dp[2]='1'
    if i==2:
        if 2 in A:
            dp[5]='2'
    if i==3:
        if 3 in A:
            dp[5]='3'
    if i==4:
        if 4 in A:
            dp[4]='4'
    if i==5:
        if 5 in A:
            dp[5]='5'
    if i==6:
        if 6 in A:
            dp[6]='6'
    if i==7:
        if 7 in A:
            dp[3]='7'
    if i==8:
        if 8 in A:
            dp[7]='8'
    if i==9:
        if 9 in A:
            dp[6]='9'

if N>=4:
    if B[2]!=[]:
        dp[4]='11'
if N>=5:
    if B[3]!=[] and dp[2]!='n':
        dp[5]='71'
if N>=6:
    a='0'
    b='0'
    c='0'
    if B[2]!=[] and dp[4]!='n':
        a='1'+dp[4]
    if B[3]!=[]:
        b='77'
    if B[4]!=[] and dp[2]!='n':
        c='41'
    if dp[6]=='n':
        a=int(a)
        b=int(b)
        c=int(c)
        x=max(a,b,c)
        if x!=0:
            dp[6]=str(x)
    else:
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(dp[6])
        dp[6]=str(max(a,b,c,d))

if N>=7:
    a='0'
    b='0'
    c='0'
    d='0'
    if B[2]!=[] and dp[5]!='n':
        a='1'+dp[5]
    if B[3]!=[] and dp[4]!='n':
        b='7'+dp[4]
    if B[4]!=[] and dp[3]!='n':
        c='47'
    if B[5]!=[] and dp[2]!='n':
        d=str(max(B[5]))+'1'
    if dp[7]=='n':
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        x=max(a,b,c,d)
        if x!=0:
            dp[7]=str(x)
    else:
        a=int(a)
        b=int(b)
        c=int(c)
        d=int(d)
        e=int(dp[7])
        dp[7]=str(max(e,a,b,c,d))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  4 20:56:12 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

A1 = np.array(A)
A1.sort()
matchi = np.array([99,2,5,5,4,5,6,3,7,6])

matchi = matchi[A1]
m = np.min(matchi)
m_n = list(A1[matchi == m])

ans = m_n * (N // m)

tmp = N % m
flg = True
while flg:
    tmp += m
    ans.pop()
    for i in range(1,len(matchi)+1):
#        print(i,tmp,matchi)
        if tmp == matchi[-i]:
            ans.append(A1[-i])
            flg = False
            break
        elif tmp >= matchi[-i] and tmp % matchi[-i] in matchi:
            ans.append(A1[-i])
            ans.append(A1[matchi == tmp % matchi[-i]][-1])
            flg = False
            break

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

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = [0,2,5,5,4,5,6,3,7,6]
S = set()
for a in A:
    S.add(d[a])

INF = 10 ** 8
dp = [-INF for _ in range(N+1)]
dp[0] = 0

for i in range(N+1):
    for s in S:
        if i - s >= 0:
            dp[i] = max(dp[i], dp[i-s]+1)

ans = 0
digit = dp[N]

print(dp)

for i in range(digit-1, -1, -1):
    if i != 0:
        for a in A:
            if dp[N-d[a]] == i:
                ans = ans * 10 + a
                N -= d[a]
                break
    else:
        for a in A:
            if N == d[a]:
                ans = ans * 10 + 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)
d = [0,2,5,5,4,5,6,3,7,6]
S = set()
for a in A:
    S.add(d[a])

dp = [0 for _ in range(N+1)]

for i in range(N+1):
    for s in S:
        if i - s >= 0:
            dp[i] = max(dp[i], dp[i-s]+1)

ans = 0
digit = dp[N]

for i in range(digit-1, -1, -1):
    if i != 0:
        for a in A:
            if dp[N-d[a]] == i:
                ans = ans * 10 + a
                N -= d[a]
                break
    else:
        for a in A:
            if N == d[a]:
                ans = ans * 10 + a
                break
print(ans)