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

Solution (Python):


import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]

  if len(digits) == 0:
    return False

  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

      replaces = [digits[i][0] for i in idxs]
      uppers = [d for d in replaces if d > base_digit]
      lowers = [d for d in replaces if d < base_digit]

      num = number[:]

      if len(uppers) > 0:
        num = uppers + num[len(uppers):]

      if len(lowers) > 0:
        num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()

Solution (Python):
import collections 

MINUSINF = '-'

def chmax(a, b):
    if a == MINUSINF:
        return b
    elif len(a) < len(b):
        return b
    elif len(a) == len(b):
        return a if a > b else b
    else:
        return b
        
n, m = [int(s) for s in input().split()]
alist = [int(s) for s in input().split()]

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

dp = [MINUSINF for i in range(11000)]
dp[0] = ''

for i in range(n+1):
    if dp[i] == MINUSINF:
        continue
    for j, a in enumerate(alist):
        dp[i + match[a-1]] = chmax(dp[i + match[a-1]], dp[i] + str(a))

print(dp[n])

Solution (Python):
match = {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 = sorted(list(map(int, input().split())), reverse=True)

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

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

print(ans)

Solution (Python):
N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)


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


dp = [-1] * (N + 1)
dp[0] = 0

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

digit = dp[N]
ans = ''

n = N
for d in range(digit):
    for a in A:
        if n - h[a] < 0:continue
        if dp[n - h[a]] == digit - 1:
            ans += str(a)
            n -= h[a]
            digit -= 1
            break
print(ans)

Solution (Python):
def main():
  N, M = map(int, input().split())
  alist = list(map(int, input().split()))
  alist.sort(reverse=True)
  nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

  dp = [-1 for _ in range(N + 1)]
  dp[0] = 0
  for a in alist:
    n = nums[a]
    for i in range(N - n + 1):
      if dp[i] == -1:
        continue
      dp[i + n] = max(dp[i + n], dp[i] * 10 + a)

  print(dp[-1])
      

if __name__ == '__main__':
  main()

Solution (Python):
mi = {"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 = input().split()
dpn = [0] + [-1] * 10010
dp = [""] * 10010
for i in range(n):
    for a in A:
        if dpn[i] != -1:
            cnt = dpn[i] + 1
            if dpn[i + mi[a]] < cnt:
                dpn[i + mi[a]] = cnt
                dp[i + mi[a]] = max(a + dp[i], dp[i] + a)
            elif dpn[i + mi[a]] == cnt:
                dp[i + mi[a]] = max(dp[i + mi[a]], a + dp[i], dp[i] + a)
print(dp[n])

Solution (Python):
def printing(a_start, a_2, n):

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)


    if len(a_3) >= 2:
        if a_start[0] + a_3[-1][0] < n and a_3[0][0] < a_3[1][0] and a_3[1][0] > a_start[0]:
            a_3.pop(0)


    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
            elif n % a_start[1] == 0:
                break
        else:
            n -= a_3[0][1]
            ans += str(a_3[0][0])

    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Solution (Python):
N, M = map(int, input().split())
A = [i for i in input().split()]



def mx(a, b):
    if a is not None and b is None:
        return a
    elif a is None and b is not None:
        return b
    if len(a) != len(b):
        if len(a) > len(b):
            return a
        else:
            return b
    return max(a, b)


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

dp = [None] * (N + 1)
dp[0] = ''

for i in range(N + 1):
    for a in A:
        if i - h[a] < 0: continue
        if dp[i-h[a]] is None and dp[i] is None:
            continue
        try:
            dp[i] = mx(dp[i-h[a]] + a, dp[i])
        except:
            continue

print(dp[N])

Solution (Python):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
dp = [0]
cost = [0,2,5,5,4,5,6,3,7,6]
for i in range(1, N+1):
    dp.append(-(2<<10))
    for a in A:
        if i >= cost[a]: 
            dp[i] = max(dp[i - cost[a]] + 1, dp[i])
ans = ""
while N > 0:
    for e in A:
        if N >= cost[e] and dp[N] - 1 == dp[N - cost[e]]:
            if dp[N] == 1:
                if N != cost[e]: continue
            N -= cost[e]
            ans += str(e)
            break
print(ans)

Solution (Python):
def f(x):
    k = int(x)
    return c[k], k

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

N, M = list(map(int, input().split()))
A = list(map(f, input().split()))
A = sorted(A, key=lambda x: x[0] * 10 - x[1])

b = []
dic = {}
n = 0
for d in A:
    if n != d[0]:
        b.append(d[0])
        n = d[0]
        dic[n] = d[1]

