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:
N, M = map(int, input().split())
A = list(map(int, input().split()))
match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

# キーはマッチの本数、値は桁数を入れる辞書。マッチ本数が0本の場合も考慮したいので、range(N+1)としている
dp = [-1 for i in range(N + 1)]

cost = []
for i in range(M):
    cost.append([A[i], match[A[i]]])

dp[0] = 0


for i in range(N): # マッチの本数分ループする
    for k in range(M): # 今回使える整数分だけループ
        if i + 1 - cost[k][1] >= 0: # 整数kが使えるだけのマッチの本数がある場合
            dp[i + 1] = max(dp[i + 1], dp[i + 1 - cost[k][1]] + 1) # (指定したマッチの本数 - 新しい整数を入れるのに要した本数) + 1が桁数となる。


tmp = 0 #使ったマッチの数
res = ''
cost.sort(key=lambda x: x[0], reverse=True) # 今回使える整数を、大きい順にソート

for i in range(dp[N]):
    for j in range(M):
        if N - cost[j][1] - tmp >= 0: # 全マッチ本数 - 整数のコスト - 今まで使ったマッチ本数>= 0
            if dp[N - cost[j][1] - tmp] == dp[N - tmp] - 1:
                '''
                左辺:まだ残っているマッチ本数から対象の整数を利用した場合の桁数
                右辺:まだ残っているマッチで実現できる桁数-1
                '''
                res = res + str(cost[j][0])
                tmp += cost[j][1]
                break # 対象桁ごとに、何らかの整数が入ったらそこでおしまいにする
            
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

ma.sort()
print(dfs(N))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			d = dfs(num - ma_map[p])
			if d == -1: continue
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

ma.sort()
print("{}".format(dfs(N)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
match = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

dp = [-1 for i in range(N + 1)]

cost = []
for i in range(M):
    cost.append([A[i], match[A[i]]])

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

tmp = 0 #使ったマッチの数
res = ''
cost.sort(key=lambda x: x[0], reverse=True)
for i in range(dp[N]):
    for j in range(M):
        if N - cost[j][1] - tmp >= 0:
            if dp[N - cost[j][1] - tmp] == dp[N - tmp] - 1:
                res = res + str(cost[j][0])
                tmp += cost[j][1]
                break
            
print(res)

Submission status: Accepted

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

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

for i in range(1, n+1):
    for a_j in a:
        i_prev = i - n_use[a_j]
        if i_prev < 0:
            continue
        else:
            dp[i] = max(dp[i], dp[i_prev]*10+a_j)
# print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] + [-N] * N
for x in range(1, N + 1):
    mx = -N
    for j in range(M):
        num = x - m[A[j]]
        if num >= 0:
            if mx < dp[num] + 1:
                mx = dp[num] + 1
    if mx < 0:
        dp[x] = -N
    else:
        dp[x] = mx

A.sort(reverse=True)
nd = dp[N]
n = N
for i in range(N):
    for a in A:
        if n >= m[a] and dp[n - m[a]] == nd - 1:
            nd -= 1
            n -= m[a]
            print(a, end="")
            break
print()

Submission status: Accepted

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

# 0初期化ではダメ。組合せ不可を表し、演算しても問題ない状態にしておく
dp=[-float("inf")] * (N+1)
dp[0]=0

cost =[0, 2,5,5,4,5,6,3,7,6]
for i in range(N+1):
    for a in A:
      # -inf初期化なので、不可能なものの演算結果も同じ
       new_i = i + cost[a]
       if new_i <= N:
        dp[new_i] = max([dp[new_i],  dp[i]+1])

sa = sorted(A, reverse=True)
n = N
ans = 0
while n > 0:
  for a in sa:
    nn = n-cost[a]
    if nn >= 0 and dp[n] == dp[nn] +1:
      ans = ans * 10 + a
      n -= cost[a]
      break

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
INF = 10 ** 6
match_dict = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5,
              6: 6, 7: 3, 8: 7, 9: 6}

a_list = list(map(int, input().split()))
a_sorted = sorted(a_list, reverse=True)

dp = [0, -INF]

for i in range(2, n + 1):
    tmp_dp = []
    for a in a_sorted:
        if i - match_dict[a] < 0:
            tmp_dp.append(-INF)
        else:
            tmp_dp.append(dp[i - match_dict[a]] + 1)
    dp.append(max(tmp_dp))

sum_str = ''
tmp_i = n
while tmp_i > 0:
    for a in a_sorted:
        if tmp_i >= match_dict[a] and dp[tmp_i - match_dict[a]] == dp[tmp_i] - 1:
            sum_str = sum_str + str(a)
            tmp_i = tmp_i - match_dict[a]
            break

print(int(sum_str))

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

c = []

for x in a:
    if x in [1, 4, 7, 8]:
        c.append((x, b[x - 1]))

if 5 in a:
    c.append((5, 5))
elif 3 in a:
    c.append((3, 5))
elif 2 in a:
    c.append((2, 5))

if 9 in a:
    c.append((9, 6))
elif 6 in a:
    c.append((6, 6))

c = sorted(c, key=itemgetter(1), reverse=True)

dp = [-999999 for _ in range(n + 1)]
dp[0] = 0

for i in range(2, n + 1):
    for x, y in c:
        if i >= y:
            dp[i] = max(dp[i], dp[i - y] + 1)
    #print(i, dp)

c = sorted(c, key=itemgetter(0), reverse=True)

#print(c)
#print(dp)

s = []
k = dp[n]
while k > 0:
    #print(s, k)
    #input()
    for x, y in c:
        if n >= y:
            if dp[n - y] == k - 1:
                s.append(str(x))
                k -= 1
                n -= y
                break

print(int(''.join(s)))

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-1 for i in range(n+1)]
dp[0]=0
for i in range(n+1):
    #max_tmp = -float("inf")
    for j in am:
        if i+c[j-1]<=n:
            dp[i+c[j-1]] = max(dp[i+c[j-1]], dp[i]+1)
