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:
cost_digit = { 2: [1], 3:[7], 4:[4], 5: [2,3,5], 6: [6,9], 7: [8]}
digit_cost = [2,5,5,4,5,6,3,7,6]

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

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

cost = set([digit_cost[x-1] for x in materials])

minpart = set()
for c in cost:
    if c == 2 or c == 3:
        minpart.add(c)
    elif c == 4:
        if 2 not in minpart:
            minpart.add(4)
    elif c == 5:
        if 2 not in minpart or 3 not in minpart:
            minpart.add(5)
    elif c == 6:
        if 2 not in minpart and 3 not in minpart:
            minpart.add(6)
    else: # c== 7
        if 2 not in minpart or 3 not in minpart:
            if 3 not in minpart or 4 not in minpart:
                if 2 not in minpart or 5 not in minpart:
                    minpart.add(7)


usedigit = []
result = {}

for part in minpart:
    result[part] = {part : 1}
    usedigit.append(max(set(cost_digit[part]) & set(materials)))

usedigit.sort(reverse=True)


for target in range(max(minpart)+1, n+1):

    for part in minpart:

        curtarget = target - part
        if curtarget in result:
            d = result[curtarget].copy()
            if part in d:
                d[part] += 1
            else:
                d[part] = 1

            result[target] = d
            break

ans = ''
res = result[n]

for d in usedigit:
    if digit_cost[d-1] in res:
        ans += ''.join([str(d) for _ in range(res[digit_cost[d-1]])])
    
print(ans)

Submission status: Wrong Answer

Solution code:
cost_digit = { 2: [1], 3:[7], 4:[4], 5: [2,3,5], 6: [6,9], 7: [8]}
digit_cost = [2,5,5,4,5,6,3,7,6]

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

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

cost = set([digit_cost[x-1] for x in materials])

minpart = set()
for c in cost:
    if c == 2 or c == 3:
        minpart.add(c)
    elif c == 4:
        if 2 not in minpart:
            minpart.add(4)
    elif c == 5:
        if 2 not in minpart or 3 not in minpart:
            minpart.add(5)
    elif c == 6:
        if 2 not in minpart and 3 not in minpart:
            minpart.add(6)
    else: # c== 7
        if 2 not in minpart or 3 not in minpart:
            if 3 not in minpart or 4 not in minpart:
                if 2 not in minpart or 5 not in minpart:
                    minpart.add(7)


usedigit = []
result = {}

for part in minpart:
    result[part] = {part : 1}
    usedigit.append(max(set(cost_digit[part]) & set(materials)))

usedigit.sort(reverse=True)


for target in range(max(minpart)+1, n+1):

    for part in minpart:

        curtarget = target - part
        if curtarget in result:
            d = result[curtarget].copy()
            if part in d:
                d[part] += 1
            else:
                d[part] = 1

            result[target] = d
            break

ans = ''
res = result[n]

for d in usedigit:
    if digit_cost[d-1] in res:
        ans += ''.join([str(d) for _ in range(res[digit_cost[d-1]])])
    
print(ans)

Submission status: Wrong Answer

Solution code:
cost_digit = { 2: [1], 3:[7], 4:[4], 5: [2,3,5], 6: [6,9], 7: [8]}
digit_cost = [2,5,5,4,5,6,3,7,6]

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

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

cost = set([digit_cost[x-1] for x in materials])

minpart = set()
for c in cost:
    if c == 2 or c == 3:
        minpart.add(c)
    elif c == 4:
        if 2 not in minpart:
            minpart.add(4)
    elif c == 5:
        if 2 not in minpart or 3 not in minpart:
            minpart.add(5)
    elif c == 6:
        if 2 not in minpart and 3 not in minpart:
            minpart.add(6)
    else: # c== 7
        if 2 not in minpart or 3 not in minpart:
            if 3 not in minpart or 4 not in minpart:
                if 2 not in minpart or 5 not in minpart:
                    minpart.add(7)


usedigit = []
result = {}

for part in minpart:
    result[part] = {part : 1}
    usedigit.append(max(set(cost_digit[part]) & set(materials)))

usedigit.sort(reverse=True)


for target in range(max(minpart)+1, n+1):

    for part in minpart:

        curtarget = target - part
        if curtarget in result:
            d = result[curtarget]
            if part in d:
                d[part] += 1
            else:
                d[part] = 1

            result[target] = d
            break

ans = ''
res = result[n]

