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: Runtime Error

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort()
A.reverse()

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

A_num = [(num[a], -a) for a in A]
A_num.sort()

min_A = -A_num[0][1]
min_num = A_num[0][0]
keta_max = N//min_num

def solve(d, amari):
    if amari < 0:
        return None
    elif amari == 0:
        if d == 0:
            return ""
        else:
            return None
    if amari < d*min_num:
        return None
    elif amari == d*min_num:
        return str(min_A) * d
    for a in A:
        temp = solve(d-1, amari-num[a])
        if temp != None:
            return str(a) + temp
    return None
    

for keta in range(keta_max, 0, -1):
    ans = solve(keta, N)
    if ans:
        break
print(ans)

Submission status: Runtime Error

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

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

memo = [ "-" for _ in range(N + 1)]

def find(N):
    global memo
    if memo[N] != "-":
        return memo[N]

    mval = ""
    val = ""
    for a in A:
        if d[a - 1] < N:
            val = str(find(N - d[a - 1]))
            if val == "":
                continue
            val = val + str(a)
        elif d[a - 1] == N:
            val = str(a)
        else:
            continue

        if len(mval) < len(val) or mval < val:
            mval = val
    memo[N] = mval
    return memo[N]

m = find(N)
print(m)

Submission status: Runtime Error

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

setnum = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6} 
rset = {}
for i in a:
    if i in rset:
        if rset[setnum[i]] > i:
            rset[i] = setnum[i]
    else:
        rset[i] = setnum[i]

rset = sorted(rset.items(), reverse=True)
dp = [0] * (n + 1)
for i in rset:
    dp[i[1]] = i[0]
    for j in range(1, n + 1 - i[1]):
        if dp[j] != 0:
            dp[j + i[1]] = max(dp[j + i[1]], dp[j] * 10 + i[0])