#print(dp)
tmp_n = n
ans =""
for i in range(dp[n]):
    for j in range(m):
        if i==dp[n]-1 and tmp_n- c[am[j]-1] != 0:
            continue
        if tmp_n - c[am[j]-1] >= 0 and dp[tmp_n - c[am[j]-1]] == dp[tmp_n] -1:
            ans+=(str(am[j]))
            tmp_n -= c[am[j]-1]
            break


print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
INF = 10**5
COST = [INF,2,5,5,4,5,6,3,7,6]
digit = [-INF]*(N+1)
digit[0] = 0
for i in range(1, N+1):
    for a in A:
        c = COST[a]
        if i - c < 0:
            continue
        digit[i] = max(digit[i], 1 + digit[i-c])
ans = ''
n = N
for i in range(digit[N], 0, -1):
    for a in A:
        new_n = n - COST[a]
        if new_n < 0 or digit[new_n] < i - 1:
            continue
        ans += str(a)
        n = new_n
        break
print(ans)

Submission status: Accepted

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

def num(key):
    if key == 1:
        return 2
    elif key == 7:
        return 3
    elif key == 4:
        return 4
    elif key == 9 or key == 6:
        return 6
    elif key == 8:
        return 7
    else:
        return 5

N, M, = readline().split()
N = int(N)
M = int(M)
A = list(map(int, readline().split()))
A.sort(reverse = True)
dp = [-float('inf'),] *(N+1)
dp[0] = 0
for i in range(1, N+1):
    temp = []
    for j in range(M):
        if i - num(A[j]) >= 0:
            temp.append(dp[i-num(A[j])] + 1)
    if len(temp) > 0:
        dp[i] = max(temp)