for d in usedigit:
    if digit_cost[d-1] in res:
        ans += ''.join([str(d) for _ in range(res[digit_cost[d-1]])])
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

INF = 1000000000000000000


define = np.array([0,2,5,5,4,5,6,3,7,6])
N,M = map(int,input().split())
tA = list(map(int,input().split()))
dp = [-INF] * (N+1)
dp[0] = 0

A = define[tA]

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

dict = {}
for i,v in zip(A,tA):
    dict[i] = v
    
dict = sorted(dict.items(), key=lambda x: -x[1])
ans = ''

tmpN = N

while tmpN > 0:
    for (ma, num) in dict:
        if tmpN - ma < 0:
            continue
        if dp[tmpN] == dp[tmpN-ma] + 1:
            ans += str(num)
            tmpN -= ma
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy

d=[0,2,5,5,4,5,6,3,7,6]
b=[]

n = map(int, raw_input().split())
a = map(int, raw_input().split())

for x in a:
    b.append(d[x])

def max_num(x, a, b):
    results=[]
    max=0
    for z, y in enumerate(b):
        if x==y:
            results.append([a[z], [a[z]]])
        elif x>y:
            if max_num(x-y, a, b)!=None:
                t=0
                result=max_num(x-y, a, b)
                result[1].append(a[z])
                result[1].sort()
                for num, res in enumerate(result[1]):
                    t+=res*(10**num)
                results.append([t, result[1]])
            else:
                continue
    if results==[]:
        return
    results.sort()
    results.reverse()
    return results[0][0], results[0][1]

def final(x, a, b):
    results=[]
    minimum=a[b.index(min(b))]
    m=1
    t=0
    max=0
    if x%min(b)==0:
        for y in range(x/min(b)):
            results.append(minimum)
        for num, res in enumerate(results):
            t+=res*(10**num)
        return t
    elif x>min(b):
        b_org=copy.deepcopy(b)
        a.pop(b.index(min(b)))
        b.pop(b.index(min(b)))
        while max_num(x%min(b_org)+m*min(b_org), a, b)==None:
            print(x%min(b_org)+m*min(b_org))
            m+=1
            print(m)
        for i in range(4):
            t=0
            result = max_num(x%min(b_org)+(m+i)*min(b_org), a, b)
            results=result[1]
            for y in range(x/min(b_org)-m-i):
                results.append(minimum)
            results.sort()
            for num, res in enumerate(results):
                t+=res*(10**num)
            if t>max:
                max=t
            return max
    if results==[]:
        return


print(final(n[0], a, b))

Submission status: Wrong Answer

Solution code:
import sys
import copy

d=[0,2,5,5,4,5,6,3,7,6]
b=[]

n = map(int, raw_input().split())
a = map(int, raw_input().split())

for x in a:
    b.append(d[x])

def max_num(x, a, b):
    results=[]
    max=0
    for z, y in enumerate(b):
        if x==y:
            results.append([a[z], [a[z]]])
        elif x>y:
            if max_num(x-y, a, b)!=None:
                t=0
                result=max_num(x-y, a, b)
                result[1].append(a[z])
                result[1].sort()
                for num, res in enumerate(result[1]):
                    t+=res*(10**num)
                results.append([t, result[1]])
            else:
                continue
    if results==[]:
        return
    results.sort()
    results.reverse()
    return results[0][0], results[0][1]

def final(x, a, b):
    results=[]
    minimum=a[b.index(min(b))]
    m=1
    t=0
    max=0
    if x%min(b)==0:
        for y in range(x/min(b)):
            results.append(minimum)
        for num, res in enumerate(results):
            t+=res*(10**num)
        return t
    elif x>min(b):
        b_org=copy.deepcopy(b)
        a.pop(b.index(min(b)))
        b.pop(b.index(min(b)))
        while max_num(x%min(b_org)+m*min(b_org), a, b)==None:
            print(x%min(b_org)+m*min(b_org))
            m+=1
            print(m)
        for i in range(4):
            t=0
            result = max_num(x%min(b_org)+(m+i)*min(b_org), a, b)
            results=result[1]
            for y in range(x/min(b_org)-m):
                results.append(minimum)
            results.sort()
            for num, res in enumerate(results):
                t+=res*(10**num)
            if t>max:
                max=t
            return max
    if results==[]:
        return


print(final(n[0], a, b))

Submission status: Wrong Answer

Solution code:
import sys
import copy