print(dp[-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
n=[0,2,5,5,4,5,6,3,7,6]
num=[0]*8
for a in A:
    num[n[a]]=max(num[n[a]],a)
nums=[]
for i in range(8):
    if num[i]: nums.append((i,num[i]))

dp=[0]*(N+1)
for x,y in nums:
    dp[x]=y
for i in range(nums[0][0]+1,N+1):
    t=dp[i]
    for x,y in nums:
        if i-x>0:
            if dp[i-x]:
                dp[i]=max([dp[i],int(str(y)+str(dp[i-x])),dp[i-x]*10+y])
print(dp[N])

Submission status: Runtime Error

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

for a in a_list:
    need = items[a]
    dp[need] = a

for i in range(2, N+1):
    for j in range(M):
        if i - items[a_list[j]] >= 0:
                if dp[i - items[a_list[j]]] != 0:
                    dp[i] = max(dp[i - items[a_list[j]]] * 10 + a_list[j], dp[i])

print(dp[N])

Submission status: Runtime Error

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

for a in a_list:
    need = items[a]
    dp[need] = a

for i in range(2, N+1):
    for j in range(M):
        if i - items[a_list[j]] + 1 >= 0:
                if dp[i - items[a_list[j]]] != 0:
                    dp[i] = max(dp[i - items[a_list[j]]] * 10 + a_list[j], dp[i])

print(dp[N])

Submission status: Runtime Error

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

n,m = map(int,input().split()) # n <= 10**4
A = list(map(int,input().split()))
usable_num = sorted([[i,L[i-1]] for i in A], key=lambda x:(x[1],-x[0]))
usable_num = [usable_num[i] for i in range(m) if i == 0 or usable_num[i-1][1] != usable_num[i][1]]
ans = ""
t = 0
i = 0
while n != 0:
    if n - usable_num[0][1] < 0:
        if len(ans) <= i:
            i = len(ans) - 1
        n += L[int(ans[i])-1]
        usable_num.pop(0)
        ans = ans[:i] + ans[i+1:]
        i += 1
    n -= usable_num[0][1]
    ans = str(usable_num[0][0]) + ans
print(''.join(sorted(ans,reverse=True)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
numbers = set(map(int, input().split()))
costs = [2,5,5,4,5,6,3,7,6] # <- 1,2,3,4,5,6,7,8,9
costmap = {}
for num in numbers:
  cost = costs[num-1]
  if cost in costmap and num < costmap[cost]:
    continue
  costmap[cost] = num

from functools import lru_cache
@lru_cache(None)
def recursive(remain=N):
  maxval = costmap[remain] if remain in costmap else 0
  for cost, num in costmap.items():
    if remain > cost:
      val = recursive(remain-cost)
      if val is None:
        continue
      val = val * 10 + num
      if val > maxval:
        maxval = val
  if maxval == 0:
    return None
  return maxval

print(recursive(N))

Submission status: Runtime Error

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

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

memo = [ "-" for _ in range(N + 1)]

def find(N):
    global memo
    if memo[N] != "-":
        return memo[N]

    mval = ""
    val = ""
    for a in A:
        if d[a - 1] < N:
            val = str(find(N - d[a - 1]))
            if val == "":
                continue
            val = val + str(a)
        elif d[a - 1] == N:
            val = str(a)

        if len(mval) < len(val) or mval < val:
            mval = val
    memo[N] = mval
    return memo[N]

m = find(N)
print(m)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
numbers = set(map(int, input().split()))
costs = [2,5,5,4,5,6,3,7,6] # <- 1,2,3,4,5,6,7,8,9
costmap = {}
for num in numbers:
  cost = costs[num-1]
  if cost in costmap and num < costmap[cost]:
    continue
  costmap[cost] = num

def recursive(remain=N):
  maxval = costmap[remain] if remain in costmap else 0
  for cost, num in costmap.items():
    if remain > cost:
      val = recursive(remain-cost)
      if val is None:
        continue
      val = val * 10 + num
      if val > maxval:
        maxval = val
  if maxval == 0:
    return None
  return maxval

print(recursive(N))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
n=[0,2,5,5,4,5,6,3,7,6]
num=[0]*8
B=[(a,n[a]) for a in A]
for x,y in B:
    num[y]=max(num[y],x)
nums=[]
for i in range(8):
    if num[i]: nums.append((i,num[i]))

dp=[0]*(N+1)
for x,y in nums:
    dp[x]=y
for i in range(nums[0][0]+1,N+1):
    t=dp[i]
    for x,y in nums:
        if i-x>0:
            if dp[i-x]:
                dp[i]=max([dp[i],int(str(y)+str(dp[i-x])),dp[i-x]*10+y])
print(dp[N])

Submission status: Runtime Error

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

n,m = map(int,input().split()) # n <= 10**4
A = list(map(int,input().split()))
usable_num = sorted([[i,L[i-1]] for i in A], key=lambda x:(x[1],-x[0]))
usable_num = [usable_num[i] for i in range(m) if i == 0 or usable_num[i-1][1] != usable_num[i][1]]
ans = ""
t = 0
i = 0
while n != 0:
    if n - usable_num[0][1] < 0:
        n += L[int(ans[i])-1]
        usable_num.pop(0)
        ans = ans[:i] + ans[i+1:]
        i += 1
    n -= usable_num[0][1]
    ans = str(usable_num[0][0]) + ans
print(''.join(sorted(ans,reverse=True)))

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
import bisect
import random
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return list(input())
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
a,b = LI()
if b % a == 0:
    print(a+b)
else:
    print(b-a)
"""

#B
"""
n,m = LI()
lis = [0 for i in range(m)]
for i in range(n):
    k = LI()
    for j in k[1:]:
        lis[j-1] += 1
ans = 0
for i in lis:
    if i == n:ans += 1
print(ans)
"""

#C
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = II()
a = LI()
ans = a[0]
for i in range(1,n):
    ans = gcd(ans,a[i])
print(ans)
"""

#D
n,m = LI()
a = LI()
f = [0,2,5,5,4,5,6,3,7,6]
for i in range(m):
    a[i] = [a[i],f[a[i]]]
a.sort(key = lambda x:x[1])
dp = [[] for i in range(n+1)]
for i in a:
    dp[i[1]] = [i[0]]
for i in range(n+1):
    for j in a:
        if i-j[1] >= 0 and len(dp[i-j[1]]) > 0:
            if len(dp[i]) < len(dp[i-j[1]])+1:
                dp[i] = dp[i-j[1]]+[j[0]]
                dp[i].sort()
                dp[i] = dp[i][::-1]
            else:
                if len(dp[i]) == len(dp[i-j[1]])+1:
                    d = sorted(dp[i-j[1]]+[j[0]])
                    d = d[::-1]
                    k = [dp[i],d]
                    k.sort()
                    if k[1] == d:
                        dp[i] = d
ans = 0
k = 1
l = len(dp[-1])
for i in range(l):
    ans += k*dp[-1][l-i-1]
    k *= 10
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def main():
    # N=int(input())
    N,M = list(map(int,input().split()))
    a = list(map(int,input().split()))
    c = [2,5,5,4,5,6,3,7,6]
    dp = [-1e7 for _ in range(N+1)]
    dp[0] = 0
    for i in range(1,N+1):
        for j in a:
            dp[i] = max(dp[i],dp[i-c[j-1]]+1)
    ans = ""
    now = N
    for _ in range(dp[N]):
        ag = -1
        ma = -1
        for j in a:
            if now - c[j-1] < 0:
                continue
            if dp[now]!=dp[now-c[j-1]]+1:
                continue
            if j > ma:
                ma = j
        now -= c[ma-1]
        ans += str(ma)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

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

def match(i):
    ANS=0
    for s in str(i):
        ANS+=M[int(s)]

    return ANS
        

def dfs(i,NOW):
    if NOW==N:
        L=sorted(list(i),reverse=True)
        
        print("".join(L))
        sys.exit()
    elif NOW>N:
        return
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
#print(A)
A.sort(key=lambda x:M[x])
#print(A)

dfs("",0)

Submission status: Runtime Error

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

import functools

DIGIT = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

memo = {}

def dp(count):
    if count not in memo:
        answer = -1
        for a in A:
            if count > DIGIT[a]:
                rest = dp(count - DIGIT[a])
                if rest >= 0:
                    s = str(rest)
                    answer = max(answer, rest * 10 + a if int(s[0]) > a else int(str(a) + s))
            elif count == DIGIT[a]:
                answer = max(answer, a)
        memo[count] = answer

    return memo[count]

print(dp(n))

Submission status: Runtime Error

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

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

T = [(-10**8,0)]*(N+1)
T[0] = (0, 0)
for i in range(1, N+1):
  for a in A:
    if C[a]>=0:
      T[i] = max(T[i], (T[i-C[a]][0]+1, a))

ans = ""
p = N
while p>0:
  ans += str(T[p][1])
  p -= C[T[p][1]]
print ans

Submission status: Runtime Error

Solution code:
N,M = map(int, raw_input().split())
A = sorted(map(int, raw_input().split()))

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

T = [(-10**8,0)]*(N+1)
T[0] = (0, 0)
for i in range(1, N+1):
  for a in A:
    if C[a]>=0 and T[i-C[a]][0]+1 >= T[i][0]:
      T[i] = (T[i-C[a]][0]+1, a)

ans = ""
p = N
while p>0:
  ans += str(T[p][1])
  p -= C[T[p][1]]
print ans