digit = dp[N]
ans = []
for i in range(digit):
    for j in range(M):
        if N - num(A[j]) >= 0 and dp[N-num(A[j])] == dp[N] - 1:
            ans.append(A[j])
            N = N - num(A[j])
            break
for i in range(digit):
    write(str(ans[i]))
write("\n")

Submission status: Accepted

Solution code:
from collections import defaultdict

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

# マッチと数字の対応表を作る
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
mat = []
for i in range(m):
    mat.append((match[a[i]-1], a[i]))

d = defaultdict(int)
for ma, num in mat:
    d[ma] = max(d[ma], num)

# dp[i]: マッチをi本使ってできる整数のケタの最大値
INF = float('inf')
dp = [-INF] * (n+10)
dp[0] = 0

for i in range(n):
    if dp[i] == -INF:
        continue
    for ma, num in mat:
        if dp[i] + 1 > dp[i+ma]:
            dp[i+ma] = dp[i] + 1

mat.sort(key=lambda x: x[1], reverse=True)

# 経路復元
ans = ""
i = n
while i > 0:
    for ma, num in mat:
        if i - ma < 0:
            continue
        if dp[i] == dp[i-ma] + 1:
            ans += str(num)
            i -= ma
            break

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
num = [0,2,5,5,4,5,6,3,7,6]
#      0,1,2,3,4,5,6,7,8,9

def f(n,al):
    INF = 10**18
    dp = [-INF for _ in range(n+1)]
    dp[0] = 0

    for i in range(1,n+1):
        for a in al:
            if i-num[a]>=0:
                dp[i] = max(dp[i], dp[i-num[a]]+1)

    res = []
    al.sort(reverse=True)

    while n>0:
        for a in al:
            if n-num[a]>=0 and dp[n-num[a]]==dp[n]-1:
                res.append(str(a))
                n -= num[a]
                break

    return "".join(res)

if __name__ == '__main__':
    n,m = map(int, input().split())
    al = list(map(int, input().split()))
    print(f(n,al))

    # from random import shuffle
    # for _ in range(1000):
    #     n = 10000
    #     m = 5
    #     al = list(range(1,10))
    #     shuffle(al)
    #     al = al[:m]
    #     f(n,al)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
honsuu = [0,2,5,5,4,5,6,3,7,6]
aval = []
for a in A:
  aval += [honsuu[a]]
aval.sort()
 
dp = [0]+ [-float("INF")]*N 

for i in range(1,N+1):
  for b in aval:
    if i < b:
      continue
    elif dp[i-b] >= 0:
      dp[i] = dp[i-b] + 1
      break

A.sort(reverse=True)
ans = []
for i in range(dp[N],1,-1):
  for a in A:
    if N - honsuu[a] < 0:continue
    if dp[N - honsuu[a]] == dp[N] - 1:
      N -= honsuu[a]
      ans += [a]
      break
      
final = 0
for i in range(10):
  if i in A and honsuu[i] == N:
    final = i
ans += [final]
print(''.join(map(str, ans)))

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
value=sorted(list(map(int,input().split())), reverse=True)
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 j in value:
        if i + weight[j] < n+1:
            dp[i+weight[j]] = max(dp[i+weight[j]],dp[i]*10+j)
print(dp[n])

Submission status: Accepted

Solution code:
inf = float("inf")
N, M = map(int, input().split())
A = map(int, input().split())
C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
costs = {m: C[m - 1] for m in A}
dp = [0]
for i in range(1, N + 1):
    dp.append(
        max([dp[i - c] if i - c >= 0 else -inf for c in costs.values()]) + 1)

digits = list(costs.keys())
digits = sorted(digits, reverse=True)
num = N
result = []
for _ in range(dp[N]):
    for digit in digits:
        if num >= costs[digit] and dp[num - costs[digit]] != -inf and dp[num - costs[digit]] == dp[num] - 1:
            result.append(str(digit))
            num -= costs[digit]
            break
print("".join(result))

