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: Accepted

Solution code:
#!/usr/bin/env python3
#ABC118 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

M = [0,2,5,5,4,5,6,3,7,6]
n,m = map(int,input().split())
a = list(map(int,input().split()))
A = [[i,M[i]] for i in a]
A.sort(key = itemgetter(1))

#dp[i] := ちょうどマッチi本を使ってできる最大桁数
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(n):
    for j,k in A:
        if i + k < n+1:
            if dp[i] < 0:
                continue
            dp[i+k] = dp[i] + 1
A.sort(key = itemgetter(0),reverse = True)
ans = ''
k = n
while 1:
    for i,j in A:
        if k - j < 0:
            continue
        if dp[k-j] == dp[k]-1:
            ans += str(i)
            k -= j
            break
    else:
        break
print(ans)

Submission status: Accepted

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

Aset = {}
for a in A:
    c = cost[a]
    Aset[c] = max(Aset[c], a) if c in Aset else a
A = sorted([v for k,v in Aset.items()])

dp = [None]*(N+1)
dp[0] = (0,[0]*len(A))

for ia, a in enumerate(A):
    c = cost[a]
    for i in range(c, N+1):
        t = dp[i-c]
        if t and (dp[i]==None or t[0]+1>=dp[i][0]):
            dp[i] = (t[0]+1, t[1].copy())
            dp[i][1][ia] += 1
      	
l=[]
for i in range(len(A)):
    l += [A[len(A)-1-i]]*dp[N][1][len(A)-1-i]

print(*l, sep='')

Submission status: Accepted

Solution code:
def smax(s1, s2):
    if s1=="N":
        if s2[0]=="N":
            return "N"
        else:
            return s2
    if s2[0] == "N":
        return s1
    l1 = len(s1)
    l2 = len(s2)
    if l1 == l2:
        return max(s1, s2)
    if l1 > l2:
        return s1
    return s2

hon = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
aa = list(map(int, input().split()))
dp = ["N"] * (n + 1)
dp[0]=""
for i in range(2, n + 1):
    for a in aa:
        if i - hon[a] < 0: continue
        dp[i] = smax(dp[i], dp[i - hon[a]] + str(a))
print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict

memo = []


def find(nowstr, rest):
    if rest < 0:
        return ""

    for i in costlist:
        if i < rest:
            find(nowstr+str(i), rest - i)
        elif i == rest:

            memo.append(nowstr+str(i))


def cost_to_num(c):
    if c == 2:
        return "1"
    if c == 3:
        return "7"
    if c == 4:
        return "4"

    if c == 5:
        if 2 in num_to_use:
            return "2"
        elif 3 in num_to_use:
            return "3"
        else:
            return "5"
    if c == 6:
        if 6 in num_to_use:
            return "6"
        else:
            return "9"
    if c == 7:
        return "8"


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

num_to_use = set(Alist)
"""
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 を 1 つ作るには、
2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 本のマッチ棒を使う。
"""
ref = [2, 5, 5, 4, 5, 6, 3, 7, 6]
if 9 in num_to_use:
    num_to_use.discard(6)
if 5 in num_to_use:
    num_to_use.discard(2)
    num_to_use.discard(3)
if 3 in num_to_use:
    num_to_use.discard(2)


costlist = [ref[i-1] for i in num_to_use]
costlist.sort()
# print(num_to_use)
# print(costlist)
# print(costlist[0])
minlength = N // costlist[0] - 5
if minlength < 0:
    minlength = 0
ans_tail = [cost_to_num(costlist[0])]*minlength

delta = N - minlength * costlist[0]
# print(delta)
find("", delta)

# print(memo)

ans_length = len(memo[0])
temp = 0
for i in memo:
    if len(i) < ans_length:
        continue

    numlist = [cost_to_num(int(j)) for j in i]+ans_tail
    # print(numlist)
    numlist.sort(reverse=True)
    joined = "".join(numlist)
    # print(joined)
    if temp < int(joined):
        temp = int(joined)