ans = [0] * b[0]
n = b[0]
count = 0
while True:
    max_ = 0
    for d in b:
        if n - d == 0:
            if dic[d] > max_:
                max_ = dic[d]
        elif n - d > 0 and ans[n - d] > 0:
            t = ans[n - d] * 10 + dic[d]
            max_ = max(max_, t)

    if n == N:
        print(max_)
        break;
    if max_ > 0 and (N - n) % b[0] == 0:
        if count < 2:
            count += 1
        else:
            print(''.join(sorted(list(str(max_) + str(dic[b[0]])*((N - n)//b[0])), reverse=True)))
            break
    ans.append(max_)
    n += 1

Solution (Python):
N, M = map(int, input().split())
A = [int(i) for i in input().split()]




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

dp = [-1] * (N + 1)
dp[0] = 0

for i in range(N + 1):
    for a in A:
        if i - h[a] < 0: continue
        dp[i] = max(10*dp[i-h[a]] + a, dp[i])

print(dp[N])

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


def num(a):  
    return [2, 5, 5, 4, 5, 6, 3, 7, 6][a - 1]


dp = [0] * (N + 1)  
for i in range(1, N + 1):
    match_match = [dp[i - num(a)] + 1 for a in A if i - num(a) >= 0]
    if match_match:
        dp[i] = max(match_match)
    else:
        dp[i] = -1000

remind = 0  
ans = ''  
for i in range(dp[N]):
    for a in A:
        if N - num(a) - remind >= 0:
            if dp[N - num(a) - remind] == dp[N] - 1 - i:
                remind += num(a)
                ans += str(a)
                break
print(ans)

Solution (Python):
def f(x):
    k = int(x)
    return c[k], k


c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = list(map(f, input().split()))
A = sorted(A, key=lambda x: x[0] * 10 - x[1])


b = []
dic = {}
n = 0
for d in A:
    if n != d[0]:
        b.append(d[0])
        n = d[0]
        dic[n] = d[1]

ans = [0] * b[0]
n = b[0]
while True:
    max_ = 0
    for d in b:
        if n - d == 0:
            if dic[d] > max_:
                max_ = dic[d]
        elif n - d > 0 and ans[n - d] > 0:
            t = ans[n - d] * 10 + dic[d]
            max_ = max(max_, t)

    if n == N:
        print(max_)
        break
    ans.append(max_)
    n += 1

Solution (Python):
nums = [2,5,5,4,5,6,3,7,6]

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

digits = list(map(int,input().split()))

dp = [-1]*(n+10)
dp[0] = 0
for i in range(n+1):
   if(dp[i] == -1):
       continue
   else:
       for digit in digits:
           dp[i+nums[digit-1]] = max(dp[i+nums[digit-1]], dp[i]*10+digit)
           

print(dp[n])

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

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

for i in range(1,n+1):
  for j in a:
    honsu = match[j-1]
    if i-honsu>=0:
      dp[i] = max(dp[i-honsu]*10+j,dp[i])
print(dp[n])

Solution (Python):
def printing(a_start, a_2, n):

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)


    if len(a_3) >= 2:
        if a_start[0] + a_3[-1][0] < n and a_3[0][0] < a_3[1][0] and a_3[1][0] > a_start[0]:
            a_3.pop(0)


    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
            elif n % a_start[1] == 0:
                break
        else:
            n -= a_3[0][1]
            ans += str(a_3[0][0])

    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Solution (Python):
import sys

sys.setrecursionlimit(10000)

from collections import Counter
 
def parse_line(line, type=int):
    return [type(x) for x in line.split(' ')]
 
 

weight = ['x', 2, 5, 5, 4, 5, 6, 3, 7, 6]
 

def run(k, weight_to_num, cache):
    if k not in cache:
        if k <= 1:
            res = 0
        else:
            res = 0
            for w, num in weight_to_num.items():
                res = max(res, run(k - w, weight_to_num, cache))
            if res > 0:
                res += 1
            if k in weight_to_num:
                res = max(1, res)
        cache[k] = res
    return cache[k]
 
 
def main():
    n, m = parse_line(input())
    numbers = set(parse_line(input()))
    
 
    
 
    if 6 in numbers and 9 in numbers:
        numbers.remove(6)
    if 2 in numbers and 3 in numbers:
        numbers.remove(2)
    if 2 in numbers and 5 in numbers:
        numbers.remove(2)
    if 3 in numbers and 5 in numbers:
        numbers.remove(3)
 
    weight_to_num = {weight[v]: v for v in numbers}
    cache = {}
    run(n, weight_to_num, cache)
    
    
 
    ws = list(weight_to_num.keys())
    ws.sort(reverse=True, key=lambda w: weight_to_num[w])
    res = []
    cache = {k:v for k,v in cache.items() if v > 0}
    cache[0] = 0
 
    if n not in cache:
        return
 
    l = cache[n]
    while l:
        for w in ws:
            if cache.get(n - w, 'False') == l - 1:
                res.append(weight_to_num[w])
                n = n - w
                l -= 1
                break
    print(''.join((str(x) for x in res)))
 
 
if __name__ == '__main__':
    main()

Solution (Python):
def get_int(): return int(input())
def get_float(): return float(input())
def get_line(): return input().split()
def get_lines(v): return [get_line() for _ in range(v)]
def get_int_line(): return list(map(int, get_line()))
def get_int_lines(v): return [get_int_line() for _ in range(v)]
def get_float_line(): return list(map(float, get_line()))
def get_float_lines(v): return [get_float_line() for _ in range(v)]

cost = [0,2,5,5,4,5,6,3,7,6]
N, M = get_int_line()
A = get_int_line()

dp = [-1 for _ in range(N + 1)]
dp[0] = 0
for i in range(N):
  if (dp[i] == -1): continue
  for v in A:
    if (i + cost[v] <= N and dp[i + cost[v]] < dp[i] * 10 + v):
      dp[i + cost[v]] = dp[i] * 10 + v

print(dp[N])

Solution (Python):
match = [2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
aa=list(map(int,input().split()))
dp=[-1]*(n+10)

dp[0]=0
for i in range(n+1):
        for nums in aa:
                if dp[i] == -1 :continue
                dp[i+match[nums-1]] = max(dp[i]*10+nums,dp[i+match[nums-1]])

print(dp[n])

Solution (Python):






def main():
    N,M = map(int, input().split())
    A = list(map(int, input().split()))
    
    match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    
    result = [-1 for _ in range(N+1)]
    result[0] = 0
    
    
    
    for i in range(1, N+1):
        for a in A:
            if i < match[a]:
                
                continue
            result[i] = max(result[i], result[i-match[a]]*10+a)
            
    
    print(result[N])





main()

Solution (Python):
n, m = map(int, input().split())
a = [int(a) for a in input().split()]    
required_matches = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

dp = [0] + [-1] * n
for used_matches in range(1, n+1):
    usable_digits = [ai for ai in a if used_matches - required_matches[ai] >= 0]
    if usable_digits != []:
        dp[used_matches] = max([dp[used_matches-required_matches[ai]]*10 + ai
            for ai in usable_digits])
print(dp[n])

Solution (Python):
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
while(N>0):
    for i in src[::-1]:
        if N - arr[i] >= 0 and dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
print(ans if ans else 0)

Solution (Python):
def chmax(x, y):
    if x == '-':
        return y

    lx = len(x)
    ly = len(y)
    if lx < ly:
        return y
    elif lx == ly:
        if x < y: return y
        else: return x
    else:
        return x


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

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


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

print(dp[N])

Solution (Python):


import sys
from functools import lru_cache

sys.setrecursionlimit(10000)

input = sys.stdin.readline

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

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

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

def num(n):
    return B[n-1]

@lru_cache(maxsize=None)
def dp(i):
    if i == 0:
        return 0
    elif i < 0:
        return -float('inf')
    else:
        C = []
        for j in range(M):
            C.append(dp(i-num(A[j]))+1)
        return max(C)

s = ''
n = dp(N)
K = N

for i in range(n):
    for j in range(M):
        if dp(K-num(A[j])) == dp(K)-1:
            s += str(A[j])
            K -= B[A[j]-1]
            break

print(int(s))

Solution (Python):



def main():
    N, M = map(int, input().split())

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

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

    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for i in range(1, N + 1):
        for a in A:
            if i < costs[a]:
                continue
            dp[i] = max(dp[i], dp[i - costs[a]] * 10 + a)
    print(dp[N])


main()

Solution (Python):
c=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int, input().split())
A=list(map(int, input().split()))
INF=100010
dp = [-INF for _ in range(N+1)]
dp[0]=0

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

print(dp[N])

Solution (Python):
costs = [2, 5, 5, 4, 5, 6, 3, 7, 6]


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for i in range(1, N + 1):
        for a in A:
            if i < costs[a - 1]:
                continue
            dp[i] = max(dp[i], dp[i - costs[a - 1]] * 10 + a)
    print(dp[N])


main()

Solution (Python):
import sys

def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  A = list(map(int, input().split()))
  d = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
  
  dp = [0 for _ in range(N+1)]
  for i in range(1, N+1):
    dpi = - float('inf')
    for a in A:
      if d[a] <= i:
        dpi = max(dpi, dp[i - d[a]] + 1)
    dp[i] = dpi

  ans = [0 for _ in range(dp[N])]
  for i in range(len(ans)):
    num = 0
    for a in A:
      if (d[a] <= N) and (dp[N - d[a]] == dp[N] - 1):
        num = max(num, a)
    ans[i] = str(num)
    N -= d[num]

  print(''.join(ans))


if __name__ == '__main__':
  main()

Solution (Python):

from sys import stdin
import numpy as np
from itertools import product

s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


COST = np.array([2, 5, 5, 4, 5, 6, 3, 7, 6])

N, M = ds_in()
A_list = np.array(ds_in())
A_cost = COST[A_list - 1]  

min_cost = min(A_cost)
base_num = max(A_list[A_cost == min_cost])

if N % min_cost == 0:
    print(int(str(base_num) * (N//min_cost)))
    exit()


mod_cost = {i: [-1, 10**6] for i in range(1, min_cost)}
for a, c in zip(A_list, A_cost):
    mod = c % min_cost
    if mod > 0:
        if c < mod_cost[mod][1]:
            mod_cost[mod][1] = c
            mod_cost[mod][0] = a
        elif c == mod_cost[mod][1]:
            mod_cost[mod][0] = max(a, mod_cost[mod][0])


for i in range(1, min_cost):
    if mod_cost[i][1] > 10:
        del mod_cost[i]

N_mod = N % min_cost
upper = []
for m in mod_cost.keys():
    upper.append([i for i in range(0, min_cost + 1)])


ans = []
for cand in product(*upper):
    if N_mod == sum(map(lambda x, y: x*y, mod_cost.keys(), cand)) % min_cost:
        temp_N = N
        num_list = []
        for x, y in zip(mod_cost.keys(), cand):
            num_list.extend([mod_cost[x][0]] * y)
            temp_N -= mod_cost[x][1] * y
        if temp_N >= 0:
            num_list.extend([base_num] * (temp_N // min_cost))
            num_list.sort()
            ans.append(int(''.join(map(str, num_list[::-1]))))

print(max(ans))

Solution (Python):
match_num=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int, input().split())
nums=sorted(list(map(int, input().split())),reverse=True)
INF=1000000

dp = [-INF for _ in range(N+1)]
dp[0]=0
usables=[]
for n in nums:
  usables.append(match_num[n])

for i in range(min(usables), N+1):
  tmp=[]
  for u in usables:
    if (i-u)>=0:
      tmp.append(dp[i-u])
  
  dp[i]=max(tmp)+1

remained_maches=N

ans=''  
for i in range(dp[N]):
  for j in range(M):
    if (remained_maches-usables[j])>=0:
      if dp[remained_maches]-1==dp[remained_maches-usables[j]]:
        ans+=str(nums[j])
        remained_maches-=usables[j]
        break
        
print(ans)

Solution (Python):


import math
import sys
from operator import itemgetter
input = sys.stdin.readline











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

def chmax(a, b):
	if a is None:
		return b
	elif len(a) < len(b):
		return b
	elif len(a) > len(b):
		return a
	else:
		return max(a, b)

dict = {}
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [None] * (N+1)

for i in Ar:
	if num[i] in dict:
		dict[num[i]] = max(i, dict[num[i]])
	else:
		dict[num[i]] = i


dp[0] = ""
for i in range(1, N+1):
	for j in dict:
		if (i >= j) and (dp[i-j] is not None):
			dp[i] = chmax(dp[i], dp[i-j] + str(dict[j]))

print(dp[N])

Solution (Python):


import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]

  if len(digits) == 0:
    return False

  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

      replaces = [digits[i][0] for i in idxs]
      uppers = [d for d in replaces if d > base_digit]
      lowers = [d for d in replaces if d < base_digit]

      num = number[:]

      if len(uppers) > 0:
        num = uppers + num[len(uppers):]

      if len(lowers) > 0:
        num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()

Solution (Python):
import numpy as np

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

match = [-1]*(N+1)
match[0] = 0
for i in range(1,N+1):
  for a in A:
    if i < costs[a]:
      continue
    else:
      match[i] = max(match[i],match[i-costs[a]]*10+a)

print(match[N])

Solution (Python):
d = {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()
d_ = {}
for i in range(M):
    d_[d[A[i]]] = A[i]
diff = [(d_[key],key) for key in d_]
diff.sort()

DP = ['']*(10**4+1)
for a,l in diff:
    DP[l] = str(a)
    
for i in range(N+1):
    for a,l in diff:
        if i-l >= 0:
            if len(DP[i-l])+1>=len(DP[i]) and DP[i-l]!='':
                    DP[i] = str(a)+DP[i-l]

ans = list(DP[N])
ans.sort()
ans.reverse()
ans = ''.join(ans)
print(ans)

Solution (Python):
"""
Match Matching
提出 
"""


def solve():
	
	num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
	N, M = map(int, input().split())
	A = [int(i) for i in input().split()]
	A.sort(reverse=True)
	
	
	dp = [-1 * float("inf")] * (N + 1)

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

	
	ans = ''
	for i in range(dp[N]):  
		for a in A:
			
			
			
			
			
			
			
			
			if N - num[a] > -1 and dp[N] - 1 == dp[N - num[a]]:
				ans += str(a)
				N -= num[a]
				break
		

	print(ans)


if __name__ == '__main__':
	solve()

Solution (Python):
"""
Match Matching
提出 
"""


def solve():
    
    num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    
    
    dp = [-1 * float("inf")] * (N + 1)

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

    
    ans = ''
    for i in range(dp[N]):  
        for a in A:
            
            
            
            
            
            
            
            
            if N - num[a] > -1 and dp[N] - 1 == dp[N - num[a]]:
                ans += str(a)
                N -= num[a]
                break
        

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>1:
        arr = [ a for a in A if  n-costs[a-1]>=0 and D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        else:
            break
    print(ans)

main()

Solution (Python):
N, M= map(int, input().split())
a_list = sorted(map(int, input().split()), reverse = True)


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

inf = 10 ** 5
dp = [-inf] * (N + 1)
dp[0] = 0


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


ans = [""] * dp[N]
rest_match = N
for i in range(dp[N]):
    for a in a_list:
        index = rest_match - match_num[a]
        if index >= 0 and dp[index] == dp[N] - i - 1:
            rest_match -= match_num[a]
            ans[i] = str(a)
            break
print("".join(ans))

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
inf = float("inf")
dp = [-inf] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    for j in a:
        cost_j = int("0255456376"[j])
        if i- cost_j >= 0:
            dp[i] = max(dp[i], j+dp[i-cost_j]*10)

ans = dp[n]
if ans == -inf:
    ans = 0
print(ans)

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
inf = float("inf")
dp = [-inf] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    for j in a:
        cost_j = int("0255456376"[j])
        if i- cost_j >= 0:
            dp[i] = max(dp[i], j+dp[i-cost_j]*10)
print(dp[n])

Solution (Python):

N,M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
f = [-1, 2,5,5,4,5,6,3,7,6] 


dp = [-float('inf')]*(N+1)
dp[0] = 0
for i in range(N+1):
    nxt = dp[i]
    for aj in A:
        if i-f[aj]<0: continue
        nxt = max(nxt, 
                  dp[i-f[aj]] + 1)
    dp[i] = nxt
    

keta = dp[N]
ans = ""
matchs = N

while keta>0:
    for aj in A:
        if matchs-f[aj] < 0: continue
        if dp[matchs-f[aj]] == keta-1:
            ans += str(aj)
            matchs -= f[aj]
            keta -= 1
            break
print(ans)

Solution (Python):





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

A.sort(reverse=True)  


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




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


dp[0] = 0
for a in A:
    if num[a] <= N:  
        dp[num[a]] = 1


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



ans = ""
for i in range(dp[N]):  
    for a in A:  
        
        if N - num[a] > -1 and dp[N - num[a]] == dp[N] - 1:
            ans += str(a)
            N -= num[a]  
            break

print(ans)

Solution (Python):
n, m = map(int, input().split())
a = list(map(int, input().split()))
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]  
f = [0] + [-1] * 10000  


for i in range(n):
    
    i += 1
    for x in a:
        
        

        o = c[x]  

        if i - o >= 0:  
            
            f[i] = max(f[i], f[i - o] * 10 + x)

print(f[n])

Solution (Python):

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


dp = [None]*(N+1)
dp[0] = ""


def max_str(s1:str, s2:str)->str:
    """return bigger one"""
    l1, l2 = len(s1), len(s2)
    if l1 != l2:
        return s1 if l1>l2 else s2
    if l1 == l2: 
        return s1 if s1>s2 else s2
    
for i in range(2, N+1):
    nxt = ""
    for aj in A:
        
        if i-f[aj]<0 or dp[i-f[aj]]==None: continue
        nxt = max_str(nxt, 
                      dp[i-f[aj]]+str(aj))
    if nxt!="":
        dp[i] = nxt
    
print(dp[N])