Submission status: Accepted

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

Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}
dp = [-1 for _ in range(N + 1)]
dp[0] = 0
for a in sorted(A, reverse=True):
    c = Matches[a]
    for i in range(N - c + 1):
        if dp[i] == -1:
            continue
        dp[i+c] = max(dp[i+c], dp[i] * 10 + a)

print(dp[N])

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split()]
a = sorted([int(x) for x in input().split()])
INF = 10**9

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

keta = [-INF for _ in range(N+1)]
keta[0] = 0
for i in range(1, N+1):
    cand = [keta[i-num[aa]] for aa in a if i-num[aa] >= 0]
    if len(cand) > 0:
        keta[i] = max(cand) + 1

n = N
ans = ""
while n > 0:
    cand = [aa for aa in a if n-num[aa] >= 0 and keta[n]-1 == keta[n-num[aa]]]
    if len(cand) > 0:
        ans += str(cand[-1])    # ソートしてるので。
        n = n - num[cand[-1]]
print(ans)

Submission status: Accepted

Solution code:
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  if i[0] - 1 < N:
    dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if max(dp[i]) == 0:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      if sum(t) > sum(dp[k]):
        dp[k] = t
      else:
        for ii in range(9, 0, -1):
          if t[ii] > dp[k][ii]:
            dp[k] = t
            break
          elif t[ii] < dp[k][ii]:
            break
          
t = dp[-1]
Ans = ""
for i in range(9, 0, -1):
  for j in range(t[i]):
    Ans += str(i)
    
print(Ans)

Submission status: Accepted

