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):
from pprint import pprint
def arr_scan():
    return list(map(int, input().split(' ')))

n, m = arr_scan()



dp = ['' for _ in range(n + 1)]
costs = [0,2,5,5,4,5,6,3,7,6]





letters = arr_scan()


for wt in range(1, n + 1):
    
    for l in letters:
        
        if wt - costs[l] >= 1 and dp[wt - costs[l]] != '':
            if len(dp[wt - costs[l]]) + 1 > len(dp[wt]):
                dp[wt] = max(dp[wt - costs[l]] + str(l), str(l) + dp[wt - costs[l]])
            elif len(dp[wt- costs[l]]) + 1 == len(dp[wt]): 
                dp[wt] = max(dp[wt], dp[wt - costs[l]] + str(l), str(l) + dp[wt - costs[l]])
        elif wt == costs[l]:
            if len(dp[wt]) == 1:
                dp[wt] = max(dp[wt], str(l))
            elif dp[wt] == '':
                dp[wt] = str(l)
        

print(dp[n])

Solution (Python):
n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1] * (n + 8)
dp[0] = 0
for a in sorted(map(int, input().split()), reverse=True):
    na = needs[a]
    for i in range(n + 1):
        if dp[i] == -1:
            continue
        dp[i + na] = max(dp[i + na], dp[i] * 10 + a)
print(dp[n])

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = defaultdict(lambda: 0)
for a in map(int, input().split()):
    na = needs[a]
    usable[na] = max(usable[na], a)
use_keys = sorted(usable.keys())

dp = [-1] * (n + 8)
dp[0] = 0
for a in sorted(usable.values(), reverse=True):
    na = needs[a]
    for i in range(n + 1):
        if dp[i] == -1:
            continue
        dp[i + na] = max(dp[i + na], dp[i] * 10 + a)

print(dp[n])

Solution (Python):
from collections import defaultdict

n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = defaultdict(lambda: 0)
for a in map(int, input().split()):
    na = needs[a]
    usable[na] = max(usable[na], a)
use_keys = sorted(usable.keys())

dp = [-1] * (n + 8)
dp[0] = 0
for a in sorted(usable.values(), reverse=True):
    na = needs[a]
    for i in range(n + 1):
        if dp[i] == -1:
            continue
        dp[i + na] = max(dp[i + na], dp[i] * 10 + a)

print(dp[n])

Solution (Python):


def solve():
    N, M  = map(int, input().split())
    A = sorted(list(map(int, input().split())), reverse=1)
    I = [0,2,5,5,4,5,6,3,7,6]
    dp_a = [0 for _ in range(8)]
    for i in range(2, N+1):
        dp_a[i%8] = max((10*dp_a[j%8]+a for j,a in ((i-I[a], a) for a in A) if j >= 0 and (dp_a[j%8] != 0 or I[a] == i)), default=0)
    res = str(dp_a[i%8])
    return str(res)
if __name__ == '__main__':
    print(solve())

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

def f(x):
    """数xを作るために必要なマッチ棒の本数を返す関数

    :type x: str
    :param x: マッチ棒で作る数
    :rtype: int
    :return: xを作るために必要なマッチ棒の本数
    """

    num_base = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    ret = 0
    for i in range(len(x)):
        ret += num_base[int(x[i])]

    return ret


def max_num(x, y):
    """xとyの大きいほうを返す関数。
    1.文字列の長さが長い方が大きい
    2.文字列の長さが等しいとき、文字列として比較して大きい方が大きい

    :type x: str
    :param x: マッチ棒で作る数
    :type y: str
    :param y: マッチ棒で作る数
    :rtype: str
    :return: 大きい方の数
    """

    if len(x) > len(y):
        return x
    elif len(y) > len(x):
        return y
    else:
        if x > y:
            return x
        else:
            return y


dp = [""] * (n + 1)
for j in range(2, n + 1):
    for i in range(m):
        match = f(str(a[i]))

        if j == match:
            dp[j] = max_num(dp[j], dp[j - match] + str(a[i]))
            dp[j] = max_num(dp[j], str(a[i]) + dp[j - match])

        elif j > match:
            if dp[j - match] != "":
                dp[j] = max_num(dp[j], dp[j - match] + str(a[i]))
                dp[j] = max_num(dp[j], str(a[i]) + dp[j - match])

