Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

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

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

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

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

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

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Accepted

Solution code:
import sys

K = {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()]

items = sorted(A, reverse=True)
weights = [K[x] for x in items]

m = [[0]*M] + [None for i in range(N)]
for i in range(1, N+1):
	best = [0]*M
	
	for j in range(M):
		remaining = i - weights[j]
		if remaining >= 0 and m[remaining] is not None and sum(m[remaining])+1 > sum(best):
			best = m[remaining][:j] + [m[remaining][j]+1] + m[remaining][j+1:]
	
	if sum(best) == 0:
		best = None

	m[i] = best

for i in range(M):
	for j in range(m[N][i]):
		sys.stdout.write(str(items[i]))

sys.stdout.write("\n")

Submission status: Accepted

Solution code:
def greater(a,b):
    if a is None:
        return b
    if len(a)>len(b):
        return a
    if len(b)>len(a):
        return b
    for i in range(len(a)):
        if a[i]>b[i]:
            return a
        if b[i]>a[i]:
            return b
    return a

c={"1":2,"2":5,"3":5,"4":4,"5":5,"6":6,"7":3,"8":7,"9":6}
n,m=map(int,input().split())
l=input().split()
l.sort()
max=[None for i in range(10010)]
for a in l:
    max[c[a]]=a
for i in range(2,n):
    if max[i] is not None:
        for a in l:
            k=max[i]+a if max[i][0]>a else a+max[i]
            max[i+c[a]]=greater(max[i+c[a]],k)
print(max[n])

Submission status: Accepted

Solution code:

def get_match_list(num_list, num_num):
    match_num_list = set()
    match_dic = [2,5,5,4,5,6,3,7,6]
    for num in num_list:
        match_num_list.add(match_dic[num-1])
    match_num_list = list(match_num_list)
    match_num_list.sort()
    return match_num_list

def get_dp(use_match_list, match_nun):
    dp = [-1 for i in range(match_nun + 1)]
    dp[0] = 0
    for i in range(2, match_nun + 1):
        for macth_bar in use_match_list:
            if dp[i-macth_bar] >= 0:
                dp[i] = dp[i-macth_bar] + 1
                break
    return dp

def print_ans(dp, match_nun, num_list):
    match_dic = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    max_ketasuu = dp[match_nun]
    ans = ''
    while match_nun > 0:
        for num in num_list:
            use_match_num = match_dic[num - 1]
            if match_nun - use_match_num < 0:
                continue
            if dp[match_nun - use_match_num] == max_ketasuu - 1:
                ans += str(num)
                match_nun -= use_match_num
                max_ketasuu -= 1
                break
    print(ans)



def main():
    match_nun, num_num = map(int, input().split())
    num_list = list(map(int, input().split()))
    num_list.sort(reverse=True)
    use_match_list = get_match_list(num_list, num_num)
    dp = get_dp(use_match_list, match_nun)
    print_ans(dp, match_nun, num_list)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])

def main():
    n, m = get_next_ints()
    numbers = get_next_ints()
    costs = [0,2,5,5,4,5,6,3,7,6]
    from collections import defaultdict
    
    cost_number = defaultdict(int)
    for number in numbers:
        cost = costs[number]
        cost_number[cost] = max(cost_number[cost], number)
    use_numbers = cost_number.values()
    costs_numbers = list(zip( cost_number.values(),list(cost_number.keys())))
    costs_numbers.sort(reverse=True)
    #print(costs_numbers)
    
    dp = {0:0}
    for i in range(1,n+1):
        answers = []
        for number, cost in costs_numbers:
            if (i - cost) in dp:
                answers.append(dp[(i - cost)])
        if answers:
            dp[i] = max(answers) + 1
    #print(dp)
    digits = []
    
    remain = n
    while remain > 0:
        current = dp[remain]
        for number, cost in costs_numbers:
            if (remain - cost) in dp:
                if dp[(remain - cost)] == current - 1:
                    digits.append(str(number))
                    remain -= cost
                    break
                    
    print("".join(digits))
        
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	
	d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	num2match = {key:val for key, val in d.items() if key in nums}
	
	dp = [-1 for i in range(n + 1)]
	dp_keta = [0 for i in range(n + 1)]

	dp[0] = 0
	val_set = list(set(num2match.values()))
	match2num = {v:max([int(key) for key, val in num2match.items() if val == v]) for v in val_set}

	cnt = 0
	for i in range(2, n + 1):
		for val in val_set:
			#print(val)
			cnt += 1
			if i >= val and dp[i - val] >= 0:
				tmp = match2num[val] * (10 ** dp_keta[i - val]) + dp[i - val]
				dp[i] = max(dp[i], tmp)
				dp_keta[i] = max(dp_keta[i], dp_keta[i - val] + 1)

	#print(num2match)
	#print(match2num)
	#print(dp)
	#print(dp)
	print(int(dp[n]))
	#print(cnt)
 
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians, log10
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul, xor
from copy import copy, deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
A = LIST()
need = [0,2,5,5,4,5,6,3,7,6]