Solution code:
from fractions import *
from collections import *
n, m = map(int,input().split())
a = sorted(map(int,input().split()))[::-1]
c = [0,2,5,5,4,5,6,3,7,6]
mi = min(a, key=lambda x: c[x])
x = sum(c[i]*c[mi]//gcd(c[i],c[mi]) for i in a if i!=mi)
q, r = divmod(max(0, n-x), c[mi])
n = min(n, x+r)
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(2, n+1):
    for j in a:
        if i >= c[j]:
            dp[i] = max(dp[i], dp[i-c[j]]+1)
d = Counter()
d[mi] += q
while n:
    i = max((i for i in a if n>=c[i]), key=lambda x: dp[n-c[x]])
    d[i] += 1
    n -= c[i]
print(''.join(str(k)*d[k] for k in sorted(d)[::-1]))

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
value=sorted(list(map(int,input().split())))[::-1]
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 j in value:
        if i + weight[j] < n+1:
            dp[i+weight[j]] = max(dp[i+weight[j]],dp[i]*10+j)
print(dp[n])

Submission status: Accepted

Solution code:
INF = float('inf')

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

num = [N + 1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# num[数字] = 必要なマッチ棒の本数
# 数字0は使用できない

dp = [-INF for _ in range(N + 1)]
dp[0] = 0
# dp[マッチ棒の本数] = 構成可能な最大桁数
# 最大桁数を求めるので、初期値-INFとして、maxで更新

for i in range(1, N + 1):
    for aa in a:
        # aa: 使用可能な数字
        idx = i - num[aa]
        if idx >= 0:
            dp[i] = max(dp[i], dp[idx] + 1)

a = list(sorted(a, reverse=True))
# 降順ソート

need = dp[N]
# 構成可能な最大整数が必要とする桁数

rest = N
# 使用可能なマッチ棒の本数

ans = ''

while need > 0:
    for aa in a:
        # aa: 使用可能な数字（降順）
        idx = rest - num[aa]
        if idx >= 0:
            # マッチ棒の本数が足りるため、数字aaを使用できる場合
            if dp[idx] == need - 1:
                ans += str(aa)
                # ans末尾にaaを追記

                rest -= num[aa]
                need -= 1

                break
                # 次の桁の調査でaa[0]から試すため
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
mt=[0,2,5,5,4,5,6,3,7,6]
a=sorted(map(int, input().split()))[::-1]
dp=[-1]*(n+1)
dp[0]=0
for i in range(n+1):
    if dp[i]==-1:continue
    for j in a:
        if i+mt[j]<n+1:
            dp[i+mt[j]]=max(dp[i]*10+j,dp[i+mt[j]])
print(dp[-1])

Submission status: Accepted

Solution code:
#python3.4
import math
def inpul(): return list(map(int, input().split()))

N, M = inpul()
A = inpul()

c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010

f[0] = 0
for i in range(1, N+1):
	for x in A:
		if i-c[x] >= 0:
			f[i] = max(f[i], f[i-c[x]]*10+x)
print(f[N])

Submission status: Accepted

Solution code:
B_arr = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

N, M = (int(x) for x in input().split())
A_arr = [int(x) for x in input().split()]

d = [-1]*(10*N)
d[0] = 0

for i in range(1, N+1):
    for A in A_arr:
        d[i] = max(d[i], d[i-B_arr[A]]*10+A)

print(d[N])

Submission status: Accepted

Solution code:
T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

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


P=[]
for i in A:
	P.append(T[i-1])


dp=[ None for i in range(N+1) ]
dp[0]=""


for i in range(N):
	#print "i :::: ",i,dp
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:

				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )


print dp[N]

Submission status: Accepted

Solution code:
# intのn, mに入力のNとMを，aに配列として，使用できる数であるA_1 ~ A_jを入力する
n,m,*a=map(int,open(0).read().split())

# d[0]: dpi(0)=0を表す
# 使用できるマッチの本数N * 9の-1を用意する(9は，全マッチ棒を使用した場合の領域も確保している)
"""
d: [マッチ棒が0の時は0,
    
"""
d=[0]+[-1]*n*9

# 1 ~ (使用できるマッチ棒の本数)までの最大桁数(解説のdpi(N-1)に相当)を全探索で求める
for i in range(1,n+1):
    # d[1] ~ d[n]を全探索で求める
    # d[i]は次のaの各要素jの最大値
    #   max{j + d[i - (jの数を作るのに必要なマッチの本数)] * 10 } (つまり，jは一番下の桁に使う)
    d[i]=max(j + d[i-int('0255456376'[j])]*10 for j in a)
print(d[n])

Submission status: Accepted

Solution code:
n,m,*a=map(int,open(0).read().split())
d=[0]+[-1]*n*9
for i in range(n):d[i+1]=max(j+d[i-int('0144345265'[j])]*10 for j in a)
print(d[n])

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()                        # 破壊的。返り値はNone

# print(N, M)
# print(a)

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


dp = [-999 for _ in range(N+1)]
dp[0] = 0
for i in range(N+1):
    n = [dp[i-num[a[j]]] for j in range(M) if i-num[a[j]] >= 0]
    if len(n) > 0:
        dp[i] = max(n) + 1

# print(dp)

i = N
ans = ""
for _ in range(dp[N]):
    # print("i", i)
    # c = [(a[j], dp[i-num[a[j]]], dp[i]) for j in range(M)]
    # print("c", c)
    if dp[i] > 1:
        b = max([a[j] for j in range(M)
                 if i - num[a[j]] >= 0 and dp[i-num[a[j]]] + 1 == dp[i]])
        ans += str(b)
    else:
        b = max([a[j] for j in range(M)
                 if i - num[a[j]] == 0 and dp[i-num[a[j]]] + 1 == dp[i]])
        ans += str(b)
        break
    # print("ans", ans)
    i = i-num[b]
    # print(i)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=list(map(int,input().split()))
seg0=[0,2,5,5,4,5,6,3,7,6]

import numpy as np

A.sort(reverse=1)
seg=[]
for i in range(m):
    seg.append(seg0[A[i]])

#print(seg)

keta=[-np.inf for i in range(n+1)]
keta[0]=0
for i in range(1,n+1):
    for j in range(m):
        if i-seg[j]>=0 :
            keta[i]=max(keta[i],keta[i-seg[j]]+1)

#print(keta)

ke=keta[n]

#print(ke)
#print(seg)
ans=0
while ke>1 :
    for j in range(m):
        #print(n-seg[j])
        #print(keta[n-seg[j]])
        if n-seg[j]>0 and keta[n]==keta[n-seg[j]]+1 :
            ans+=A[j]*10**(ke-1)
            n-=seg[j]
            #print(ans)
            break
    ke-=1

#print(n)
for i in range(m):
    #print(keta[n])
    if n==seg[i] :
        ans+=A[i]
        break

print(ans)

Submission status: Accepted

Solution code:
n, m = [int(elem) for elem in input().split()]
a = [elem for elem in input().split()]
a = sorted(a, reverse=True)

num_dict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}
dp = ["" for _ in range(n+1)]

