Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

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

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

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

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

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

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Wrong Answer

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

num = [
    [1, 2],
    [2, 5],
    [3, 5],
    [4, 4],
    [5, 5],
    [6, 6],
    [7, 3],
    [8, 8],
    [9, 6]
]
num = [x for x in num if x[0] in A]
num.sort(key=lambda x: x[1])

ans = []


def solve(k):
    for x in num:
        if x[1] <= k:
            k -= x[1]
            ans.append(x[0])
            break
    return k


def solve2(k, l):
    cost = 0
    for x in num:
        if x[0] == l:
            cost = x[1]
            break
    for x in num:
        if x[0] > l and k >= x[1]-cost:
            k -= x[1]-cost
            return (x[0], k)

    return (0, k)


prev = 0
k = N

while(prev != k):
    prev = k
    k = solve(k)
num.sort(reverse=True)


for i in range(len(ans)):
    tmp = solve2(k, ans[i])
    if tmp[0] != 0:
        ans[i] = tmp[0]
        k = tmp[1]
    else:
        break
num.sort(key=lambda x: x[1], reverse=True)

for i in reversed(range(len(ans))):
    if k == 0:
        break
    for x in num:
        if x[0] == ans[-1]:
            k += x[1]
            break
    for x in num:
        if x[1] <= k:
            ans[i] = x[0]
            k -= x[1]
            break
print("".join(map(str, ans)))

Submission status: Wrong Answer

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

num = [
    [1, 2],
    [2, 5],
    [3, 5],
    [4, 4],
    [5, 5],
    [6, 6],
    [7, 3],
    [8, 8],
    [9, 6]
]
num = [x for x in num if x[0] in A]
num.sort(key=lambda x: x[1])

ans = []


def solve(k):
    for x in num:
        if x[1] <= k:
            k -= x[1]
            ans.append(x[0])
            break
    return k


def solve2(k, l):
    cost = 0
    for x in num:
        if x[0] == l:
            cost = x[1]
            break
    for x in num:
        if x[0] > l and k >= x[1]-cost:
            k -= x[1]-cost
            return (x[0], k)

    return (0, k)


prev = 0
k = N

while(prev != k):
    prev = k
    k = solve(k)
num.sort(reverse=True)


for i in range(len(ans)):
    tmp = solve2(k, ans[i])
    if tmp[0] != 0:
        ans[i] = tmp[0]
        k = tmp[1]
    else:
        break

if k > 0:
    for x in num:
        if x[0] == ans[-1]:
            k += x[1]
            break

    for x in num:
        if x[1] == k:
            ans[-1] = x[0]