print(dp[n])

Solution (Python):

import bisect
import heapq
import math
import random
import sys
import copy
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    c = [
        -1,
        2, 
        5, 
        5, 
        4, 
        5, 
        6, 
        3, 
        7, 
        6, 
        ]
    
    if 2 in A and 5 in A:
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 2 in A and 3 in A:
        A.remove(2)
    if 6 in A and 9 in A:
        A.remove(6)



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

    return dp[0]


def main():
    
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if N-Match[A[m]]>=0:
    if dp[N-Match[A[m]]]&(1<<(S-k-1)):
      ans.append(str(A[m]))
      N-=Match[A[m]]
    else:
      for l in range(m+1,len(A)):
        if N-Match[A[l]]>=0:
          if dp[N-Match[A[l]]]&(1<<(S-k-1)):
            m=l
            ans.append(str(A[m]))
            N-=Match[A[m]]
            break
  else:
    for l in range(m+1,len(A)):
      if N-Match[A[l]]>=0:
        if dp[N-Match[A[l]]]&(1<<(S-k-1)):
          m=l
          ans.append(str(A[m]))
          N-=Match[A[m]]
          break
print("".join(ans))

Solution (Python):
n,m,*a=map(int,open(0).read().split())
c,d=[0,2,5,5,4,5,6,3,7,6],[0]*n*9
for i in range(n):
 for j in a:
  if d[i]or i<1:d[i+c[j]]=max(d[i+c[j]],d[i]*10+j)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
c=(0,2,5,5,4,5,6,3,7,6)
d=[0]*n*9
for i in range(n):
 for j in a:
  if d[i]or i<1:d[i+c[j]]=max(d[i+c[j]],d[i]*10+j)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split());c,d=[0,2,5,5,4,5,6,3,7,6],[0]*n*9
for i in range(n):
 for j in a:
  if d[i]or i<1:d[i+c[j]]=max(d[i+c[j]],d[i]*10+j)
print(d[n])

Solution (Python):
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

B = sorted([(a, req[a]) for a in A], key=lambda x: x[0], reverse=True)
a_min, n_min = min(B, key=lambda x: x[1])
g = [(a, n-n_min) for a, n in B if a > a_min and n > n_min]
l = [(a, n-n_min) for a, n in B if a < a_min and n > n_min]
l.sort(key=lambda x: x[1], reverse=True)
C = g + l

def dp(rem, C):
    ret = None
    if rem == 0:
        ret = []
    elif rem > 0:
        for i in range(len(C)):
            a, m = C[i]
            nxt = dp(rem-m, C[i:])
            if nxt is not None:
                ret = [a] + nxt
                break
    return ret


i = 0
while True:
    quo = N // n_min - i
    rem = N % n_min + i * n_min
    lst = dp(rem, C)
    if lst is not None:
        lst = sorted(lst + [a_min] * (quo-len(lst)), reverse=True)
        print(''.join(map(str, lst)))
        break
    i += 1

Solution (Python):
n,m,*a=map(int,open(0).read().split())
c=(0,2,5,5,4,5,6,3,7,6)
d=[0]+[-1]*n*9
for i in range(n):
 for j in a:
  if d[i]+1:d[i+c[j]]=max(d[i+c[j]],d[i]*10+j)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
c=(0,2,5,5,4,5,6,3,7,6)
d=[0]+[-1]*n*9
for i in range(n):
 for j in a:
  if d[i]>=0:d[i+c[j]]=max(d[i+c[j]],d[i]*10+j)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split());c,d=[0,2,5,5,4,5,6,3,7,6],[0]+[-1]*n*9
for i in range(n):
 for j in a:
  if d[i]>=0:d[i+c[j]]=max(d[i+c[j]],d[i]*10+j)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
c=[0,2,5,5,4,5,6,3,7,6]
d=[0]+[-1]*n*9
for i in range(n):
 for j in a:
  if d[i]>=0:d[i+c[j]]=max(d[i+c[j]],d[i]*10+j)
print(d[n])