dp = [''] * (N+10)
for a in A:
    dp[need[a]] = max(dp[need[a]], str(a))

for i in range(N):
    if dp[i] != '':
        for a in A:
            # 基本は文字列の長さ(桁数)で比較
            if len(dp[i+need[a]]) < len(dp[i])+1:
                dp[i+need[a]] = dp[i]+str(a)
            # それが同じ時だけ大小で比較
            elif len(dp[i+need[a]]) == len(dp[i])+1:
                dp[i+need[a]] = max(dp[i+need[a]], dp[i]+str(a))
print(dp[N])

Submission status: Accepted

Solution code:
def greater(a,b):
    if len(a)>len(b):
        return a
    elif len(b)>len(a):
        return b
    for i in range(len(a)):
        if a[i]<b[i]:
            return b
        if b[i]<a[i]:
            return a
    return a

cost=[0,2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
la=[int(a) for a in input().split()]
la.sort()
sa=[str(a) for a in la]
ca=[cost[a] for a in la]
max=[None for i in range(10010)]
for i in range(m):
    max[ca[i]]=sa[i]
for i in range(2,n):
    if max[i]==None:
        continue
    for j in range(m):
        if max[i][0]>sa[j]:
            k=max[i]+sa[j]
        else:
            k=sa[j]+max[i]
        if max[i+ca[j]]==None:
            max[i+ca[j]]=k
        else:
            max[i+ca[j]]=greater(max[i+ca[j]],k)
print(max[n])

Submission status: Accepted

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

dp = [0]+ [-float("INF")]*N 
# i 本のマッチで作れる最高の桁数
for i in range(1,N+1):
  for b in aval:
    if i < b:
      continue
    elif dp[i-b] >= 0:
      dp[i] = dp[i-b] + 1
      break
      
#作れる桁数はdp[-1]=dp[N] で, 最高桁にi が使えるかどうかの条件は, 
#a in A かつ dp[N- honsuu[a]] = dp[N] - 1
A.sort(reverse=True)
ans = []
for i in range(dp[N],0,-1):
  for a in A:
    if N - honsuu[a] < 0:continue
    if dp[N - honsuu[a]] == dp[N] - 1:
      N -= honsuu[a]
      ans += [a]
      break
print(''.join(map(str, ans)))

Submission status: Accepted

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

dp = [0]+ [-float("INF")]*N 
# i 本のマッチで作れる最高の桁数
for i in range(1,N+1):
  for b in aval:
    if i < b:
      continue
    elif dp[i-b] >= 0:
      dp[i] = dp[i-b] + 1
      break
      
#作れる桁数はdp[-1]=dp[N] で, 最高桁にi が使えるかどうかの条件は, 
#a in A かつ dp[N- honsuu[a]] = dp[N] -1
A.sort(reverse=True)
ans = []
for i in range(dp[N],1,-1):
  for a in A:
    if N - honsuu[a] < 0:continue
    if dp[N - honsuu[a]] == dp[N] - 1:
      N -= honsuu[a]
      ans += [a]
      break
      
final = 0
for i in range(10):
  if i in A and honsuu[i] == N:
    final = i
ans += [final]
print(''.join(map(str, ans)))

Submission status: Accepted

Solution code:
#A
"""
a,b = map(int, input().split())
if b % a == 0:
    print(b + a)
else:
    print(b-a)
"""

#B
"""
n, m = map(int, input().split())
ans = list(map(int, input().split()))
del ans[0]
ans = set(ans)
for i in range(n-1):
    a = list(map(int, input().split()))
    del a[0]
    ans = ans & set(a)
print(len(ans))
"""


#C
"""
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
print(gcd_list(a))
"""

#D
n,m = map(int, input().split())
a = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = [-float("inf") for _ in range(n + 1)]
num_ans = []
a.sort(reverse=True)
for i in a:
    num_ans.append(num[i])
ans[0] = 0
for i in range(n + 1):
    for b in num_ans:
        if i - b >= 0:
            ans[i] = max(ans[i - b] + 1, ans[i])
anse = ""
while ans[n] > 0:
    for k, i in enumerate(num_ans):
        if n - i >= 0:
            
            if ans[n] - 1 == ans[n - i]:
                anse += str(a[k])
                n -= i
                break
    if n < 0:
        break
            
print(anse)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def strmax(a, b):
    if len(a) > len(b):
        return a
    elif len(a) < len(b):
        return b
    else:
        return max(a, b)


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [None] * (N+1)
    dp[0] = ""
    cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    for i in range(N+1):
        for d in A:
            if i < cost[d]:
                continue
            prev = dp[i - cost[d]]
            if prev is None:
                continue
            else:
                candidate = strmax(prev + str(d),
                                   str(d) + prev)
            if dp[i] is None:
                dp[i] = candidate
            else:
                dp[i] = strmax(dp[i], candidate)
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

N,M = list(map(int, input().split()))
a = list(map(int, input().split()))
# a = np.sort(a)[::-1]

dp = [-1e+8] * (N + 1)
dp[0] = 0
for i in range(N+1):
    for aa in a:
        if i >= rate[aa]:
            dp[i] = max([dp[i], dp[i-rate[aa]]*10 + aa])
print(dp[-1])

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
am = list(map(int, input().split()))
c = [0,2,5,5,4,5,6,3,7,6]
f = [-1]*10010
f[0]=0
for i in range(1,N+1):
    for x in am:
        if i-c[x] >= 0:
            f[i] = max(f[i], f[i-c[x]]*10 +x)
            
print(f[N])

Submission status: Accepted

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

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

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

print(dp[-1])

Submission status: Accepted

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

A.sort(reverse=True)

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

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

print(dp[-1])

Submission status: Accepted

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


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [0] + [-float('inf')] * (N+1)       # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

for num_match in range( 2, N+1 ):
    for Aj in A:
        if num_match >= cost[Aj]:
            dp[num_match] = max( dp[num_match], dp[num_match-cost[Aj]]+1 )


ans = ""
digit = dp[N]

A.sort( reverse=True )
while N > 0:
    for Ai in A:
        if N-cost[Ai] >=0 and dp[N-cost[Ai]] == digit-1:
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

print( ans )

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = sorted(map(int,input().split()))[::-1]
c = [0,2,5,5,4,5,6,3,7,6]
dp = [-float('inf')]*(n+1)
dp[0] = 0
for i in range(2, n+1):
    for j in a:
        if i >= c[j]:
            dp[i] = max(dp[i], dp[i-c[j]]+1)
r = []
while n:
    i = max((i for i in a if n>=c[i]), key=lambda x: dp[n-c[x]])
    r.append(i)
    n -= c[i]
print(''.join(map(str, r)))

Submission status: Accepted

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

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

dp = [[-1 for n in range(N+1)] for m in range(M+1)]
dp[0][0] = 0
#keta
dp_r = [[-1 for n in range(N+1)] for m in range(M+1)]
#m

d = {}
for a in A:
    d[a] = c[a-1]
#print(d)

inv_d = {}
for k,v in d.items():
    if v in inv_d:
        if k > inv_d[v]:
            inv_d[v] = k
    else:
        inv_d[v] = k
#print(inv_d)

s_A = sorted(inv_d.items(), key=lambda x:x[0],reverse=True)
#print(s_A)
A = [a[1] for a in s_A]
M = len(A)

for m in range(1,M+1):
    for n in range(N+1):
        #dp[m][n] = max(dp[m-1][n],
        #dp[m][n-c[A[m-1]-1]] + 1 if (n-c[A[m-1]-1])>=0 and dp[m][n-c[A[m-1]-1]] != -1 else -1)
        if n-c[A[m-1]-1] >= 0 and dp[m][n-c[A[m-1]-1]] != -1:
            if dp[m-1][n] < (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 1
            elif dp[m-1][n] == (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 2
            else:
                dp[m][n] = dp[m-1][n]
                dp_r[m][n] = 0
        else:
            dp[m][n] = dp[m-1][n]
            dp_r[m][n] = 0


#import pprint
#pprint.pprint(dp,width=100)
#pprint.pprint(dp_r,width=100)

def trace(dp,m,n):
    r=[[]]
    for _ in range(N+M+2):
        if m==0 and n==0:
            return r
        elif dp_r[m][n] == 0:
            m = m-1
        elif dp_r[m][n] == 1:
            r = [r_+[m] for r_ in r]
            n = n-c[A[m-1]-1]
        elif dp_r[m][n] == 2:
            r_1 = trace(dp,m-1,n)
            r_2 = trace(dp,m,n-c[A[m-1]-1])
            return [r[0]+r_ for r_ in r_1] + [r[0]+r_+[m] for r_ in r_2]

tm = trace(dp,M,N)

ans = []
for tm_ in tm:
    ans_ = [inv_d[c[A[m-1]-1]] for m in tm_]
    ans_.sort(reverse=True)
    ans += [ans_]

ans.sort(reverse=True)
#print(ans)
for ans_ in ans[0]:
    print(ans_,sep='',end='')
print()

Submission status: Accepted

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

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

dp = [[-1 for n in range(N+1)] for m in range(M+1)]
dp[0][0] = 0
#keta
dp_r = [[-1 for n in range(N+1)] for m in range(M+1)]
#m

d = {}
for a in A:
    d[a] = c[a-1]
#print(d)

inv_d = {}
for k,v in d.items():
    if v in inv_d:
        if k > inv_d[v]:
            inv_d[v] = k
    else:
        inv_d[v] = k
#print(inv_d)

s_A = sorted(inv_d.items(), key=lambda x:x[0])
A = [a[1] for a in s_A]
M = len(A)

for m in range(1,M+1):
    for n in range(N+1):
        #dp[m][n] = max(dp[m-1][n],
        #dp[m][n-c[A[m-1]-1]] + 1 if (n-c[A[m-1]-1])>=0 and dp[m][n-c[A[m-1]-1]] != -1 else -1)
        if n-c[A[m-1]-1] >= 0 and dp[m][n-c[A[m-1]-1]] != -1:
            if dp[m-1][n] < (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 1
            elif dp[m-1][n] == (dp[m][n-c[A[m-1]-1]] + 1):
                dp[m][n] = dp[m][n-c[A[m-1]-1]] + 1
                dp_r[m][n] = 2
            else:
                dp[m][n] = dp[m-1][n]
                dp_r[m][n] = 0
        else:
            dp[m][n] = dp[m-1][n]
            dp_r[m][n] = 0


#import pprint
#pprint.pprint(dp,width=100)
#pprint.pprint(dp_r,width=100)

def trace(dp,m,n):
    r=[[]]
    for _ in range(N+M+2):
        if m==0 and n==0:
            return r
        elif dp_r[m][n] == 0:
            m = m-1
        elif dp_r[m][n] == 1:
            r = [r_+[m] for r_ in r]
            n = n-c[A[m-1]-1]
        elif dp_r[m][n] == 2:
            r_1 = trace(dp,m-1,n)
            r_2 = trace(dp,m,n-c[A[m-1]-1])
            return [r[0]+r_ for r_ in r_1] + [r[0]+r_+[m] for r_ in r_2]

tm = trace(dp,M,N)

ans = []
for tm_ in tm:
    ans_ = [inv_d[c[A[m-1]-1]] for m in tm_]
    ans_.sort(reverse=True)
    ans += [ans_]

ans.sort(reverse=True)
#print(ans)
for ans_ in ans[0]:
    print(ans_,sep='',end='')
print()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
cd = [(a, cost[a]) for a in A]
cd.sort(key=lambda x: x[0], reverse=True)

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

ans, i = [], N
for _ in range(dp[-1]):
    for a, c in cd:
        if i - c >= 0 and dp[i - c] == dp[i] - 1:
            ans.append(a)
            i = i - c
            break

print(''.join(map(str, ans)))

Submission status: Accepted

Solution code:
from copy import copy
from sys import stdout

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

W, _ = map(int, raw_input().strip().split(' '))

dp = [[0 for _ in xrange(9)] for _ in xrange(W + 1)]

values  = map(int, raw_input().strip().split(' '))
weights = [digit_costs[values[i] - 1] for i in xrange(len(values))]

def is_larger(a, b) : 
    a_s, b_s = sum(a), sum(b)
    if a_s != b_s : 
        if a_s > b_s : 
            return True
        return False

    for i in xrange(8, -1, -1) : 
        if a[i] > b[i] : 
            return True
        if b[i] > a[i] : 
            return False

    return False

for i in xrange(len(values)) : 
    vi = values[i]
    wi = weights[i]
    
    for w in xrange(0, W - wi + 1) : 
        if any(x for x in dp[w]) or not w :
            temp = copy(dp[w])
            temp[vi - 1] += 1
            if is_larger(temp, dp[w + wi]) :
                dp[w + wi] = temp



result = ''
for x in xrange(8, -1, -1) : 
    if dp[-1][x] : 
        result += str(x + 1) * dp[-1][x]

print result

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
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_size = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for size in range(1, max_size + 1):
    for idxs in itertools.combinations_with_replacement(range(len(digits)), size):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

      replaces = [digits[i][0] for i in idxs]
      replaces.sort(reverse=True)
      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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

# xを作るために使うマッチの本数
h = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

# dp[i] = i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

# dp[i] = i本使ってできる最大の数

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)

# xを作るために使うマッチの本数
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

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

# dp[i] = i本使ってできる最大の数

# xを作るために使うマッチの本数
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])