print("".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    b = [0,2,5,5,4,5,6,3,7,6]
    c = [[b[i], -i] for i in a]
    c.sort()
    result = [[] for _ in range(n+1)]
    dp = [-1]*(n+1)
    dp[0] = 0
    for i in range(1, n+1):
        for j in c:
            if i-j[0] >= 0:
                if dp[i-j[0]] >= 0:
                    dp[i] = dp[i-j[0]] +1
                    break
    result = []
    i = n
    while i > 0:
        j = 0
        while j < len(c):
            if dp[i-c[j][0]] + 1 == dp[i]:
                result.append(-c[j][1])
                i -= c[j][0]
                j = len(c)
            else:
                j += 1
    result.sort(reverse = True)
    print(''.join(map(str, result)))
if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    b = [0,2,5,5,4,5,6,3,7,6]
    c = [[b[i], -i] for i in a]
    c.sort()
    result = [[] for _ in range(n+1)]
    dp = [-1]*(n+1)
    dp[0] = 0
    for i in range(1, n+1):
        for j in c:
            if i-j[0] >= 0:
                if dp[i-j[0]] >= 0:
                    dp[i] = dp[i-j[0]] +1
                    break
    result = []
    i = n
    while i > 0:
        j = 0
        while j < len(c):
            if dp[i-c[j][0]] + 1 == dp[i]:
                result.append(-c[j][1])
                i -= c[j][0]
                j = len(c)
            else:
                j += 1            
    print(''.join(map(str, result)))
if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
dp = [-10**5]*(n+1)
dp[0] = 0
t = [0,2,5,5,4,5,6,3,7,6]
a = set(map(int,input().split()))
for i in range(2,n+1):
  for x in a:
    if i-t[x] >= 0 and dp[i] < dp[i-t[x]] + 1:
      dp[i] = dp[i-t[x]] + 1
a = list(a)
a.sort(reverse=True)
cur = ""
idx = n
while idx:
  for x in a:
    if idx - t[x] >= 0 and dp[idx] == dp[idx-t[x]] + 1:
      cur += str(x)
      idx -= t[x]
      continue
print(cur)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement
from collections import Counter

def get_max_value(input_match_num):
  if input_match_num in mem: return mem[input_match_num]

  max_value = -float('inf')
  for value, match_num in A.items():
    if input_match_num == match_num:max_value = max(max_value,value)
  mem[input_match_num] = max_value
  return max_value

N,M = map(int,input().split())
match_nums = [2,5,5,4,5,6,3,7,6]
A = {}
mem = {}
min_match_num = float('inf')
for a in map(int,input().split()):
  A[a] = match_nums[a-1]
  min_match_num = min(min_match_num, match_nums[a-1])

keta_nums = N//min_match_num
rest_nums = N%min_match_num

value = get_max_value(min_match_num)
if rest_nums == 0:
  print(str(value)*keta_nums)
  exit()

ans = -float('inf')
A_values = set(A.values())
for cmb in combinations_with_replacement([i for i in range(keta_nums)], rest_nums):
  tmp_values = [value]*keta_nums
  flag = True
  for idx, add_num in Counter(cmb).items():
    if min_match_num + add_num in A_values:
      tmp_values[idx] = get_max_value(min_match_num+add_num)
    else:
      flag = False
  if flag == True:ans = max(ans, sum([val*(10**(keta_nums-idx-1)) for idx, val in enumerate(tmp_values)]))
  #print(ans, tmp_values, cmb)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations_with_replacement
from collections import Counter

def get_max_value(input_match_num):
  max_value = -float('inf')
  if input_match_num in mem: return mem[input_match_num]
  for value, match_num in A.items():
    if input_match_num == match_num:max_value = max(max_value,value)
  mem[input_match_num] = max_value
  return max_value

N,M = map(int,input().split())
match_nums = [2,5,5,4,5,6,3,7,6]
A = {}
mem = {}
for a in map(int,input().split()):
  A[a] = match_nums[a-1]

min_match_num = min(A.values())
keta_nums = N//min_match_num
rest_nums = N%min_match_num

value = get_max_value(min_match_num)
if rest_nums == 0:
  print(str(value)*keta_nums)
  exit()

ans = -float('inf')
for cmb in combinations_with_replacement([i for i in range(keta_nums)], rest_nums):
  tmp_values = [value]*keta_nums
  flag = True
  for idx, add_num in Counter(cmb).items():
    if min_match_num + add_num in A.values():
      tmp_values[idx] = get_max_value(min_match_num+add_num)
    else:
      flag = False
  if flag == True:ans = max(ans, int(''.join([str(s) for s in tmp_values])))
  #print(ans, tmp_values, cmb)
print(ans)

Submission status: Wrong Answer

Solution code:
d=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=list(map(int,input().split()))
l=[]
for a in A:
    l.append([a,d[a]])
l.sort(key=lambda x:x[0],reverse=True)
l.sort(key=lambda x:x[1])
min_val,min_match=l[0]

ans=[]
if N%min_match==0:
    ans.append(int(str(min_val)*(N//min_match)))
from itertools import combinations_with_replacement
for i in range(1,M):
    f = False
    r = 1
    while not f:
        for p in combinations_with_replacement(l[1:],r):
            v=[]
            m_sum=0
            for val,mat in p:
                v.append(str(val))
                m_sum+=mat
            if (N-m_sum)%min_match==0:
                ans.append(int(''.join(sorted(v+
                    [str(min_val)]*((N-m_sum)//min_match),reverse=True))))
        f = (len(ans) != 0)
        r += 1
print(max(ans))

Submission status: Wrong Answer

Solution code:
import sys
import queue

#+++++

def sa(v, p):
	return v //p, v %p

def ggg(value, p_list, ctv):
	dd=p_list[:]
	#print('gfg',dd)
	if len(dd)==0:
		return None
	a=dd.pop(0)
	if a > value:
		return None
	
	m,p=sa(value, a)
	if p == 0:
		aa= [max(ctv[a])]*(m)
		return aa
	else:
		best_st=None
		for i in range(min(m+1,6)):
			nokori=p+i*a
			ret=bbb(nokori, ctv)
			if ret is not None:
				aa= [max(ctv[a])]*(m-i)
				st=ret+aa
				if is_big(st, best_st):
					best_st=st
				
		return best_st

def bbb(value, ctv):
	ol=queue.PriorityQueue()
	kk_costs=ctv.keys()
	
	best_st=None
	
	cc=0
	st=[]
	ol.put((cc,(cc, st)))
	while not ol.empty():
		scc, (cc, st) = ol.get()
		#pa((scc,cc,st))
		if scc > value:
			return best_st
			
		if scc == value:
			if is_big(st, best_st):
				best_st=st
			continue
				
		for cost in kk_costs:
			tst=st[:]
			tst.append(max(ctv[cost]))
			ol.put((cc+cost, (cc+cost, tst)))
	return None
	
def is_big(base, other):
	if other is None:
		return True
	if base is None:
		return False
		
	if len(base) != len(other):
		return len(base) > len(other)
	return base > other


def mk_value(a_ll):
	if a_ll is None:
		return 0
		
	a_ll.sort(reverse=True)
	a_ll2=[str(v) for v in a_ll]
	ans=''.join(a_ll2)
	return ans
	
def main():
	n , _ = map(int, input().split())
	al = list(map(int, input().split())	)
	
	cost_list=[1000, 2,5,5,4,5,6,5,7,6]
	
	aal=[(v, cost_list[v]) for v in al]
	aal.sort(key=lambda x:-x[0])
	ctv={}
	for v in aal:
		ctv.setdefault(v[1], []).append(v[0])
	
	#for kk in ctv.keys():
	#	pa((kk,':',ctv[kk]))
	aal=list(ctv.keys())
	aal.sort()
	
	ccc = ggg(n, aal, ctv)
	ans=mk_value(ccc)
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import queue

#+++++

def sa(v, p):
	return v //p, v %p

def ggg(value, p_list, ctv):
	dd=p_list[:]
	#print('gfg',dd)
	if len(dd)==0:
		return None
	a=dd.pop(0)
	if a > value:
		return None
	
	m,p=sa(value, a)
	if p == 0:
		aa= [max(ctv[a])]*(m)
		return aa
	else:
		best_st=None
		for i in range(min(m+1,20)):
			nokori=p+i*a
			ret=bbb(nokori, ctv)
			if ret is not None:
				aa= [max(ctv[a])]*(m-i)
				st=ret+aa
				if is_big(st, best_st):
					best_st=st
				
		return best_st

def bbb(value, ctv):
	ol=queue.PriorityQueue()
	kk_costs=ctv.keys()
	
	best_st=None
	
	cc=0
	st=[]
	ol.put((cc,(cc, st)))
	while not ol.empty():
		scc, (cc, st) = ol.get()
		#pa((scc,cc,st))
		if scc > value:
			return best_st
			
		if scc == value:
			if is_big(st, best_st):
				best_st=st
			continue
				
		for cost in kk_costs:
			tst=st[:]
			tst.append(max(ctv[cost]))
			ol.put((cc+cost, (cc+cost, tst)))
	return None
	
def is_big(base, other):
	if other is None:
		return True
	if base is None:
		return False
		
	if len(base) != len(other):
		return len(base) > len(other)
	return base > other


def mk_value(a_ll):
	if a_ll is None:
		return 0
		
	a_ll.sort(reverse=True)
	a_ll2=[str(v) for v in a_ll]
	ans=''.join(a_ll2)
	return ans
	
def main():
	n , _ = map(int, input().split())
	al = list(map(int, input().split())	)
	
	cost_list=[1000, 2,5,5,4,5,6,5,7,6]
	
	aal=[(v, cost_list[v]) for v in al]
	aal.sort(key=lambda x:-x[0])
	ctv={}
	for v in aal:
		ctv.setdefault(v[1], []).append(v[0])
	
	#for kk in ctv.keys():
	#	pa((kk,':',ctv[kk]))
	aal=list(ctv.keys())
	aal.sort()
	
	ccc = ggg(n, aal, ctv)
	ans=mk_value(ccc)
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import queue

#+++++

def sa(v, p):
	return v //p, v %p

def ggg(value, p_list, ctv):
	dd=p_list[:]
	#print('gfg',dd)
	if len(dd)==0:
		return None
	a=dd.pop(0)
	if a > value:
		return None
	
	m,p=sa(value, a)
	if p == 0:
		aa= [max(ctv[a])]*(m)
		return aa
	else:
		for i in range(m+1):
			nokori=p+i*a
			ret=bbb(nokori, ctv)
			if ret is not None:
				aa= [max(ctv[a])]*(m-i)
				return (ret + aa)
		return None

def bbb(value, ctv):
	ol=queue.PriorityQueue()
	kk_costs=ctv.keys()
	
	best_st=None
	
	cc=0
	st=[]
	ol.put((cc,(cc, st)))
	while not ol.empty():
		scc, (cc, st) = ol.get()
		#pa((scc,cc,st))
		if scc > value:
			return best_st
			
		if scc == value:
			if is_big(st, best_st):
				best_st=st
			continue
				
		for cost in kk_costs:
			tst=st[:]
			tst.append(max(ctv[cost]))
			ol.put((cc+cost, (cc+cost, tst)))
	return None
	
def is_big(base, other):
	if other is None:
		return True
	if base is None:
		return False
		
	if len(base) != len(other):
		return len(base) > len(other)
	return base > other


def mk_value(a_ll):
	if a_ll is None:
		return 0
		
	a_ll.sort(reverse=True)
	a_ll2=[str(v) for v in a_ll]
	ans=''.join(a_ll2)
	return ans
	
def main():
	n , _ = map(int, input().split())
	al = list(map(int, input().split())	)
	
	cost_list=[1000, 2,5,5,4,5,6,3,7,6]
	
	aal=[(v, cost_list[v]) for v in al]
	aal.sort(key=lambda x:-x[0])
	ctv={}
	for v in aal:
		ctv.setdefault(v[1], []).append(v[0])
	
	#for kk in ctv.keys():
	#	pa((kk,':',ctv[kk]))
	aal=list(ctv.keys())
	aal.sort()
	
	ccc = ggg(n, aal, ctv)
	ans=mk_value(ccc)
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

#+++++

def sa(v, p):
	return v //p, v %p

def ggg(value, p_list, ret_list):
	#pa(p_list)
	dd=p_list[:]
	#print('gfg',dd)
	if len(dd)==0:
		return None
	a=dd.pop(0)
	if a > value:
		return None
	
	m,p=sa(value, a)
	if p == 0:
		ret_list.append(m)
		return ret_list
	else:
		for i in range(m+1):
			nokori=p+i*a
			rre=ret_list[:]
			rre.append(m-i)
			#pa((rre,nokori,i,m,a))
			ret=ggg(nokori, dd, rre)
			if ret is not None:
				return ret
		return None
	
def main():
	n , _ = map(int, input().split())
	al = list(map(int, input().split())	)
	
	cost_list=[1000, 2,5,5,4,5,6,3,7,6]
	
	aal=[(v, cost_list[v]) for v in al]
	aal.sort(key=lambda x:-x[0])
	ctv={}
	for v in aal:
		ctv.setdefault(v[1], []).append(v[0])
	
	#for kk in ctv.keys():
	#	pa((kk,':',ctv[kk]))
	aal=list(ctv.keys())
	aal.sort()
	vv=[]
	ccc = ggg(n, aal, vv)
	rrr=[(num,cost,max(ctv[cost])) for num,cost in zip(ccc,aal)]
	rrr.sort(key=lambda x:-1*x[2])
	ans=''
	for num, cost,value in rrr:
		ans+=str(value)*num
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys

#+++++

def sa(v, p):
	return v //p, v %p

def ggg(value, p_list, ret_list):
	#pa(p_list)
	dd=p_list[:]
	#print('gfg',dd)
	if len(dd)==0:
		return None
	a=dd.pop(0)
	if a > value:
		return None
	
	m,p=sa(value, a)
	if p == 0:
		ret_list.append(m)
		return ret_list
	else:
		for i in range(m+1):
			nokori=p+i*a
			rre=ret_list[:]
			rre.append(m-i)
			#pa((rre,nokori,i,m,a))
			ret=ggg(nokori, dd, rre)
			if ret is not None:
				return ret
		return None
	
def main():
	n , _ = map(int, input().split())
	al = list(map(int, input().split())	)
	
	cost_list=[1000, 2,5,5,4,5,6,3,7,6]
	
	aal=[(v, cost_list[v]) for v in al]
	aal.sort(key=lambda x:-x[0])
	ctv={}
	for v in aal:
		ctv.setdefault(v[1], []).append(v[0])
	
	#for kk in ctv.keys():
	#	pa((kk,':',ctv[kk]))
	aal=list(ctv.keys())
	aal.sort()
	vv=[]
	ccc = ggg(n, aal, vv)
	rrr=[(num,cost,ctv[cost][0]) for num,cost in zip(ccc,aal)]
	rrr.sort(key=lambda x:-1*x[2])
	ans=''
	for num, cost,value in rrr:
		ans+=str(value)*num
	
	print(ans)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

MATCH = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
A = list(map(int, input(). split()))
A.sort(key = lambda x : MATCH[x])

key = A[0]
n = N//MATCH[key];
lst = [key]*n

ext = N-n*MATCH[key]

id = n

A.sort(reverse = True)

ans = []

def foo(lst, extr, id2, id3):
    for i in A:
        ext = extr
        id = id2
        idk = id3
        tmp = deepcopy(lst)
        if MATCH[i]-MATCH[key] > 0:
            j = ext//(MATCH[i]-MATCH[key])
            if j > 0:
                ext -= (MATCH[i]-MATCH[key])*j
                for k in range(j):
                    if key < i:
                        tmp.insert(id, i)
                        del tmp[idk]
                        id -= 1
                    else:
                        del tmp[idk]
                        tmp.insert(idk, i)
                        idk += 1
                if ext == 0:
                    ans.append(tmp)
                else:
                    foo(tmp, ext, id, idk);
foo(lst, ext, id, 0)

max = 0

for tmp in ans:
    val = 0
    tmp.reverse()
    for x in tmp:
        val *= 10
        val += x
    if max < val:
        max = val

print(max)

Submission status: Wrong Answer

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

dp = [-1] * (N+1)
weights = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
# 0本のマッチで作れる最大の整数は０
dp[0] = 0

for i in range(N+1):
    for a in A:
        if i + weights[a] > N:
            continue
        dp[i + weights[a]] = max(dp[i + weights[a]], dp[i] * 10 + weights[a])
print(dp[N])

Submission status: Wrong Answer

Solution code:
l = [[0,0],[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()))
l0 = []
for i in range(m):
    l0.append(l[a[i]])
l0.sort(key=lambda x:x[0],reverse=True)
l0.sort(key=lambda x:x[1])
p,q = l0[0]
count = n - (n//q)*q
c = 1
ans = 0
for i in range(n//q):
    ans += p*c
    c *= 10
c = c//10
l0.sort(key=lambda x:x[0],reverse=True)
i = 0
while count > 0 and i < m:
    p1,q1 = l0[i]
    if q1 > q:
        q1 -= q
    #print(count)
    if p1 > p:
        while count >= q1:
            ans -= p*c
            ans += p1*c
            count -= q1
            c = c//10
        i += 1
    else:
        i += 1
i = 0
c = 1
l0.sort(key=lambda x:x[1],reverse=True)
while count > 0 and i < m:
    p1,q1 = l0[i]
    if q1 > q:
        q1 -= q
    if p1 < p:
        while count >= q1:
            ans -= p*c
            ans += p1*c
            count -= q1
            c *= 10
        i += 1
    else:
        i += 1
print(ans)

Submission status: Wrong Answer

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

dic = {}
dic[1] = 2
dic[2] = 5
dic[3] = 5
dic[4] = 4
dic[5] = 5
dic[6] = 6
dic[7] = 3
dic[8] = 7
dic[9] = 6

ls = [-1]*8
dp = [-1]*(N+1)
dp[0] = 0
for i in a:
  j = dic[i]
  if ls[j]<i:
    ls[j] = i

tag = []
for i in range(len(ls)):
  if ls[i]!=-1:
    tag += [i]
for i in range(N+1):
  for j in tag:
    if i+j<=N:
      s = max(dp[i+j]*10+ls[j], dp[i+j])

print(dp[N])

Submission status: Wrong Answer

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

H = set(T[a-1] for a in A)
H = list(H)
H.sort()

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

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

ans = ''
j = N
for i in range(1,dp[-1]):
    for a in A:
        if dp[j-T[a-1]] == dp[j] - 1:
            ans += str(a)
            j -= T[a-1]
            break

for a in A:
    if j == T[a-1]:
        ans += str(a)
        j -= T[a-1]
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

#import fractions #fractions.gcd() python~3.4
sys.setrecursionlimit(1000000)

N, M = map(int,input().split())
A = list(map(int, input().split()))
A.sort()
B=[-1]*8
for i in range(M):
    if A[i] == 1:
        B[2] = A[i]
    if A[i] == 2:
        B[5] = A[i]
    if A[i] == 3:
        B[5] = A[i]
    if A[i] == 4:
        B[4] = A[i]
    if A[i] == 5:
        B[5] = A[i]
    if A[i] == 6:
        B[6] = A[i]
    if A[i] == 7:
        B[3] = A[i]
    if A[i] == 8:
        B[7] = A[i]
    if A[i] == 9:
        B[6] = A[i]
num = []
for i in range(8):
    if B[i] > 0:
        num.append(i)

num_num = []
def dfs(r, stair):
    if stair == len(num):
        return False
    
    for a in reversed(range(r//num[stair]+1)):
        r2 = r-num[stair]*a
        num_num.append(a)
        if r2 == 0:
            return True
        Flag = dfs(r2, stair+1)
        if Flag:
            return True
        num_num.pop()

dfs(N, 0)


ans = []
for i in range(len(num_num)):
    for j in range(num_num[i]):
        ans.append(str(B[num[i]]))
ans.sort(reverse=True)
print("".join(ans))

Submission status: Wrong Answer

Solution code:
def main():
    import heapq
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    C = [1,7,4,5,3,2,9,6,8]
    D = [2,3,4,5,5,5,6,6,7]
    E = []
    F = []
    
    for i in range(len(C)):
        if (C[i] in A) and (not D[i] in F):
            E.append(C[i])
            F.append(D[i])
    E = E[::-1]
    F = F[::-1]
    G = [0] * len(E)
    X = []
    flag = 0

    heapq.heappush(X,[0,0,G])
    
    while flag == 0:
        tmp = heapq.heappop(X)
        if tmp[1] == N:
            Ans = deepcopy(tmp[2])
            flag = 1
        for i in range(len(G)):
            if tmp[1] + F[i] <= N:
                p = deepcopy(tmp[2])
                p[i] += 1
                heapq.heappush(X,[tmp[0]-1, tmp[1] + F[i], p])
    H = []
    for i in range(len(G)):
        H.append([E[i],Ans[i]])
    H = sorted(H)
    H = H[::-1]
    ans = ""
    for i in range(len(G)):
        ans += str(H[i][0])*H[i][1]
    print(int(ans))
    
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    import heapq
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    C = [1,7,4,5,3,2,9,6,8]
    D = [2,3,4,5,5,5,6,6,7]
    E = []
    F = []
    
    for i in range(len(C)):
        if (C[i] in A) and (not D[i] in F):
            E.append(C[i])
            F.append(D[i])
    E = E[::-1]
    F = F[::-1]
    G = [0] * len(E)
    X = []
    flag = 0

    heapq.heappush(X,[0,G,0])
    
    while flag == 0:
        tmp = heapq.heappop(X)
        if tmp[2] == -N:
            Ans = deepcopy(tmp[1])
            flag = 1
        for i in range(len(G)):
            if tmp[2] - F[i] >= -N:
                p = deepcopy(tmp[1])
                p[i] += 1
                heapq.heappush(X,[tmp[0]-1, p, tmp[2] - F[i]])
    H = []
    for i in range(len(G)):
        H.append([E[i],Ans[i]])
    H = sorted(H)
    H = H[::-1]
    ans = ""
    for i in range(len(G)):
        ans += str(H[i][0])*H[i][1]
    print(int(ans))
    
    
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    import heapq
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    C = [1,7,4,5,3,2,9,6,8]
    D = [2,3,4,5,5,5,6,6,7]
    E = []
    F = []
    
    for i in range(len(C)):
        if (C[i] in A) and (not D[i] in F):
            E.append(C[i])
            F.append(D[i])
    E = E[::-1]
    F = F[::-1]
    G = [0] * len(E)
    X = []
    flag = 0
    opt = 0
    heapq.heappush(X,[-sum(G),G,0])
    while flag == 0:
        tmp = heapq.heappop(X)
        if tmp[2] == -N:
            Ans = deepcopy(tmp[1])
            flag = 1
        for i in range(len(G)):
            if tmp[2] - F[i] >= -N:
                p = deepcopy(tmp[1])
                p[i] += 1
                heapq.heappush(X,[tmp[0]-1, p, tmp[2] - F[i]])
    H = []
    for i in range(len(G)):
        H.append([E[i],Ans[i]])
    H = sorted(H)
    H = H[::-1]
    ans = ""
    for i in range(len(G)):
        ans += str(H[i][0])*H[i][1]
    print(int(ans))
    
    
    
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
A = list(map(int, input().split()))
num_use_dic = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
usable = defaultdict(int)  # key: 使う本数, value: 整数
ans = []

for num in A:
    use = num_use_dic[num]
    if usable[use] < num:  # 使用本数が同じなら大きい数字のみ使えば良い
        usable[use] = num




def dfs(candidate, count):
    global ans
    if ans:
        return
    if count < 0:
        return
    if count == 0:
        ans = list(map(int, list(candidate)))
        return

    for use, num in sorted(usable.items()):
        dfs(candidate+str(num), count-use)


dfs('', n)
ans.sort(reverse=True)
print(''.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    d1 = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
    d2 = dict()
    for a in A:
        if d1[a] not in d2: d2[d1[a]] = a
        else: d2[d1[a]] = max(a, d2[d1[a]])
    d3 = dict()
    for a in d2.values():
        d3[a] = d1[a]

    # print(d3)
    min_d = min(d2.keys())
    min_a = d2[min_d]
    i = N // min_d
    j = N % min_d
    s = str(d2[min_d])*i
    t = ""
    for k in range(len(s)):
        for a in sorted(d3.keys(), reverse = True):
            if d1[a] - min_d <= j:
                t += str(a)
                j -= d1[a] - min_d
                break
    if j == 0: return t

    B = [[d3[a], a] for a in d3 if d3[a] > min_d]
    B = sorted(B, key = lambda x: x[0], reverse = True)
    cand = [["", j]]
    for k in range(j):
        c = int(t[len(t)-1-k])
        temp = []
        for u, j1 in cand:
            if j1 == 0:
                return t[:-k] + u[::-1]
            for v, a in B:
                if v - d3[c] > 0:
                    temp.append([u + str(a), j1-v+d3[c]])
        cand += temp

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

dp = [0]*(n+1)

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

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

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

minm = min(match[a] for a in aa)
keta = n//minm

if m == 1 :
    print(str(aa[0])*keta)
elif m == 2 :
    ans_best = 0
    for a0, a1 in permutations(aa, 2) :
        m0, m1 = match[a0], match[a1]
        for i in range(min(6, keta)) :
            ans = int(str(a0)*i+str(a1)*(keta-i))
            if m0*i+m1*(keta-i)==n : ans_best = max(ans_best, ans)
            ans = int(str(a0)*(keta-i)+str(a1)*i)
            if m0*(keta-i)+m1*i==n : ans_best = max(ans_best, ans)
    print(ans_best)
else :
    ans_best = 0
    for a0, a1, a2 in permutations(aa, 3) :
        m0, m1, m2 = match[a0], match[a1], match[a2]
        for i in range(min(6, keta)) :
            for j in range(min(6, keta)-i) :
                ans = int(str(a0)*i+str(a1)*j+str(a2)*(keta-i-j))
                if m0*i+m1*j+m2*(keta-i-j)==n : ans_best = max(ans_best, ans)
                ans = int(str(a0)*i+str(a1)*(keta-i-j)+str(a2)*j)
                if m0*i+m1*(keta-i-j)+m2*j==n : ans_best = max(ans_best, ans)
                ans = int(str(a0)*(keta-i-j)+str(a1)*i+str(a2)*j)
                if m0*(keta-i-j)+m1*i+m2*j==n : ans_best = max(ans_best, ans)
    print(ans_best)

Submission status: Wrong Answer

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

number = [0]*9
for i in range(9):
    for j in range(m):
        if a[j] == i+1:
            number[i] += 1

can_use = []
if number[0] > 0:
    can_use.append(2)

if number[6] > 0:
    can_use.append(3)

if number[3] > 0:
    can_use.append(4)

if number[1] + number[2] + number[4] > 0:
    can_use.append(5)

if number[5] + number[8] > 0:
    can_use.append(6)

if number[7] > 0:
    can_use.append(7)

digit = list(list(0 for _ in range(6)) for _ in range(n+1))
digit_num = list(0 for _ in range(n+1))
for i in range(1,n+1):
    for j in can_use:
        if i - j >= 0:
            if digit_num[i-j] == 0 and i != j:
                continue
            elif digit_num[i-j] + 1 + digit[i-j][4]*10**(-3) + digit[i-j][5]*10**(-6) + digit[i-j][1]*10**(-9) + digit[i-j][3]*10**(-12) + digit[i-j][2]*10**(-15) + digit[i-j][2]*10**(-18) > digit_num[i] + digit[i][4]*10**(-3) + digit[i][5]*10**(-6) + digit[i][1]*10**(-9) + digit[i][3]*10**(-12) + digit[i][2]*10**(-15) + digit[i][2]*10**(-18):
                digit_num[i] = digit_num[i-j] + 1
                for k in range(6):
                    digit[i][k] = digit[i-j][k]
                digit[i][j-2] += 1
        else:
            continue


can_use_digit = [0]*9
can_use_digit[0] = digit[n][0]
can_use_digit[6] = digit[n][1]
can_use_digit[3] = digit[n][2]
if number[1] + number[2] + number[4] > 0:
    can_use_digit[max(number[1]*1,number[2]*2,number[4]*4)] = digit[n][3]

if number[5] + number[8] > 0:
    can_use_digit[max(number[5]*5,number[8]*8)] = digit[n][4]

can_use_digit[7] = digit[n][5]
answer = 0
for i in range(8,-1,-1):
    for j in range(can_use_digit[i]):
        answer *= 10
        answer += i+1

print(answer)