d=[0,2,5,5,4,5,6,3,7,6]
b=[]

n = map(int, raw_input().split())
a = map(int, raw_input().split())

for x in a:
    b.append(d[x])

def max_num(x, a, b):
    results=[]
    max=0
    for z, y in enumerate(b):
        if x==y:
            results.append([a[z], [a[z]]])
        elif x>y:
            if max_num(x-y, a, b)!=None:
                t=0
                result=max_num(x-y, a, b)
                result[1].append(a[z])
                result[1].sort()
                for num, res in enumerate(result[1]):
                    t+=res*(10**num)
                results.append([t, result[1]])
            else:
                continue
    if results==[]:
        return
    results.sort()
    results.reverse()
    return results[0][0], results[0][1]

def final(x, a, b):
    results=[]
    minimum=a[b.index(min(b))]
    m=1
    t=0
    if x%min(b)==0:
        for y in range(x/min(b)):
            results.append(minimum)
    elif x>min(b):
        b_org=copy.deepcopy(b)
        a.pop(b.index(min(b)))
        b.pop(b.index(min(b)))
        while max_num(x%min(b_org)+m*min(b_org), a, b)==None:
            print(x%min(b_org)+m*min(b_org))
            m+=1
            print(m)
        result = max_num(x%min(b_org)+m*min(b_org), a, b)
        results=result[1]
        for y in range(x/min(b_org)-m):
            results.append(minimum)
    if results==[]:
        return
    results.sort()
    for num, res in enumerate(results):
       t+=res*(10**num)
    return t



print(final(n[0], a, b))

Submission status: Wrong Answer

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

def dfs(res, r, num, al):
    if r<2:
        return -1

    t = [-1]
    for i in range(1,10):
        if i in al:
            if num[i]<=r:
                if r-num[i]>0:
                    t.append(dfs(10*res+i, r-num[i], num, al))
                else:
                    t.append(10*res+i)
    return max(t)

def f(n,al):
    num = [0,2,5,5,4,5,6,3,7,6]
    #      0,1,2,3,4,5,6,7,8,9
    al.sort(key=lambda x:num[x])
    return str(dfs(0,n,num,al))

def f2(n, al):
    num = [0,2,5,5,4,5,6,3,7,6]
    #      0,1,2,3,4,5,6,7,8,9
    al.sort(reverse=True)
    al.sort(key=lambda x:num[x])
    res = 0
    while n>20:
        res = 10*res + al[0]
        n -= num[al[0]]

    res = dfs(res,n,num,al)
    if res<0:
        return "-1"
    res = list(str(res))
    res.sort(reverse=True)
    return "".join(map(str,res))

if __name__ == '__main__':
    n,m = map(int, input().split())
    al = list(map(int, input().split()))
    print(f2(n,al))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
al = list(map(int, input().split()))

num = [0,2,5,5,4,5,6,3,7,6]
#      0,1,2,3,4,5,6,7,8,9
al.sort(key=lambda x:num[x])

def dfs(res, r):
    if r<2:
        return -1

    t = [-1]
    for i in range(1,10):
        if i in al:
            if num[i]<=r:
                if r-num[i]>0:
                    t.append(dfs(10*res+i, r-num[i]))
                else:
                    t.append(10*res+i)
    return max(t)

res = 0
while n>20:
    res = 10*res + al[0]
    n -= num[al[0]]

res = dfs(res,n)
res = list(str(res))
res.sort(reverse=True)
print("".join(map(str,res)))

Submission status: Wrong Answer

Solution code:
#わからんテスト
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

dp = [[0 for j in range(10)] for i in range(N)]

Submission status: Wrong Answer

Solution code:
#わからんテスト
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
mt=[0,2,5,5,4,5,6,3,7,6]
a=sorted(map(int, input().split()))
dp=['']*(n+1)
dp[0]='*'
for i in range(n+1):
    if not dp[i]:continue
    for j in a:
        if i+mt[j]<n+1:
            dp[i+mt[j]]=dp[i]+str(j)
print(dp[-1][1:])

Submission status: Wrong Answer

Solution code:
B_arr = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

A_arr.sort(reverse=True)
tmp_arr = []
A_arr_2 = []
for A in A_arr:
    if not B_arr[A] in tmp_arr:
        A_arr_2.append(A)
        tmp_arr.append(B_arr[A])
A_arr_2.sort(key=lambda x:B_arr[x])
A_arr = A_arr_2

