Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

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

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

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

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

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

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(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(9)
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
DP1,DP2=[-float("inf")]*(n+1),[[]]*(n+1)
DP1[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP1[i+1-D[A[j]]]!=-float("inf") and DP1[i+1-D[A[j]]]+1>=DP1[i+1]:
      DP1[i+1]=DP1[i+1-D[A[j]]]+1
      x,y=0,0
      X,Y=DP2[i+1],DP2[i+1-D[A[j]]]+[A[j]]
      X.sort(reverse=True)
      Y.sort(reverse=True)
      for xx in X:
        x=x*10+xx
      for yy in Y:
        y=y*10+yy
      if y>x:
        DP2[i+1]=DP2[i+1-D[A[j]]]+[A[j]]
ans=0
DP2[n].sort(reverse=True)
for i in DP2[n]:
  ans=ans*10+i
print(ans)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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: Wrong Answer

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)
d = {l[i]: i for i in reversed(a)}
dp = [-1] * (n + 10)
dp[0] = 0
prev = [-1] * (n + 10)
for i in range(n):
    for num in a:
        if dp[i] != -1 and dp[i + l[num]] < dp[i] + 1:
            dp[i + l[num]] = dp[i] + 1
            prev[i + l[num]] = i
ans = 0
i = n
while prev[i] != -1:
    ans *= 10
    ans += d[i - prev[i]]
    i = prev[i]
print(''.join(sorted(str(ans), reverse=True)))

Submission status: Wrong Answer

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)
d = {l[i]: i for i in reversed(a)}
dp = [0] * (n + 10)
prev = [-1] * (n + 10)
for i in range(n):
    for num in a:
        if dp[i + l[num]] < dp[i] + 1:
            dp[i + l[num]] = dp[i] + 1
            prev[i + l[num]] = i
ans = 0
i = n
while prev[i] != -1:
    ans *= 10
    ans += d[i - prev[i]]
    i = prev[i]
print(''.join(sorted(str(ans), reverse=True)))

Submission status: Wrong Answer

Solution code:
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] and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])

maxlist=[""]*(N+1)
 
for i in range(N+1):
    if i!=0 and maxlist[i]=="":
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            ans=maxlist[i]+str(b[0])
            _max=maxlist[i+b[1]]
            if len(ans)<len(_max):
                continue
            elif len(ans)>len(_max):
                maxlist[i+b[1]] = ans
            else:
                for j in range(len(ans)):
                    if ans[j]<_max[j]:
                        break
                    if ans[j]>_max[j]:
                        maxlist[i+b[1]] = ans
                        break
 
print(maxlist[N])

Submission status: Wrong Answer

Solution code:
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] and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])

maxlist=[""]*(N+10)
 
for i in range(N+1):
    if i!=0 and maxlist[i]=="":
        continue
    else:
        for b in B:
            ans=maxlist[i]+str(b[0])
            _max=maxlist[i+b[1]]
            if i+b[1]>N:
                continue
            if len(ans)<len(_max):
                continue
            elif len(ans)>len(_max):
                maxlist[i+b[1]] = ans
            else:
                for j in range(len(ans)):
                    if ans[j]>_max[j]:
                        maxlist[i+b[1]] = ans
 
print(maxlist[N])

Submission status: Wrong Answer

Solution code:
def concat(a,b):
	return int(str(a)+str(b))


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])

print(B)
maxlist=[0]*(N+10)

for i in range(N+1):
	if i!=0 and maxlist[i]==0:
		continue
	else:
		for b in B:
			if concat(maxlist[i],b[0]) > maxlist[i+b[1]]:
				maxlist[i+b[1]] = concat(maxlist[i],b[0])

print(maxlist[N])

Submission status: Wrong Answer

Solution code:
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]
  ]
  flag = False
  tail = []
  while True:
    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:
          match_num != last_match_num
          new_queue.append([nums + [digit], rest_match_num - match_num])
        elif rest_match_num == match_num:
          tail.append(sorted(nums + [digit], reverse=True))
          flag = True
        else:
          break
    if flag: break
    queue = new_queue
  return ans + sorted(tail, reverse=True)[0]