Solution (Python):
n,m,*a=map(int,open(0).read().split())
d=[0]+[-1]*n*9
for i in range(n):
 for j,k in enumerate((0,2,5,5,4,5,6,3,7,6)):
  if d[i]>=0and j in a:d[i+k]=max(d[i+k],d[i]*10+j)
print(d[n])

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    A = []
    A_num = {}
    A_num[1] = 2
    A_num[2] = 5
    A_num[3] = 5
    A_num[4] = 4
    A_num[5] = 5
    A_num[6] = 6
    A_num[7] = 3
    A_num[8] = 7
    A_num[9] = 6
    for i in range(M):
        A.append(int(input_raw[i]))

    dp = [0] * (N + 1)
    A.sort(reverse = True)

    for i in range(1, N + 1):
        max_num = -sys.maxint
        for a in A:
            if i - A_num[a] >= 0 and dp[i - A_num[a]] >= 0:
                max_num = max(max_num, dp[i - A_num[a]] + 1)
        dp[i] = max_num

    remain = N
    s = ""
    for i in range(dp[N]):
        for a in A:
            if remain - A_num[a] >= 0:
                if dp[remain - A_num[a]] == dp[remain] - 1:
                    s += str(a)
                    remain = remain - A_num[a]
                    break
    print s



if __name__ == '__main__':
    main()

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

costp = sorted([ (cost[a] ,a) for a in A], key=lambda x:x[1], reverse=True)
costX = [ z[0] for z in costp]
A = [ z[1] for z in costp]


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

for i in range(N, 1, -1):
    if (dp[i]) == -1:
        continue

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


ans = ""

i = 0
while i<N:
    
    for c,a in zip(costX,A):
        
        
        
        
        
        if i+c <= N:
            if dp[i]-1 == dp[i+c]:
                ans += str(a)
                i = i+c
                break

print(ans)

Solution (Python):
n, m = map(int, input().split())
needs = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
usable = {}
for a in map(int, input().split()):
    na = needs[a]
    if na in usable:
        usable[na] = max(usable[na], a)
    else:
        usable[na] = a
use_keys = sorted(usable.keys())

dp = [-9] * (n + 1)
dp[0] = 0
for d in range(2, min(8, n + 1)):
    for u in use_keys:
        du = d - u
        if du < 0:
            break
        dp[d] = max(dp[d], dp[du] + 1)
for d in range(8, n + 1):
    for u in use_keys:
        dp[d] = max(dp[d], dp[d - u] + 1)

ans = ''
remain = n
rk = [(str(a), needs[a]) for a in sorted(usable.values(), reverse=True)]
for d in range(dp[n] - 1, -1, -1):
    for a, na in rk:
        ra = remain - na
        if ra < 0:
            continue
        if dp[ra] == d:
            ans += a
            remain = ra
            break

print(ans)

Solution (Python):



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

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

mtoa = {}
for a in sorted(A):
    mtoa[ntom[a]] = a

ms = sorted(mtoa.keys(), key=lambda x: mtoa[x], reverse=True)
dp = [0] + [float('-inf')] * N
for i in range(min(ms), N+1):
    dp[i] = max(dp[i-x] for x in ms if i >= x) + 1

ans = []
left = N
while left:
    for m in ms:
        if left >= m and dp[left] == dp[left - m] + 1:
            left -= m
            ans.append(mtoa[m])
            break
        
print(*ans, sep='')

Solution (Python):
n,m=map(int,input().split())
*a,=map(int,input().split())

cost={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[-1]*(n+1)
v=[0]*(n+1)

dp[0]=0
for i in range(1,n+1):
    for j in range(10)[::-1]:
        if not j in a or i<cost[j]:continue
        if dp[i]<dp[i-cost[j]]+1:
            dp[i]=dp[i-cost[j]]+1
            v[i]=j

p=n
while p!=0:
    print(v[p],end="")
    p-=cost[v[p]]
print()

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

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

remain = dp[N]
match = N
while match > 0:
    
    for a in A:
        
        
        
        
        
        if match - cost[a-1] < 0:
            continue
        if dp[match-cost[a-1]] == remain - 1:
            ans += str(a)
            remain -= 1
            match -= cost[a-1]
            break
print(ans)

Solution (Python):
r=raw_input;N,M=r().split();c,A=[0,2,5,5,4,5,6,3,7,6],sorted(r().split());N=int(N);D,a=[0]+[-1]*N*9,[0,0]*N
for i in range(1,N+1):
 for j in A:
  p=i-c[int(j)]
  if min(p,D[p],D[p]+1-D[i])>=0:D[i],a[i]=D[p]+1,j
S=""
while N:S+=a[N];N-=c[int(a[N])]
print S

Solution (Python):
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]

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