def inner(m, p_arr):
    ans = []
    p_top = B_arr[p_arr[0]]
    p_top_max = m//p_top
    if m % p_top == 0:
        ans.append([p_arr[0]]*(p_top_max))
        return ans
    if len(p_arr) == 1:
        return []
    n = 0
    ml = m - p_top*p_top_max
    max_len = 0
    while True:
        sub_arr = inner(ml, p_arr[1:])
        for sub in sub_arr:
            ans.append([p_arr[0]]*(p_top_max-n)+sub)
            max_len = max(max_len, p_top_max-n+len(sub))
        ml += p_top
        n += 1
        if ml > m:
            break
        if ml//p_arr[1]+1+p_top_max-n < max_len:
            break
    return ans

results = inner(N, A_arr)
results.sort(key=lambda x:len(x), reverse=True)

result = results[0]
result.sort(reverse=True)
for r in result:
    print(r, end="")
print()

Submission status: Wrong Answer

Solution code:
B_arr = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

A_arr.sort(reverse=True)
tmp_arr = []
A_arr_2 = []
for A in A_arr:
    if not B_arr[A] in tmp_arr:
        A_arr_2.append(A)
        tmp_arr.append(B_arr[A])
A_arr_2.sort(key=lambda x:B_arr[x])
A_arr = A_arr_2

def inner(m, p_arr):
    p_top = B_arr[p_arr[0]]
    p_top_max = m//p_top
    if m % p_top == 0:
        return [p_arr[0]]*(p_top_max)
    if len(p_arr) == 1:
        return None
    n = 0
    ml = m - p_top*p_top_max
    while True:
        sub = inner(ml, p_arr[1:])
        if sub != None:
            return [p_arr[0]]*(p_top_max-n)+sub
        ml += p_top
        n += 1
        if ml > m:
            return None

result = inner(N, A_arr)

result.sort(reverse=True)
for r in result:
    print(r, end="")
print()

Submission status: Wrong Answer

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

A.sort(reverse=1)
seg=[]
for i in range(m):
    seg.append(seg0[A[i]])

#print(seg)

keta=[0 for i in range(n+1)]
for i in range(1,n+1):
    for j in range(m):
        if i-seg[j]>=0 :
            keta[i]=max(keta[i],keta[i-seg[j]]+1)

#print(keta)

ke=keta[n]

#print(ke)
#print(seg)
ans=0
while ke>1 :
    for j in range(m):
        #print(n-seg[j])
        #print(keta[n-seg[j]])
        if n-seg[j]>0 and keta[n]==keta[n-seg[j]]+1 :
            ans+=A[j]*10**(ke-1)
            n-=seg[j]
            #print(ans)
            break
    ke-=1

#print(n)
for i in range(m):
    #print(keta[n])
    if n==seg[i] :
        ans+=A[i]
        break

print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=1)
seg=[]
for i in range(m):
    seg.append(seg0[A[i]])

#print(seg)

keta=[0 for i in range(n+1)]
for i in range(1,n+1):
    for j in range(m):
        if i-seg[j]>=0 :
            keta[i]=max(keta[i],keta[i-seg[j]]+1)

#print(keta)

ke=keta[n]

#print(ke)
#print(seg)
ans=0
while ke>1 :
    for j in range(m):
        #print(n-seg[j])
        #print(keta[n-seg[j]])
        if n-seg[j]>0 and keta[n]==keta[n-seg[j]]+1 :
            ans+=A[j]*10**(ke-1)
            n-=seg[j]
            #print(ans)
            break
    ke-=1

#print(n)
for i in range(m):
    #print(keta[n])
    if n==seg[i] :
        ans+=A[i]

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(elem) for elem in input().split()]
a = [elem for elem in input().split()]
a.sort()