if rest != 0:
  ans = make_tail(rest, ans)


print("".join(map(str, sorted(ans, reverse=True))))

Submission status: Wrong Answer

Solution code:
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]
  ]
  flag = False
  tail = []
  while True:
    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:
          match_num != last_match_num
          new_queue.append([nums + [digit], rest_match_num - match_num])
        elif rest_match_num == match_num:
          tail.append(sorted(nums + [digit], reverse=True))
          flag = True
        else:
          break
      if flag: break
    if flag: break
    queue = new_queue
  return ans + sorted(tail, reverse=True)[0]


if rest != 0:
  ans = make_tail(rest, ans)


print("".join(map(str, sorted(ans, reverse=True))))

Submission status: Wrong Answer

Solution code:
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 = []
while True:
  if i == pattern_num:
    break
  match_num, digit = match_nums[i]

  if match_num <= rest:
    n, rest = divmod(rest, match_num)
    ans += [digit] * n
  else:
    i += 1

def make_tail(rest_match_num, ans):
  queue = [
    [[], rest_match_num]
  ]
  flag = False
  tail = []
  while True:
    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:
          match_num != last_match_num
          new_queue.append([nums + [digit], rest_match_num - match_num])
        elif rest_match_num == match_num:
          tail = nums + [digit]
          flag = True
          break
        else:
          break
      if flag: break
    if flag: break
    queue = new_queue
  return ans + tail


if rest != 0:
  ans = make_tail(rest, ans)


print("".join(map(str, sorted(ans, reverse=True))))

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
L = list(map(int,input().split()))
K = [0,2,5,5,4,5,6,3,7,6]
A = sorted([[L[k],K[L[k]]] for k in range(M)])[::-1]

dp = [0 for k in range(N+1)]
for k in range(N+1):
    t = 0
    for j in range(M):
        if k-K[L[j]] >= 0:
            t = max(t,dp[k-K[L[j]]]+1)
    dp[k] = t

ans = ""
keta = dp[N]
match = N
while keta > 1:
    f = 0
    for k in range(M):
        if dp[match-A[k][1]] == keta-1 and f == 0:
            ans += str(A[k][0])
            match -= A[k][1]
            keta -= 1
            f = 1
for k in range(M):
    if match == A[k][1]:
        ans += str(A[k][0])
        break
print(ans)

Submission status: Wrong Answer

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

import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            if i < MATCH_NUM[a]:
                continue
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    res = ''
    for _ in range(max_digit_num):
        m = -1
        for a in A:
            if N < MATCH_NUM[a]:
                continue
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if a > m:
                    m = a
        res += str(m)
        N -= MATCH_NUM[m]
    print(res)