c.sort()
cc = [[c[i],k[c[i]-1]] for i in range(b)]
ccc = [[c[i],k[c[i]-1]] for i in range(b)]
dp = [-1 for i in range(a+1)]
dp[0] = 0
cc.sort(key = lambda x:x[1])
for j in range(b):
	for i in range(a+1):
		if i-cc[j][1] >= 0 and dp[i-cc[j][1]] >= 0:
			dp[i] = max(dp[i-cc[j][1]]+1,dp[i])
ccc.reverse()
k = a
co = ''
for i in range(dp[a]):
	for j in range(b):
		if k-ccc[j][1] >= 0 and dp[k-ccc[j][1]] == dp[k] - 1:
			co += str(ccc[j][0])
			k -= ccc[j][1]
			break
print(co)

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 a in A:
    for i in range(n - mi[a] + 1):
        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):
N, M = map(int, input().split())
A_list = list(map(int, input().split()))
cost_Dict = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A_Dict = {}
for x in A_list:
    A_Dict[x] = cost_Dict[x]


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

A_list = list(A_Dict.keys())
A_list.sort(reverse=True)

for i in range(N+1):
    _list = []
    for x in A_list:
        if i - A_Dict[x] < 0:
            continue
        else:
            dp[i] = max(dp[i], dp[i-A_Dict[x]]+1)

ans = ""
cost = N
while cost > 0:
    for x in A_list:
        if cost - A_Dict[x] < 0:
            continue
        elif dp[cost - A_Dict[x]] == dp[cost] - 1:
            ans += str(x)
            cost -= A_Dict[x]
            break

print(ans)

Solution (Python):
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

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

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

print(''.join(sorted(str(dp[-1]), reverse = True)))

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

num_base = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num_set = set([0])
for i in range(m):
    num_set.add(num_base[a[i]])


def f(x):
    """数xを作るために必要なマッチ棒の本数を返す関数

    :type x: str
    :param x: マッチ棒で作る数
    :rtype: int
    :return: xを作るために必要なマッチ棒の本数
    """

    num_base = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    ret = 0
    for i in range(len(x)):
        ret += num_base[int(x[i])]

    return ret


def max_num(x, y):
    """xとyの大きいほうを返す関数。
    1.文字列の長さが長い方が大きい
    2.文字列の長さが等しいとき、文字列として比較して大きい方が大きい

    :type x: str
    :param x: マッチ棒で作る数
    :type y: str
    :param y: マッチ棒で作る数
    :rtype: str
    :return: 大きい方の数
    """

    if len(x) > len(y):
        return x
    elif len(y) > len(x):
        return y
    else:
        if x > y:
            return x
        else:
            return y


dp = [""] * (n + 1)
for j in range(2, n + 1):
    for i in range(m):
        match = f(str(a[i]))

        if j == match:
            dp[j] = max_num(dp[j], dp[j - match] + str(a[i]))
            dp[j] = max_num(dp[j], str(a[i]) + dp[j - match])

        elif j > match:
            if dp[j - match] != "":
                dp[j] = max_num(dp[j], dp[j - match] + str(a[i]))
                dp[j] = max_num(dp[j], str(a[i]) + dp[j - match])

print(dp[n])

Solution (Python):
r=raw_input
N,M=r().split()
c=[0,2,5,5,4,5,6,3,7,6]
A=sorted(r().split())
N=int(N)
D,a=[0]+[-1]*N*9,[0,0]*N
for i in range(1, N + 1):
 for j in A:
  p=i-c[int(j)]
  if min(p,D[p],D[p]+1-D[i])>=0:D[i],a[i]=D[p]+1,j
S=""
while N:S,N=S+a[N],N-c[int(a[N])]
print S

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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



SET_A=set(A)