num_dict = {"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6}
dp = ["" for _ in range(n+1)]

for i in range(n+1):
    for strnum in a:
        if i - num_dict[strnum] < 0:
            continue
        if i - num_dict[strnum] == 0 and dp[i] == "":
            dp[i] = strnum
        pre_strnum = dp[i - num_dict[strnum]]
        if pre_strnum != "":
            if len(pre_strnum) + 1 > len(dp[i]):
                dp[i] = pre_strnum + strnum

print("".join(sorted(dp[n], reverse=True)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0,2,5,5,4,5,6,3,7,6]
D=[]
for a in A:
	for aa in A:
		if B[a]==B[aa] and a!=aa:
			d=min(a,aa)
			if d not in D:
				D.append(d)
		if B[a]%B[aa]==0 and a!=aa and B[a]!=B[aa]: #B[a]>B[aa]
			if a not in D:
				D.append(a)

#print(D)
for d in D:
	A.remove(d)
for i in range(len(A)):
	for ii in range(i):
		if B[A[i]]<B[A[ii]]:
			A[i],A[ii]=A[ii],A[i]
#print(A)
C=[None for _ in range(N+1)]
C[0]=''
def DP(n):
	global C
	R=[-1 for _ in range(10)]
	for a in A:
		if n-B[a]<0:
			break
		if C[n-B[a]]==None:
			DP(n-B[a])
		R[a]=int(str(a)+C[n-B[a]])
	r=str(max(set(R)))
	if r=='-1':
		C[n]=''
	else:
		C[n]=r
DP(N)
print(C[N])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0,2,5,5,4,5,6,3,7,6]
D=[]
for a in A:
	for aa in A:
		if B[a]==B[aa] and a!=aa:
			d=min(a,aa)
			if d not in D:
				D.append(d)
		if B[a]%B[aa]==0 and a!=aa and B[a]!=B[aa]: #B[a]>B[aa]
			if a not in D:
				D.append(a)

#print(D)
for d in D:
	A.remove(d)
for i in range(len(A)):
	for ii in range(i):
		if B[A[i]]<B[A[ii]]:
			A[i],A[ii]=A[ii],A[i]
print(A)
C=[None for _ in range(N+1)]
C[0]=''
def DP(n):
	global C
	#print(n)
	#print(C)
	if C[n] != None:
		return C[n]
	else:
		R=[-1 for _ in range(10)]
		for a in A:
			if n-B[a] <0:
				break
			if C[n-B[a]]==None:
				DP(n-B[a])
			if C[n-B[a]]!='-1':
				R[a]=int(str(a)+C[n-B[a]])
		#print(R)
		r=str(max(R))
		C[n]=r
		return r
print(DP(N))
#print(C)

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
mt=[0,2,5,5,4,5,6,3,7,6]
a=sorted(map(int, input().split()))
dp=['']*(n+1)
dp[0]='*'
for i in range(n+1):
    if not dp[i]:continue
    for j in a:
        if i+mt[j]<n+1:
            dp[i+mt[j]]=str(j)+dp[i]
print(''.join(sorted(dp[-1][:-1])[::-1]))

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
mt=[0,2,5,5,4,5,6,3,7,6]
a=sorted(map(int, input().split()))
dp=['']*(n+1)
dp[0]='*'
for i in range(n+1):
    if not dp[i]:continue
    for j in a:
        if i+mt[j]<n+1:
            dp[i+mt[j]]=str(j)+dp[i]
print(*sorted(dp[-1][:-1])[::-1],sep='')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
mat = []
for i in range(m):
    mat.append((match[a[i]-1], a[i]))

d = defaultdict(int)
for ma, num in mat:
    d[ma] = max(d[ma], num)


memo = [0] * (n + 10)



# dp[i]: マッチをi本使ってできる整数のケタの最大値
INF = float('inf')
dp = [-INF] * (n+10)
dp[0] = 0

for i in range(n):
    if dp[i] == -INF:
        continue
    for ma, num in mat:
        if dp[i] + 1 > dp[i+ma]:
            dp[i+ma] = dp[i] + 1
            memo[i+ma] = ma

res = []
i = n
while i > 0:
    res.append(d[memo[i]])
    i -= memo[i]

res.sort(reverse=True)

ans = ""
for i in res:
    ans += str(i)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
mat = []
for i in range(m):
    mat.append((match[a[i]-1], a[i]))

d = defaultdict(int)
for ma, num in mat:
    d[ma] = max(d[ma], num)


memo = [0] * (n + 10)



# dp[i]: マッチをi本使ってできる整数のケタの最大値
INF = float('inf')
dp = [-INF] * (n+10)
dp[0] = 0

for i in range(n):
    for ma, num in mat:
        if dp[i] + 1 > dp[i+ma]:
            dp[i+ma] = dp[i] + 1
            memo[i+ma] = ma

res = []
i = n
while i > 0:
    res.append(d[memo[i]])
    i -= memo[i]

res.sort(reverse=True)

ans = ""
for i in res:
    ans += str(i)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
mat = []
for i in range(m):
    mat.append((match[a[i]-1], a[i]))

d = defaultdict(int)
for ma, num in mat:
    d[ma] = max(d[ma], num)

memo = [0] * (n + 10)


# dp[i]: マッチをi本使ってできる整数のケタの最大値
dp = [0] * (n+10)

for i in range(n):
    for ma, num in mat:
        if dp[i] + 1 > dp[i+ma]:
            dp[i+ma] = dp[i] + 1
            memo[i+ma] = ma

res = []
i = n
while i > 0:
    res.append(d[memo[i]])
    i -= memo[i]

res.sort(reverse=True)

ans = ""
for i in res:
    ans += str(i)

print(ans)

Submission status: Wrong Answer

Solution code:
def greater(a,b):
    if a==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

c=[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=[c[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:
        for j in range(m):
            k=max[i]+sa[j] if max[i][0]>sa[j] else sa[j]+max[i]
            max[i+ca[j]]=greater(max[i+ca[j]],k)
print(max[n])

Submission status: Wrong Answer

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[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 ** int(math.log10(dp[i - val]) + 1)) + dp[i - val]
				dp[i] = max(dp[i], tmp)
			elif i >= val and dp[i - val] == 0:
				tmp = match2num[val]
				dp[i] = max(dp[i], tmp)
	
	#print(num2match)
	#print(match2num)
	#print(dp)
	#print(dp)
	print(int(dp[n]))
	#print(cnt)
 
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
list = list(map(int,input().split()))
uses = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dict = {}
for i in sorted(list):
    dict[uses[i]] = i
dlist = sorted(dict.items(), key=lambda x: x[0])
result = []

def bfs(index, mat):
    if index >= len(dlist):
        return False
    if mat % dlist[index][0] == 0:
        result.append([dlist[index][1], mat // dlist[index][0]])
        return True
    if mat < dlist[index][0]:
        return False
    for i in range(mat//dlist[index][0],-1,-1):
        if bfs(index + 1, mat - (dlist[index][0] * i)):
            result.append([dlist[index][1], i])
            return True
    return False

bfs(0,n)
result.sort(reverse=True)

for re in result:
    print(str(re[0]) * re[1],end="")

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
list = list(map(int,input().split()))
uses = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dict = {}
for i in list:
    dict[uses[i]] = i
dlist = sorted(dict.items(), key=lambda x: x[0])
result = []

def bfs(index, mat):
    if index >= len(dlist):
        return False
    if mat % dlist[index][0] == 0:
        result.append([dlist[index][1], mat // dlist[index][0]])
        return True
    if mat < dlist[index][0]:
        return False
    for i in range(mat//dlist[index][0],-1,-1):
        if bfs(index + 1, mat - (dlist[index][0] * i)):
            result.append([dlist[index][1], i])
            return True
    return False

bfs(0,n)
result.sort(reverse=True)

for re in result:
    print(str(re[0]) * re[1],end="")

Submission status: Wrong Answer

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: Wrong Answer

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

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

Submission status: Wrong Answer

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] 
# i 本のマッチで作れる最高の桁数
for i in range(1,N+1):
  for b in aval:
    if i < b:
      continue
    else:
      dp += [dp[i-b] + 1]
      break
  else:
    dp += [-1]

#作れる桁数は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: Wrong Answer

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] 
# i 本のマッチで作れる最高の桁数
for i in range(1,N+1):
  for b in aval:
    if i <= b:
      continue
    else:
      dp += [dp[i-b] + 1]
      break
  else:
    dp += [0]

#作れる桁数は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: Wrong Answer

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] 
# i 本のマッチで作れる最高の桁数
for i in range(1,N+1):
  for b in aval:
    if i < b:
      continue
    else:
      dp += [dp[i-b] + 1]
      break
  else:
    dp += [0]

#作れる桁数は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
    break
ans += [final]
print(''.join(map(str, ans)))

Submission status: Wrong Answer

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] 
# i 本のマッチで作れる最高の桁数
for i in range(1,N+1):
  for b in aval:
    if i < b:
      continue
    else:
      dp += [dp[i-b] + 1]
      break
  else:
    dp += [0]

#作れる桁数は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: Wrong Answer

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,0] 
# i 本のマッチで作れる最高の桁数
for i in range(2,N+1):
  for b in aval:
    if i < b:
      continue
    else:
      dp += [dp[i-b] + 1]
      break
  else:
    dp += [0]

#作れる桁数は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)))