for i in range(n+1):
    for strnum in a:
        if i - num_dict[strnum] < 0:
            continue
        if i - num_dict[strnum] == 0 and dp[i] == "":
            dp[i] = strnum
        pre_strnum = dp[i - num_dict[strnum]]
        if pre_strnum != "":
            if len(pre_strnum) + 1 > len(dp[i]):
                dp[i] = pre_strnum + strnum

print("".join(sorted(dp[n], reverse=True)))

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
A = sorted([s for s in input().split()], reverse=True)
numDict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}
dp = ["" for _ in range(N + 1)]

for i in range(N + 1):
    for strNum in A:
        if i - numDict[strNum] < 0:
            continue
        if i - numDict[strNum] == 0 and dp[i] == "":
            dp[i] = strNum
        preStrNum = dp[i - numDict[strNum]]
        if preStrNum != "":
            if len(preStrNum) + 1 > len(dp[i]):
                dp[i] = preStrNum + strNum

print("".join(sorted(dp[N], reverse=True)))

Submission status: Accepted

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

#最小本数で作成可能な数字をリスト化
creat_A=[]
for n in A:
  creat_A.append(num[n-1])

#dp[N]:N本のマッチ棒を使って作ることのできる最大桁数
dp=[-1 for _ in range(N+1)]
for i in range(M):
  if creat_A[i] <= N:
    dp[creat_A[i]]=1

for i in range(N):
  if dp[i]>0:
    for j in range(M):
      if i+creat_A[j] <= N:
        dp[i+creat_A[j]]=max(dp[i+creat_A[j]],dp[i]+1)

#dp[N]から使用した数字の数を算出。
ans=[0 for _ in range(10)]

now=N
while dp[now] > 0:
  res=-1
  temp_i=-1
  for i in range(M):
    if now-creat_A[i] >0 and dp[now-creat_A[i]]==dp[now]-1:
      if res < A[i]:
        res=A[i]
        temp_i=i
  if res==-1:
    break
  else:
    ans[res]+=1
    now-=creat_A[temp_i]
    
temp2=0
for i in range(M):
  if creat_A[i]==now:
    temp2=max(temp2,A[i])
ans[temp2]+=1

#答えの出力。最小から加えて逆向きに読めばOK
ansans=""
for i in range(10):
  if ans[i]>0:
    ansans+=(str(i)*ans[i])
ansans=ansans[::-1]
print(ansans)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
l = map(int, raw_input().split())
dp = [-1]*(n+10)
dp[0] = 0
cost = [0,2,5,5,4,5,6,3,7,6]
for i in range(1, n + 1):
    for j in l:
        if cost[j] <= i:
            dp[i] = max(dp[i], dp[i-cost[j]]*10 + j)