main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [i for i in range(1, 10)]
C = [2, 5, 5, 4, 5, 6, 3, 7, 6]
inf = float('inf')
costs = {m: C[m-1] for m in A}
print(costs)
dp = deque([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.sort(reverse=True)
result = deque()
num = N
for _ in range(dp[N]):
        for i in digits:
                if num >= costs[i] and dp[num-costs[i]] != -inf and dp[num-costs[i]] == dp[num]-1:
                        result.append(str(i))
                        num -= costs[i]
                        break

print(''.join(result))

Submission status: Wrong Answer

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

import sys

input = sys.stdin.readline

MATCH_NUM = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def main():
    N, M = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]

    # N 本で作れる桁の数
    dp = [-1 for _ in range(N+1)]
    dp[0] = 0
    dp[1] = 0
    for i in range(N+1):
        for a in A:
            if i < MATCH_NUM[a]:
                continue
            dp[i] = max(dp[i], dp[i-MATCH_NUM[a]] + 1)

    max_digit_num = dp[N]

    A.sort(reverse=True)

    min_cost = 10
    for a in A:
        if MATCH_NUM[a] < min_cost:
            min_cost = MATCH_NUM[a]

    res = ''
    for _ in range(max_digit_num):
        for a in A:
            if N < MATCH_NUM[a]:
                continue
            if dp[N-MATCH_NUM[a]] == dp[N]-1:
                if N-MATCH_NUM[a] < min_cost and N-MATCH_NUM[a] != 0:
                    continue
                res += str(a)
                N -= MATCH_NUM[a]
                break
    print(res)
main()

Submission status: Wrong Answer

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# MOD = 10 ** 9 + 7

import sys

sys.setrecursionlimit(10000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

D = dict()
for a in A:
    # 必要なマッチの数：1～9の数値
    D[B[a]] = max(a, D.get(B[a], -999))

# (必要なマッチの本数, 1～10の数値)
L = list(D.items())
L.sort()

# 残りn本のマッチ、現在の値val
# 戻り値：その最大値
def f(n, val):
    if n == 0:
        ret = list(str(val))
        ret.sort(reverse=True)
        print("".join(ret))
        sys.exit(0)

    if n > 0:
        for l in L:
            f(n - l[0], val * 10 + l[1])


ans = f(N, 0)

Submission status: Wrong Answer

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# MOD = 10 ** 9 + 7
#

import sys
sys.setrecursionlimit(10000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

D = dict()
# 1から9の数値:必要なマッチの本数
for a in A:
    D[a] = min(D.get(a, 999), B[a])

L = []
# (必要なマッチの本数, 1～10の数値)
for k, v in D.items():
    L.append((v, k))
L.sort()


# 残りn本のマッチ、現在の値val
# 戻り値：その最大値
def f(n, val):
    if n < 0:
        return -9999999999
    elif n == 0:
        ret = list(str(val))
        ret.sort(reverse=True)
        print("".join(ret))
        sys.exit(0)
        return 0

    ret = 0
    for l in L:
        ret = max(ret, f(n - l[0], val * 10 + l[1]))
    return ret


ans = f(N, 0)

Submission status: Wrong Answer

Solution code:
import itertools

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

len_set = set(L[x] for x in A)

INF = 10**18
can_make = [INF]*(N+1)
can_make[0] = 0 # 何桁で作れるか

for n in range(1,N+1):
  for x in len_set:
    if n-x >= 0 and can_make[n] > can_make[n-x] + 1:
        can_make[n] = can_make[n-x] + 1

answer = []

A.sort(reverse = True)
# なるべく大きいのを使いたい。作れる桁数が減らないようにする。
for a in A:
  while N-L[a] >= 0 and can_make[N] == can_make[N-L[a]]+1:
    answer.append(str(a))
    N -= L[a]
      
answer = ''.join(answer)

print(answer)

Submission status: Wrong Answer

Solution code:
import itertools

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

l_to_n = [[] for _ in range(10)]

for a in A:
  l_to_n[L[a]].append(a)
  
l_to_n = [(i,max(x)) for i,x in enumerate(l_to_n) if x]

can_make = [False]*(N+1)
can_make[0] = True

for n in range(1,N+1):
  for l,_ in l_to_n:
    if n-l >= 0 and can_make[n-l]:
      can_make[n] = True
      break

answer = []

for l,x in l_to_n:
  while N-l >= 0 and can_make[N-l]:
    N -= l
    answer.append(str(x))
  if N == 0:
    break

answer = ''.join(sorted(answer,reverse=True))

print(answer)

Submission status: Wrong Answer

Solution code:
import itertools

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

l_to_n = [[] for _ in range(10)]
for a in A:
  l_to_n[L[a]].append(a)
  
l_to_n = [(i,max(x)) for i,x in enumerate(l_to_n) if x]

se = {0} # 1000以下で作れる長さ

for l,_ in l_to_n:
  se = {x+y for x,y in itertools.product(se,range(0,1000,l)) if x+y < 1000}

answer = []
  
for l,x in l_to_n:
  while N > 500 or N-l in se:
    N -= l
    answer.append(str(x))
  if N == 0:
    break

answer = ''.join(sorted(answer,reverse=True))

print(answer)

Submission status: Wrong Answer

Solution code:
import itertools

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

l_to_n = [[] for _ in range(10)]
for a in A:
  l_to_n[L[a]].append(a)
  
l_to_n = [(i,max(x)) for i,x in enumerate(l_to_n) if x]

se = {0} # 1000以下で作れる長さ

for l,_ in l_to_n:
  se = {x+y for x,y in itertools.product(se,range(0,1000,l)) if x+y < 1000}

answer = []
m_L,x = l_to_n[0]
while N > 1000:
  N -= m_L
  answer.append(str(x))
  
for l,x in l_to_n:
  while N-l in se:
    N -= l
    answer.append(str(x))
  if N == 0:
    break

answer = ''.join(sorted(answer,reverse=True))

print(answer)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import defaultdict

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

l_to_n = [[] for _ in range(10)]
for a in A:
  l_to_n[L[a]].append(a)
  
l_to_n = [(i,max(x)) for i,x in enumerate(l_to_n) if x]

se = {0} # 1000以下で作れる長さ

for l,_ in l_to_n:
  se = {x+y for x,y in itertools.product(se,range(0,1000,l)) if x+y < 1000}

answer = ''
m_L,x = l_to_n[0]
while N > 1000:
  N -= m_L
  answer += str(x)
  
for l,x in l_to_n:
  while N-l in se:
    N -= l
    answer += str(x)
  if N == 0:
    break

answer = ''.join(sorted(answer,reverse=True))

print(answer)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import defaultdict

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
L = [100,2,5,5,4,5,6,3,7,6]

l_to_n = [[] for _ in range(10)]
for a in A:
  l_to_n[L[a]].append(a)
  
l_to_n = [(i,max(x)) for i,x in enumerate(l_to_n) if x]

se = {0} # 100以下で作れる長さ

for l,_ in l_to_n:
  se = {x+y for x,y in itertools.product(se,range(0,100,l)) if x+y < 100}

answer = ''
m_L,x = l_to_n[0]
while N > 100:
  N -= m_L
  answer += str(x)
  
for l,x in l_to_n:
  while N-l in se:
    N -= l
    answer += str(x)
  if N == 0:
    break

answer = ''.join(sorted(answer,reverse=True))

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

chosen = {}

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

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = "".join(sorted(num+dp[i]))

        elif i + cost <= n:
            if len(dp[i+cost]) < len(dp[i]) + 1:
                dp[i+cost] = "".join(sorted(num+dp[i]))

            elif len(dp[i+cost]) > len(dp[i]) + 1:
                dp[i+cost] = dp[i+cost]

            else:
                dp[i+cost] = max(dp[i+cost],
                                 "".join(sorted(num+dp[i])))

print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

chosen = {}

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

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = num + dp[i]

        elif i + cost <= n:
            if len(dp[i+cost]) < len(dp[i]) + 1:
                dp[i+cost] = num + dp[i]

            elif len(dp[i+cost]) > len(dp[i]) + 1:
                dp[i+cost] = dp[i+cost]

            else:
                dp[i+cost] = max(dp[i+cost],
                                 "".join(sorted(num+dp[i])))

print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

chosen = {}

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

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = num + dp[i]

        elif i + cost <= n:
            if len(dp[i+cost]) < len(dp[i]) + 1:
                dp[i+cost] = num + dp[i]

            elif len(dp[i+cost]) > len(dp[i]) + 1:
                dp[i+cost] = dp[i+cost]

            else:
                dp[i+cost] = max(dp[i+cost], num+dp[i])

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

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

chosen = {}

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

for ai in a:
    chosen[str(ai)] = num_cost[ai]

dp = ["ng"]*(n+1)
dp[0] = ""
for i in range(n):
    if dp[i] == "ng":
        continue

    for num, cost in chosen.items():
        if i + cost <= n and dp[i+cost] == "ng":
            dp[i+cost] = num + dp[i]

        elif i + cost <= n:
            dp[i+cost] = str(max(int(dp[i+cost]), int(num + dp[i])))

print(dp[n])

Submission status: Wrong Answer

Solution code:
N, M = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
n_m = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
m_n = {}
for a in A:
    m_n[n_m[a]] = a
ms = sorted(m_n.keys())
length = len(ms)
stack = [[0] * (length + 1)]
dp = [[]] * (N + 1)
while stack:
    b = stack.pop()
    if b[0] <= N and not dp[b[0]]:
        dp[b[0]] = b[1:]
        if b[0] == N:
            break
        for i in range(length - 1, -1, -1):
            c = b.copy()
            c[0] += ms[i]
            c[i + 1] += 1
            stack += [c]
ans = ''
for m, num in sorted(list(zip(ms, b[1:])), key=lambda _: -m_n[_[0]]):
    ans += str(m_n[m]) * num
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools, collections, heapq
N, M = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
n_m = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
m_n = {}
for a in A:
    m_n[n_m[a]] = a
ms = sorted(m_n.keys())
length = len(ms)
stack = [[0] * (length + 1)]
dp = collections.defaultdict(int)
while stack:
    b = stack.pop()
    if b[0] == N:
        break
    if not dp[b[0]] and b[0] < N:
        dp[b[0]] = b[1:]
        for i in range(length - 1, -1, -1):
            c = b.copy()
            c[0] += ms[i]
            c[i + 1] += 1
            stack += [c]
ans = ''
for m, num in sorted(list(zip(ms, b[1:])), key=lambda _: -m_n[_[0]]):
    ans += str(m_n[m]) * num
print(ans)

Submission status: Wrong Answer

Solution code:
## DP問題
 
N,M = map(int,input().split())
As = list(map(str,input().split()))
match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}
 
# test
# N, M = 10000, 9
# As = [str(i) for i in range(1,10)]
 
 
ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())
 
dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"
 
for i in range(N+1):
    # print(i)
    for a,k in zip(ns,ks):
        if i+k <= N:
            if dp[i] == "-1":
                dp[i+k] = str(max(int(dp[i]+a),int(dp[i+k])))
            elif dp[i] == "0":
                dp[i+k] = str(max(int(a),int(dp[i+k])))
            elif len(dp[i+k]) < len(dp[i])+1:
                    dp[i+k] = dp[i]+a
            else:
                dp[i+k] = max(dp[i+k],dp[i]+a)
        else:
            continue
print(dp[N])

Submission status: Wrong Answer

Solution code:
## 

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

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


ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())

dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"

for i in range(0,N+1):
    for a,k in zip(ns,ks):
        if i+k <= N:
            dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))
        else:
            continue
        if i+k == N:
            break   
print(dp[N])

Submission status: Wrong Answer

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

res0 = []


def dfs(idx, consume, _n):
    # 最後の数
    if idx == len(require_match) - 1:
        if _n % require_match[idx] != 0:
            return
        consume[idx] = _n // require_match[idx]
        res0.append(consume)
        return

    for i in range((_n // require_match[idx])+1):
        _consume = consume[::]
        _consume[idx] = i
        __n = _n - require_match[idx] * i
        dfs(idx+1, _consume, __n)


dfs(0, [0 for i in range(m)], n)

max_cnt = 0
res1 = []
for res in res0:
    if sum(res) > max_cnt:
        max_cnt = sum(res)
        res1 = [res]
    elif sum(res) == max_cnt:
        res1.append(res)

max_num = 0
res2 = []
for res in res1:
    num = sum([a[i]*res[i] for i in range(len(res))])
    if max_num < num:
        max_num = num
        res2 = res


res3 = [[a[i], res2[i]] for i in range(len(res2))]
res3.sort(key=lambda x: x[0], reverse=True)
ans = ""
for i in res3:
    ans += (str(i[0])*i[1])
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]"):
    cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    D = {cost[i-1]: i for i in A}
    cost = sorted(D.keys())
    dp = [-1] * (N+1)
    dp[0] = 0
    for i in range(N+1):
        if dp[i] == -1:
            continue
        for c, d in D.items():
            if i + c <= N:
                dp[i+c] = max(dp[i+c], dp[i] * 10 + d)
    print(dp[N])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()