ans_head = str(temp)

# print("---")
print(ans_head)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [float("inf"), 2, 5, 5, 4, 5, 6, 3, 7, 6]
mincost = min(cost)

dp = [None] * (n + 1)
def dfs(at):
    if at < 0:
        return -1
    if at == 0:
        return 0
    if dp[at] is not None:
        return dp[at]
    r = max(dfs(at - cost[v]) * 10 + v for v in a)
    dp[at] = r
    return r


print(dfs(n))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
*A, = map(int,input().split())
B = sorted((([2,5,5,4,5,6,3,7,6][a-1],a) for a in A),key = lambda x:(x[0],-x[1]))
i = 1
while i<len(B):
    if B[i][0]==B[i-1][0]:
        B.pop(i)
    else:
        i+=1
i = [0]*(len(B)-1)
if len(B)==1:
    print(str(B[0][1])*(N//B[0][0]))
    exit()
ans = []
while i[-1]<B[0][0]:
    tmp = N - sum(j*b[0] for j,b in zip(i,B[1:]))
    if tmp>=0 and tmp%B[0][0] == 0:
        num = ""
        for k,n in sorted(zip([b for _,b in B],[tmp//B[0][0]]+i),key = lambda x:-x[0]):
            num += str(k)*n
        ans.append(int(num))
    i[0]+=1
    for j in range(len(i)-1):
        if i[j]==B[0][0]:
            i[j+1]+=1
            i[j]=0
print(max(ans))

Submission status: Accepted

Solution code:
def larger(x, y):
	if len(x) > len(y):
		return x
	elif len(x) < len(y):
		return y
	else:
		if x > y:
			return x
		return y

matchuse = [5000000000000000, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [[]]
for i in range(0, 10):
	dp[0].append('')
made = []
for i in range(0, N+1):
	lst = []
	for j in range(0, M):
		lst.append(False)
	made.append(lst)
made[0][0] = True
for i in range(1, N+1):
	lst = []
	for j in range(0, M):
		next = ''
		if i - matchuse[A[j]] >= 0:
			index = i - matchuse[A[j]]
			for k in range(0, M):
				if made[index][k]:
					next = larger(next, dp[index][k]+str(A[j]))
		lst.append(next)
		if next != '':
			made[i][j] = True
	dp.append(lst)
ans = ''
for i in range(0, M):
	ans = larger(ans, dp[N][i])
print(ans)

Submission status: Accepted

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
match = []
for num in a:
    match.append(all_match[num-1])

dp = [-10**7 for i in range(n+1)] #桁数
dp[0] = 0

for i in range(1,n+1):
    possible = []
    for honsu in match:
        if i >= honsu:
            possible.append(dp[i-honsu] + 1)
    if len(possible)>0:
        dp[i] = max(possible)

length = dp[n]
ans = 0
now = n
for i in range(length):
    for j in range(m):
        if now >= match[j]:
            if dp[now-match[j]] == dp[now]-1:
                ans += a[j]*10**(length-i-1)
                now -= match[j]
                break

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

inf = 10 ** 4

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

use = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# use[i] : 数字iを作るのに必要なマッチの本数

use_num = {use[i]: i for i in range(1, 10) if i in a}
use_num = tuple(sorted(use_num.items()))
# 本数昇順
# print(use_num)

dp = [-inf] * (n + 1)
dp[0] = 0
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use, number in use_num:
        k = j - use
        if k >= 0:
            dp[j] = max(dp[j], dp[k] + 1)
# print(dp)

use_num = tuple(sorted(use_num, key=itemgetter(1), reverse=True))
# 数字降順

rest = n
ans = ''
while rest > 0:
    for use, number in use_num:
        k = rest - use
        if (k >= 0) and (dp[k] == dp[rest] - 1):
            ans += str(number)
            rest -= use
            break
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

inf = 10 ** 4


def larger(x, y):
    lx, ly = len(x), len(y)
    if lx > ly:
        return x
    elif lx < ly:
        return y
    else:
        x.sort(reverse=True)
        y.sort(reverse=True)
        for xx, yy in zip(x, y):
            if xx > yy:
                return x
            elif xx < yy:
                return y
        return x


def dfs(rest):
    if memo[rest] is not None:
        return memo[rest]

    res = []
    for use, number in d.items():
        if rest - use >= 0 and dp[rest - use] == dp[rest] - 1:
            res = larger(res, [number] + dfs(rest - use))

    memo[rest] = res
    return res


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

needs = [inf, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# needs[i] : 数字iを作るのに必要なマッチの本数

for i in range(1, 10):
    if i not in a:
        needs[i] = inf

d = {needs[i]: i for i in range(1, 10) if needs[i] != inf}
# d[本数] = その本数で作れる最大の数値

dp = [-inf] * (n + 1)
dp[0] = 0
# dp[j] : j本から構成できる桁数の最大値

for j in range(2, n + 1):
    for use, number in d.items():
        if j - use >= 0:
            dp[j] = max(dp[j], dp[j - use] + 1)

# print(dp)

memo = [None] * (n + 1)

ans = dfs(n)
ans.sort(reverse=True)
print(*ans, sep='')

Submission status: Accepted

Solution code:
n, m = [ int(v) for v in input().split() ]
num_list = [ int(v) for v in input().split() ]
match_table = [2,5,5,4,5,6,3,7,6]
match_table_2 = [ [] for i in range(8) ]
for i in num_list:
    match_table_2[match_table[i-1]].append(i)

match_table_2 = [ (max(match_table_2[i]), i) for i in range(8) if match_table_2[i] != [] ]
match_list, figure_list = zip(*match_table_2)
k = len(match_list)

dp_list = [ 0 for i in range(n+1) ]

for i in range(n+1):
    index_list = [ i - j for j in figure_list ]
    candidate_list = []
    for j in range(k):
        if index_list[j] > 0 and dp_list[index_list[j]] > 0:
            candidate_list.append(dp_list[index_list[j]] * 10 + match_list[j])
        elif index_list[j] == 0:
            candidate_list.append(match_list[j])
    if candidate_list != []:
        dp_list[i] = max(candidate_list)

print(dp_list[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [-1] * (N + 1)
dp[0] = 0
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
mn = []
for a in A:
    mn.append([match[a-1],a])
for i in range(2, N+1):
    for m, n in mn:
        if i-m  >= 0:
            dp[i] = max(dp[i],dp[i-m]*10+n)       
print(dp[-1])

Submission status: Accepted

Solution code:
from math import isinf

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

m = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# 最大何桁作れるか

# dp[i] := ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
# dp[i + 1] = max(dp[i - m[j]] + 1) for all j in A

dp = [float('-inf') for _ in range(N + 1)]
dp[0] = 0

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

matches = N
ans = ''
for _ in range(dp[N]):
    for a in A:
        if matches - m[a] < 0:
            continue
        if dp[matches - m[a]] == dp[matches] - 1:
            matches -= m[a]
            ans += str(a)
            break

print(ans)

Submission status: Accepted

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

A.sort(reverse=True)

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

dp = [-float('inf')] * (N + 1)

dp[0] = 0
for i in range(1, N+1) :
    maxDigit = -float('inf')
    for a in A :
        if i - match[a - 1] >= 0 :
            maxDigit = max(maxDigit, dp[i - match[a - 1]] + 1)
    dp[i] = maxDigit

maxDigit = dp[-1]

r = N

for _ in range(maxDigit) :
    for a in A :
        if r - match[a - 1] < 0 or r < 0 :
            continue
        if dp[r - match[a - 1]] == dp[r] - 1 :
            print(a, end='')
            r -= match[a - 1]
            break

print('')

Submission status: Accepted

Solution code:
a = [2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = sorted(set(list(map(int, input().split()))), reverse=True)
B = sorted([a[i-1] for i in A])

dp = [-1] * (N+1)
for b in B:
    if b < N+1:
        dp[b] = 1

for i in range(1, N+1):
    for b in B:
        if i < b:
            break
        else:
            dp[i] = max(dp[i], dp[i-b]+1)
digit = dp[-1]

for n in A:
    x = a[n-1]
    if N-x >= 0:
        while dp[N-x] == digit-1:
            print(n, end='')
            N -= x
            digit -= 1
        if N == x:
            print(n, end='')
            N -= x

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

NUM = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-float('inf') for _ in range(N + 1)]
dp[0] = 0

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

dights = dp[N]
ans = ""
matchsticks = N
while(dights > 0):
    for a in A:
        if matchsticks - NUM[a - 1] >= 0 and dp[matchsticks - NUM[a - 1]] == dights - 1:
            ans += str(a)
            dights -= 1
            matchsticks -= NUM[a - 1]
            break

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
INF = float('inf')
for i in range(1, N+1):
    t = -INF
    for a in A:
        if i >= x[a]:
            t = max(dp[i-x[a]] + 1, t)
    dp[i] = t

K = N
k = dp[N]
ans = ""
while k > 0:
    for a in A:
        xa = x[a]
        if K >= xa and k == dp[K-xa] + 1:
            ans += str(a)
            K -= xa
            k -= 1
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)
lst = [[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()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 5
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if N - num(A) < 0:
        return False
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    a = sorted(LI())

    t = [9,2,5,5,4,5,6,3,7,6]
    d = {}
    for c in a:
        d[t[c]] = c

    dp = [0] * (n+10)
    for i in range(n):
        if i > 0 and dp[i] < 1:
            continue
        di = dp[i] * 10
        for k,v in d.items():
            t = di + v
            if dp[i+k] < t:
                dp[i+k] = t

    return dp[n]


print(main())

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
use=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0]=0
for i in range(N+1):
    for k in A:
        if i+use[k]<=N:
            dp[i+use[k]]=max(dp[i]+1,dp[i+use[k]])
ans=""
now=N
for i in range(dp[N]):
    for k in A:
        if now-use[k]>=0:
            if dp[now-use[k]]==dp[now]-1:
                ans+=str(k)
                now-=use[k]
                break
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
A = list(map(int, input().split()))

recipe = [2, 5, 5, 4, 5, 6, 3, 7, 6]
available =[]
dp = [-1] * (N + 1)

for i in range(M):
	available.append((A[i], recipe[A[i] - 1]))
	
available.sort(reverse = True)
dp[0] = 0

for i in range(1, N + 1):
	for j in range(M):
		k = i - available[j][1]
		if k >= 0 and dp[k] >= 0:
			if dp[k] + 1 > dp[i]:
				dp[i] = dp[k] + 1

cost = 0
ans = ''

for i in range(dp[N]):
	for j in range(M):
		if N - cost - available[j][1] >= 0 and dp[N - cost - available[j][1]] == dp[N - cost] - 1:
			cost += available[j][1]
			ans += str(available[j][0])
			break
	
print(ans)

Submission status: Accepted

Solution code:
#2 5 5 4 5 6 3 7 6
#ナップザックのdpかな
#dp[i][v] = dp[i-A[i]][v-M[i]*(10*i)]

import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

N,M = na()
A = na()
cost = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

d = {i:cost[i] for i in A}

dp = [-1]*(N+1)
dp[0] = 0
ans = [0]*(N+1)
for i in range(N+1):
    for j in range(10)[::-1]:
        if j not in d:
            continue
        elif d[j] > i:
            continue
        else:
            #print(j)
            if dp[i] < dp[i-d[j]]+1:
                dp[i] = dp[i-d[j]]+1
                ans[i] = j
S = ""
pos = N
#print(dp,ans)
while pos!=0:
    #print(pos)
    S+=str(ans[pos])
    pos-=d[ans[pos]]


print(S)

Submission status: Accepted

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

blist=[False]*10
for a in alist:
  blist[a] = True

match=[6,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)

dp[0]=0
dp[1]=-1
for i in range(N+1):
  for j in range(1,10):
    if blist[j] and i+match[j]<=N:
      if dp[i+match[j]] < dp[i]+1:
        dp[i+match[j]] = dp[i]+1
#print(dp)

answer_str = ""
while(N>0):
  for i in reversed(range(1,10)):
    if blist[i] and N-match[i] >= 0 and dp[N-match[i]] == dp[N]-1:
      answer_str += str(i)
      N -= match[i]
      break
      
print(answer_str)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP=[-float("inf")]*(n+1)
DP[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP[i+1-D[A[j]]]!=float("inf") and DP[i+1-D[A[j]]]+1>=DP[i+1]:
      DP[i+1]=DP[i+1-D[A[j]]]+1
A.sort(reverse=True)
k=DP[n]
ans=""
cur=n
for _ in range(k):
  for j in range(m):
    if cur>=D[A[j]] and DP[cur-D[A[j]]]==DP[cur]-1:
      ans+=str(A[j])
      cur-=D[A[j]]
      break
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
l = min([m[a] for a in A])
dp = [0] * (N + 1)

for i in range(N):
    for a in A:
        if (i > 0) and dp[i] == 0:
            break
        if (i + m[a] <= N):
            dp[i + m[a]] = max(dp[i + m[a]], dp[i] * 10 + a)
print(dp[-1])

Submission status: Accepted

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

dp = [-1]*(N+1)
dp[0] = ''
for a in A:
    if c[a] <= N:
        dp[c[a]] = str(a)

for i in range(N+1):
    for a in A:
        if i-c[a]>=0 and dp[i-c[a]]!=-1:
            if dp[i]==-1 or len(dp[i]) <= len(dp[i-c[a]])+1:
                dp[i] = str(a)+dp[i-c[a]]

ans = sorted(dp[N])
ans = ans[::-1]
ans = ''.join(ans)
print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
c = [0,2,5,5,4,5,6,3,7,6]

dp = [-INF]*(N+1)
dp[0] = 0
for a in A:
    if c[a] <= N:
        dp[c[a]] = 1

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

ans = ''
n = N
for a in A:
    if n-c[a]>=0:
        while dp[n] == dp[n-c[a]]+1:
            n -= c[a]
            ans = ans + str(a)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n + 1)

dp[0] = 0
for i in range(1, n + 1):
    for j in a:
        if i < match[j - 1]:
            continue
        else:
            dp[i] = max(dp[i], dp[i - match[j - 1]] + 1)

num = []
k = n
for i in range(dp[n]):
    for j in a:
        if k >= match[j - 1]:
            if dp[k - match[j - 1]] == dp[k] - 1:
                num.append(j)
                k -= match[j - 1]
                break
print("".join(map(str, num)))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
cost=[2,2,5,5,4,5,6,3,7,6]

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

for i in range(1,n+1):
    p=0
    for j in a:
        if i-cost[j]>=0 and (dp[i-cost[j]]!=0 or i-cost[j]==0):
            p=max(p,int(dp[i-cost[j]]*10+j))
    dp[i]=p

print(dp[n])

Submission status: Accepted

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

maxnum = [-1] * (n+1)
cost = [0,2,5,5,4,5,6,3,7,6]
maxnum[0] = 0
for i in range(n+1):
    for num in a:
        if ( i+cost[num] < n+1 ):
            maxnum[i+cost[num]] = max(maxnum[i+cost[num]], num + maxnum[i]*10)

print(maxnum[n])

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y: return x
	else: return y

matchlist = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
dp = [['', 0]]
for i in range(1, N+1):
	tmp = ''
	tmpmatch = 0
	for j in range(0, len(A)):
		if i-matchlist[A[j]] >= 0:
			if dp[i-matchlist[A[j]]][1]+matchlist[A[j]] == i:
				if len(tmp) < len(dp[i-matchlist[A[j]]][0])+1:
					tmp = larger(dp[i-matchlist[A[j]]][0]+str(A[j]), str(A[j])+dp[i-matchlist[A[j]]][0])
					tmpmatch = dp[i-matchlist[A[j]]][1]+matchlist[A[j]]
				elif len(tmp) == len(dp[i-matchlist[A[j]]][0])+1:
					if tmp != larger(tmp, larger(dp[i-matchlist[A[j]]][0]+str(A[j]), str(A[j])+dp[i-matchlist[A[j]]][0])):
						tmp = larger(dp[i-matchlist[A[j]]][0]+str(A[j]), str(A[j])+dp[i-matchlist[A[j]]][0])
						tmpmatch = dp[i-matchlist[A[j]]][1]+matchlist[A[j]]
	dp.append([tmp, tmpmatch])
print(dp[N][0])

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
List=list(map(int, input().split()))
d=[0]*n*9+[-1]*n*9
for i in range(1, n+1):
    d[i]=max(d[i-int("0255456376"[a])]*10+a for a in List)
print(d[n])

Submission status: Accepted

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

weight=[0,2,5,5,4,5,6,3,7,6]
dp = [-1] * (N+1)
dp[0] = 0
for i in range(N+1):
  for a in A:
    if i+weight[a] < N+1:
      dp[i+weight[a]] = max(dp[i+weight[a]], dp[i]*10+a)
print(dp[N])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a_list=list(map(int,input().split()))
ref=[0,2,5,5,4,5,6,3,7,6]
num=[0,0,0,0,0,0]
for i in a_list:
    if i>num[ref[i]-2]:
        num[ref[i]-2]=i
num_s=[]
for i in range(6):
    num_s.append([num[i],i])
num_s.sort(reverse=True)
temp=[0,0,0,0,0,0]
dp=[[0,0,0,0,0,0]]
for i in range(n):
    sub_list=[-1,-1,-1,-1,-1,-1]
    dp.append(sub_list)
for i in range(1,n+1):
    for j in range(6):
        if i-(j+2)>=0 and not num[j]==0:
            if dp[i-j-2][0]>=0:
                if sum(dp[i-j-2])+1>sum(dp[i]):
                    for k in range(6):
                        dp[i][k]=dp[i-j-2][k]
                    dp[i][j]=dp[i][j]+1
                elif sum(dp[i-j-2])+1==sum(dp[i]):
                    for h in range(6):
                        temp[h]=dp[i-j-2][h]
                    temp[j]=temp[j]+1
                    for k in num_s:
                        if temp[k[1]]>dp[i][k[1]]:
                            for h in range(6):
                                dp[i][h]=temp[h]
                            break
                        elif temp[k[1]]==dp[i][k[1]]:
                            pass
                        else:
                            break
                else:
                    pass
ans=''
for i in num_s:
    ans=ans+str(i[0])*dp[n][i[1]]
print(ans)

Submission status: Accepted

Solution code:
import copy
N, M = map(int, input().split())
A = sorted(map(int, input().split()))

digit2match_num = {i:j for i, j in zip(range(1, 10), [2,5,5,4,5,6,3,7,6])}

match_nums = sorted({digit2match_num[d]: d for d in A}.items())

rest = N


pattern_num = len(match_nums)
i = 0

ans = []

match_num, digit = match_nums[i]
n, rest = divmod(rest, match_num)
ans += [digit] * n

def make_tail(rest_match_num, ans):
  queue = [
    [[], rest_match_num]
  ]
  _ans = copy.copy(ans)
  flag = False
  tail = []
  for i in range(min(len(ans), 5)):
    new_queue = list()
    last_digit = ans.pop()
    last_match_num = digit2match_num[last_digit]
    for nums, rest_match_num in queue:
      rest_match_num += last_match_num
      new_queue.append([nums, rest_match_num])
      for match_num, digit in match_nums:
        if match_num <= rest_match_num:
          if rest_match_num == match_num:
            tail.append(
              sorted((ans + nums + [digit]), reverse=True)
            )
          elif match_num != last_match_num:
            new_queue.append([nums + [digit], rest_match_num - match_num])
        else:
          break
    queue = new_queue
  best = sorted(tail, key=lambda x: (len(x), x), reverse=True)[0]

  return best

# print(ans, rest)
if rest != 0:
  ans = make_tail(rest, ans)
print("".join(map(str, sorted(ans, reverse=True))))

Submission status: Accepted

Solution code:
l = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
dp = [-1] * (n + 10)
dp[0] = 0
for i in range(n):
    for num in a:
        dp[i + l[num]] = max(dp[i + l[num]], dp[i] * 10 + num)
print(dp[n])

Submission status: Accepted

Solution code:
def comp(a,b):
    if sum(a)<sum(b):
        return "right"
    elif sum(a)>sum(b):
        return "left"
    else:
        for i in range(8,-1,-1):
            if a[i]<b[i]:
                return "right"
            elif a[i]>b[i]:
                return "left"
        else:
            return "equal"

N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])
    
maxlist=[[0]*9 for _ in range(N+1)]
 
for i in range(N+1):
    if i!=0 and sum(maxlist[i])==0:
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            ans=[maxlist[i][k] for k in range(9)]
            ans[b[0]-1]+=1
            _max=maxlist[i+b[1]]
            if comp(ans,_max) == "left":
                maxlist[i+b[1]]=[ans[k] for k in range(9)]
 
for i in range(8,-1,-1):
    print(str(i+1)*maxlist[N][i],end="")
print()

Submission status: Accepted

Solution code:
def comp(a,b):
    if sum(a)<sum(b):
        return "right"
    elif sum(a)>sum(b):
        return "left"
    else:
        for i in range(8,-1,-1):
            if a[i]<b[i]:
                return "right"
            elif a[i]>b[i]:
                return "left"
        else:
            return "equal"

N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])

if [5,5] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:    
        B.remove([3,5])

if [3,5] in B and [2,5] in B:
    B.remove([2,5])

if [7,3] in B:
    if [6,6] in B:
        B.remove([6,6])
    if [9,6] in B:
        B.remove([9,6])
    
if [9,6] in B and [6,6] in B:
    B.remove([6,6])

if [1,2] in B and [7,3] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:
        B.remove([3,5])
    if [5,5] in B:
        B.remove([5,5])
    if [8,7] in B:
        B.remove([8,7])

if [1,2] in B and ([2,5] in B or [3,5] in B or [5,5] in B) and [8,7] in B:
    B.remove([8,7])
    
if [4,4] in B and [7,3] in B and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])
    
maxlist=[[0]*9 for _ in range(N+1)]
 
for i in range(N+1):
    if i!=0 and sum(maxlist[i])==0:
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            #ans=maxlist[i]+str(b[0])
            ans=[maxlist[i][k] for k in range(9)]
            ans[b[0]-1]+=1
            _max=maxlist[i+b[1]]
            if comp(ans,_max) == "left":
                maxlist[i+b[1]]=[ans[k] for k in range(9)]
 
for i in range(8,-1,-1):
    print(str(i+1)*maxlist[N][i],end="")
print()

Submission status: Accepted

Solution code:
def chmax(a, b):
    if a == 'X':
        a = b
    elif len(a) < len(b):
        a = b
    elif len(a) == len(a):
        if a < b:
            a = b
    return a

match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = ['X' for _ in range(10010)]

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

dp[0] = ''

for i in range(N-1):
    if dp[i] == 'X':
        continue
    for a in A:
        dp[i+match[a-1]] = chmax(dp[i+match[a-1]], dp[i] + str(a))

print(dp[N])

Submission status: Accepted

Solution code:
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*10
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    if x <= N:
        dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if t-x>=0:
            if dp[t-x]+1 == dp[t]:
                W[V[x]] += 1
                t -= x
                break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)