print dp[n]

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
#
# n,m = map(int,input().split())
# a = [int(i) for i in input().split()]
#
# translate_match=[2,5,5,4,5,6,3,7,6]
# match = []
# for i in range(m):
#     match.append(translate_match[a[i]-1])
#
# # def dp(amari,memory):
# #     for i in range(len(match)):
# #         if amari==match[i]:
# #             print(memory)
# #             break
# #         elif amari>match[i]:
# #             next = amari-match[i]
# #             memory[i] += 1
# #             dp(next,memory)
#
# # ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
#
# dp = [0]+[-1]*n
#
#
# for left_match in range(1,n+1):
#     # print(dp)
#     for j in range(len(match)):
#         if match[j]<=left_match:
#             dp[i] = max(dp[i],dp[left_match-match[j]]*10+a[j])
#             print(dp)
#
#
# print(dp[1])

def solve():
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    A.sort(reverse = True)
    #print(A)
    dp = [0] + ([-1]*N)
    #print(dp)
    for i in range(1, N+1):
        for a in A:
            if L[a] <= i:
                # print(dp)
                dp[i] = max(dp[i], dp[i-L[a]] * 10 + a)
    # print(dp)
    print(dp[-1])


if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
def func(latter, remains, former = []):
    #print(remains, former, latter)
    if remains == 0:
        return sum(x for _,x in former)
    if len(latter) == 0:      # 諦めて戻る
        while True:
            b, p = former.pop()    # formerの先頭から順に取り出し
            if p==0:               # ゼロの間は
                latter.append(b)   # latterに入れて
            else:             # ゼロでないものが見つかった時
                break         # ストップ
        return func(latter, remains+b, former+[(b, p-1)])
    a = latter.pop()
    q, r = divmod(remains, a)
    if r!=0: # 端数が出た時
        q = q-1 if q > 0 else 0  # ひとつ以上入るなら、ひとつ減らして入れ、入らないなら入れない
    return func(latter, remains-q*a, former+[(a, q)])

def func2(l, remains, remain_num, ans=[]):
    #print(l, remains, remain_num, ans)
    if len(l)>0:
        a, *l = l
        for i in range(min(remains//a, remain_num)+1):
            yield from func2(l, remains-a*i, remain_num-i, [(a, i)]+ans)
    elif remain_num==0 and remains==0:
        yield ans

n, m = map(int, input().split())
s = sorted((int(x) for x in input().split()), reverse=True)
num = [6,2,5,5,4,5,6,3,7,6]
t = sorted({num[i] for i in s}, reverse=True)
t_rev = {x:max(j for j in s if num[j]==x) for x in t}
t_min = t[-1]
m_num = func(t.copy(), n)   # 桁数
max_replacement = n - m_num*t_min        # 最小マッチでない数以外の数を最大何個使えるか
min_match_num = max(0, m_num - max_replacement)  # 最小マッチ数の数を少なくともどれだけ使うか
other_num = m_num - min_match_num   # 残された桁数
def func3(ans):
    l = {t_rev[x]:(i+min_match_num if x==t_min else i) for x,i in ans}
    return [l[x] for x in sorted(l, reverse=True)]
answer = max(func3(ans) for ans in func2(t.copy(), n-min_match_num*t_min, other_num))
print(*(str(x)*i for x, i in zip(sorted(t_rev.values(), reverse=True), answer)), sep='')

Submission status: Accepted

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

C = [None,2,5,5,4,5,6,3,7,6]
#使ったマッチの本数
dp = [-1 for _ in range(N+7)]
dp[0] = 0

for i in range(N+1):
  for j in A:
    if C[j] <= i:
      dp[i] = max(dp[i-C[j]]*10 + j, dp[i])

print(dp[N])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
if 1 in A:
    if 4 in A: A.remove(4)
    if 6 in A: A.remove(6)
    if 9 in A: A.remove(9)
if 3 in A:
    if 2 in A: A.remove(2)
if 5 in A:
    if 3 in A: A.remove(3)
    if 2 in A: A.remove(2)
if 7 in A:
    if 6 in A: A.remove(6)
    if 9 in A: A.remove(9)
if 9 in A:
    if 6 in A: A.remove(6)

def MatchNum(i):
    if i == 1: return 2
    elif i == 4: return 4
    elif i in [2, 3, 5]: return 5
    elif i == 7: return 3
    elif i == 8: return 7
    elif i in [6, 9]: return 6

MatchUse = []
for a in A:
    MatchUse.append((a, MatchNum(a)))

DP = [-1] * (N+1)
for a, num in MatchUse:
    if num <= N: DP[num] = a

for i in range(2, N):
    if DP[i] > 0:
        temp = DP[i]*10
        for a, num in MatchUse:
            if i + num <= N:
                DP[i + num] = max(DP[i + num], a + temp)
print(DP[N])

Submission status: Accepted

Solution code:
w, n = map(int, input().split())
A0 = list(map(int, input().split()))
C = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A = []
for i in range(n):
    A.append([A0[i], C[A0[i]]])

dp = [-1] * (w + 1)
dp[0] = 0
for i in range(w + 1):
    for j in range(n):
        if A[j][1] <= i:
            dp[i] = max(dp[i], dp[i - A[j][1]] * 10 + A[j][0])
            
print(dp[w])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N, M = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)

inf = float('inf')
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0] + [-inf] * N
for i in range(N + 1)[1::]:
    for x in A:
        if i >= num[x]:
            dp[i] = max(dp[i], dp[i - num[x]] + 1)