ANSLIST=[0]
def dfs(i,NOW):
    if ANSLIST[0]!=0:
        return
    ANS=0
    if NOW==N:
        L=sorted(list(i),reverse=True)
        
        
        ANSLIST[0]=int(("".join(L)))
        return

    elif NOW>N:
        return 
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
A.sort(key=lambda x:M[x])
dfs("",0)

x=ANSLIST[0]
stx=str(x)
from collections import Counter
counter=Counter(stx)


import itertools
for i,j,k in list(itertools.combinations(range(1,10),3)):
    for l,m,n in list(itertools.combinations(range(1,10),3)):
        if i in SET_A and j in SET_A and k in SET_A and l in SET_A and m in SET_A and n in SET_A and M[i]+M[j]+M[k]==M[l]+M[m]+M[n] and \
           counter[str(i)]>0 and counter[str(j)]>0 and counter[str(k)]>0 and (n>k or (n==k and m>j) or (n==k and m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)],counter[str(k)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x
                    counter[str(k)]-=x
                    counter[str(l)]+=x
                    counter[str(m)]+=x
                    counter[str(n)]+=x

for i,j in list(itertools.combinations(range(1,10),2)):
    for l,m in list(itertools.combinations(range(1,10),2)):
        if i in SET_A and j in SET_A and l in SET_A and m in SET_A and M[i]+M[j]==M[l]+M[m] and \
           counter[str(i)]>0 and counter[str(j)]>0 and (m>j or (m==j and l>i)):
                    x=min(counter[str(i)],counter[str(j)])
                    counter[str(i)]-=x
                    counter[str(j)]-=x

                    counter[str(l)]+=x
                    counter[str(m)]+=x

for i in range(1,10):
    for l in range(1,10):
        if i in SET_A and l in SET_A and l>i and M[i]==M[l] and counter[str(i)]>0:
            counter[str(l)]+=counter[str(i)]
            counter[str(i)]=0



ANS=""
for i in range(9,-1,-1):
    ANS+=str(i)*counter[str(i)]

print(ANS)

Solution (Python):
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = inpl()
A.sort(reverse = True)

inf = float('inf')
match = (inf, 2, 5, 5, 4, 5, 6, 3, 7, 6)
matnum = set([match[a] for a in A])
dp = [0]+[-inf]*N

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

print(''.join(sorted(str(dp[-1]), reverse = True)))

Solution (Python):
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)
dp = [0]+[-1]*n
for i in range(1,n+1):
    for j in a:
        if l[j] <= i:
            dp[i] = max(dp[i], dp[i-l[j]]*10+j)
print(dp[-1])

Solution (Python):
def d_match_matching(N, M, A):
    
    num_usedmatch = {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(1, N + 1):
        for a in A:
            if i - num_usedmatch[a] >= 0:
                
                dp[i] = max(dp[i], dp[i - num_usedmatch[a]] * 10 + a)
    return dp[N]

N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_match_matching(N, M, A))

Solution (Python):
import numpy as np
import math

INF = 1000000

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

match = {a:match[a] for a in A}

dp = []

for i in range(N+1):
    if i == 0:
        dp.append(0)
    else:
        tmp = [dp[i-m] for m in match.values() if i-m >= 0]
        if tmp == []:
            dp.append(-float('inf'))
        else:
            dp.append(max(tmp)+1)
s = ''
nums = list(match.keys())
nums.sort(reverse=True)
while(True):
    for num in nums:
        if N - match[num] >= 0 and dp[N - match[num]] == dp[N] - 1:
            s = s + str(num)
            N-=match[num]
            break
    if N == 0:
        break

print(int(s))

Solution (Python):
def num(x):
	if x == 1:
		return 2
	elif x == 2:
		return 5
	elif x == 3:
		return 5
	elif x == 4:
		return 4
	elif x == 5:
		return 5
	elif x == 6:
		return 6
	elif x == 7:
		return 3
	elif x == 8:
		return 7
	elif x == 9:
		return 6

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

num_to_dig = [0 for _ in range(9)]
for i in a:
	num_to_dig[num(i)] = max(num_to_dig[num(i)], i)

dp = [-float("inf")] * (n+1)
dp[0] = 0
for i in range(1, n+1):
	for j in range(9):
		if num_to_dig[j] > 0 and i >= j:
			dp[i] = max(dp[i], dp[i-j] * 10 + num_to_dig[j])
