Problem: 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.

Submission attempts (in order):
N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])

if [5,5] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:    
        B.remove([3,5])

if [3,5] in B and [2,5] in B:
    B.remove([2,5])

if [7,3] in B:
    if [6,6] in B:
        B.remove([6,6])
    if [9,6] in B:
        B.remove([9,6])
    
if [9,6] in B and [6,6] in B:
    B.remove([6,6])

if [1,2] in B and [7,3] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:
        B.remove([3,5])
    if [5,5] in B:
        B.remove([5,5])
    if [8,7] in B:
        B.remove([8,7])

if [1,2] in B and ([2,5] in B or [3,5] in B or [5,5] in B) and [8,7] in B:
    B.remove([8,7])
    
if [4,4] in B and [7,3] and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])

maxlist=[""]*(N+10)
 
for i in range(N+1):
    if i!=0 and maxlist[i]=="":
        continue
    else:
        for b in B:
            ans=maxlist[i]+str(b[0])
            _max=maxlist[i+b[1]]
            if i+b[1]>N:
                continue
            if len(ans)<len(_max):
                continue
            elif len(ans)>len(_max):
                maxlist[i+b[1]] = ans
            else:
                for j in range(len(ans)):
                    if ans[j]>_max[j]:
                        maxlist[i+b[1]] = ans
 
print(maxlist[N])

def concat(a,b):
	return int(str(a)+str(b))


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

m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]

for a in A:
	B.append(m[a-1])

print(B)
maxlist=[0]*(N+10)

for i in range(N+1):
	if i!=0 and maxlist[i]==0:
		continue
	else:
		for b in B:
			if concat(maxlist[i],b[0]) > maxlist[i+b[1]]:
				maxlist[i+b[1]] = concat(maxlist[i],b[0])

print(maxlist[N])

N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
 
for a in A:
    B.append(m[a-1])
    
maxlist=[0]*(N+10)
 
for i in range(N+1):
    if i!=0 and maxlist[i]==0:
        continue
    else:
        for b in B:
            if int(str(maxlist[i])+str(b[0])) > maxlist[i+b[1]]:
                maxlist[i+b[1]] = concat(maxlist[i],b[0])
 
print(maxlist[N])

%%timeit

def input():
    return next(input_sample)


input_sample=iter("""
10000 9
1 2 3 4 5 6 7 8 9
""".split("\n")[1:-1])


N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])

if [5,5] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:    
        B.remove([3,5])

if [3,5] in B and [2,5] in B:
    B.remove([2,5])

if [7,3] in B:
    if [6,6] in B:
        B.remove([6,6])
    if [9,6] in B:
        B.remove([9,6])
    
if [9,6] in B and [6,6] in B:
    B.remove([6,6])

if [1,2] in B and [7,3] in B:
    if [2,5] in B:
        B.remove([2,5])
    if [3,5] in B:
        B.remove([3,5])
    if [5,5] in B:
        B.remove([5,5])
    if [8,7] in B:
        B.remove([8,7])

if [1,2] in B and ([2,5] in B or [3,5] in B or [5,5] in B) and [8,7] in B:
    B.remove([8,7])
    
if [4,4] in B and [7,3] and [8,7] in B:
    B.remove([8,7])
    
if [1,2] in B and [4,4] in B:
    B.remove([4,4])

maxlist=[""]*(N+10)
 
for i in range(N+1):
    if i!=0 and maxlist[i]=="":
        continue
    else:
        for b in B:
            ans=maxlist[i]+str(b[0])
            _max=maxlist[i+b[1]]
            if i+b[1]>N:
                continue
            if len(ans)<len(_max):
                continue
            elif len(ans)>len(_max):
                maxlist[i+b[1]] = ans
            else:
                for j in range(len(ans)):
                    if ans[j]>_max[j]:
                        maxlist[i+b[1]] = ans
 
print(maxlist[N])

def comp(a,b):
    if sum(a)<sum(b):
        return "right"
    elif sum(a)>sum(b):
        return "left"
    else:
        for i in range(8,-1,-1):
            if a[i]<b[i]:
                return "right"
            elif a[i]>b[i]:
                return "left"
        else:
            return "equal"

N,M=map(int,input().split())
A=list((map(int,input().split())))
 
m=[[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
B=[]
    
for a in A:
    B.append(m[a-1])
    
maxlist=[[0]*9 for _ in range(N+1)]
 
for i in range(N+1):
    if i!=0 and sum(maxlist[i])==0:
        continue
    else:
        for b in B:
            if i+b[1]>N:
                continue
            ans=[maxlist[i][k] for k in range(9)]
            ans[b[0]-1]+=1
            _max=maxlist[i+b[1]]
            if comp(ans,_max) == "left":
                maxlist[i+b[1]]=[ans[k] for k in range(9)]
 
for i in range(8,-1,-1):
    print(str(i+1)*maxlist[N][i],end="")
print()

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Accepted