ans = ''
while N > 0:
    for x in A:
        if N >= num[x] and dp[N - num[x]] == dp[N] - 1:
            ans += str(x)
            N -= num[x]
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
mat = []
for i in range(m):
    mat.append((match[a[i]-1], a[i]))

d = defaultdict(int)
for ma, num in mat:
    d[ma] = max(d[ma], num)

# dp[i]: マッチをi本使ってできる整数のケタの最大値
INF = float('inf')
dp = [-INF] * (n+10)
dp[0] = 0

for i in range(n):
    if dp[i] == -INF:
        continue
    for ma, num in mat:
        if dp[i] + 1 > dp[i+ma]:
            dp[i+ma] = dp[i] + 1

mat.sort(key=lambda x: x[1], reverse=True)

ans = ""
i = n
while i > 0:
    for ma, num in mat:
        if i - ma < 0:
            continue
        if dp[i] == dp[i-ma] + 1:
            ans += str(num)
            i -= ma
            break

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 自力実装できず
#
# 解説PDFが理解できなかったので
# http://drken1215.hatenablog.com/entry/2019/02/16/224100
# を参考に実装

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys


def str_max(s1, s2):
    if len(s1) > len(s2):
        return s1
    elif len(s1) < len(s2):
        return s2
    if s1 > s2:
        return s1
    else:
        return s2


def main():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))
    
    needs = [0,2,5,5,4,5,6,3,7,6]
    need_to_ch = {}
    for a in sorted(As):
        need = needs[a]
        need_to_ch[need] = str(a)
    
    dp = [None for _ in range(N + 1)]
    dp[0] = ''
    for i in range(1, N + 1):
        for need, ch in need_to_ch.items():
            if i - need < 0 or dp[i - need] is None:
                continue
            cand = dp[i - need] + ch
            if dp[i] is None:
                dp[i] = cand
            else:
                dp[i] = str_max(dp[i], cand)
        # print("dp[{}] = {}".format(i, dp[i]))
    print(dp[N])


main()

Submission status: Accepted

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

d = [-1]*(n+1)
d[0] = 0

for i in range(n+1):
    for ai in a:
        if (i - c[ai]) >= 0:
            d[i] = max(d[i], d[i-c[ai]]*10 + ai)

print(d[-1])

Submission status: Accepted

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

dp = [-1 for _ in range(10010)]
dp[0] = 0            

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

for i in range(1,10005):
    for x in A:          
        if i-MatchNum[x] >= 0:
            tmp = dp[i-MatchNum[x]]*10 + x
            dp[i] = max(tmp,dp[i])
print(dp[N])