print(dp[n])

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
 for j in A:p=i-c[j];D[i],a[i]=[[D[i],a[i]],[D[p]+1,j]][min(p,D[p],D[p]+1-D[i])>=0]

S, p = "", N
while p:S,p=S+str(a[p]),p-c[a[p]]
print S

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
 for j in A:
  p=i-c[j]
  if min(p,D[p],D[p]+1-D[i])>=0:D[i],a[i]=D[p]+1,j

S, p = "", N
while p:S,p=S+str(a[p]),p-c[a[p]]
print S

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        p = i - c[j]
        if min(p, D[p], D[p] + 1 - D[i]) >= 0:
            D[i], a[i] = D[p] + 1, j

S, p = "", N
while p:S,p=S+str(a[p]),p-c[a[p]]
print S

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        p = i - c[j]
        if min(p, D[p], D[p] + 1 - D[i]) >= 0:
            D[i], a[i] = D[p] + 1, j

S, p = "", N
while p:
 S+=str(a[p])
 p-=c[a[p]]
print S

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        p = i - c[j]
        if min(p, D[p], D[p] + 1 - D[i]) >= 0:
            D[i], a[i] = D[p] + 1, j

S, p = "", N
while p:
 S+=str(a[p])
 p-=c[a[p]]

print S

Solution (Python):
N, M = map(int, raw_input().split())
c = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        p = i - c[j]
        if min(p, D[p], D[p] + 1 - D[i]) >= 0:
            D[i], a[i] = D[p] + 1, j

S, p = "", N
while p:
    S += str(a[p])
    p -= c[a[p]]
print S

Solution (Python):
Q = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}

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


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

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


ans = ''


A.sort(reverse=True)

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

print(ans)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

DP = [0] + [-1] * N * 9
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if min(pos, DP[pos], DP[pos] + 1 - DP[i]) >= 0:
            DP[i], ans[i] = DP[pos] + 1, j

S, pos = "", N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if pos >= 0 and DP[pos] >= 0 and DP[i] <= DP[pos] + 1:
            DP[i], ans[i] = DP[pos] + 1, j

S = ""
pos = N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

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

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if pos < 0 or DP[pos] < 0:
            continue
        if DP[i] <= DP[pos] + 1:
            DP[i] = DP[pos] + 1
            ans[i] = j

S = ""
pos = N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if pos < 0 or DP[pos] < 0:
            continue
        if DP[i] <= DP[pos] + 1:
            DP[i] = DP[pos] + 1
            ans[i] = j

S = ""
pos = N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A = sorted(map(int, raw_input().split()))

DP = [0] + [-1] * N
ans = [0, 0] * N

for i in range(1, N + 1):
    for j in A:
        pos = i - cost[j]
        if pos < 0 or DP[pos] < 0:
            continue
        if DP[i] <= DP[pos] + 1:
            DP[i] = DP[pos] + 1
            ans[i] = j

S = ""
pos = N
while pos:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S

Solution (Python):



MAX_N = 10005
MAX_M = 11
dp = [[-1 for j in range(MAX_N)] for i in range(MAX_M)]


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

    f = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    dp[0][0] = 0
    for i in range(M):
        for j in range(N+1):
            if j < f[A[i]]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-f[A[i]]]+1)

    ans = []
    cj = N
    for i in range(M, 0, -1):
        for j in range(cj//f[A[i-1]], -1, -1):
            x = dp[i-1][cj-f[A[i-1]]*j]
            y = dp[i][cj]
            if dp[i-1][cj-f[A[i-1]]*j] == dp[i][cj] - j:
                for k in range(j):
                    ans.append(str(A[i-1]))
                cj -= f[A[i-1]] * j
                break

    print("".join(ans))


if __name__ == '__main__':
    main()

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
cost = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
A = map(int, raw_input().split())

DP = [0] + [-1] * N
ans = [0] * N + [0]

for i in range(1, N + 1):
    for j in range(10)[::-1]:
        if not j in A:
            continue
        if cost[j] > i:
            continue
        if DP[i - cost[j]] < 0:
            continue
        if DP[i] < DP[i - cost[j]] + 1:
            DP[i] = DP[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = N
while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print S