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())
x=[0,2,5,5,4,5,6,3,7,6]
a=list(map(int,input().split()))
a.sort()
x=[ x[a[i]] for i in range(M) ]

p=[[-1 for j in range(M)] for i in range(430)]
p[0]=[0 for j in range(M)]

for i in range(421):
    for j in range(M):
        if p[i][0]>-1 and sum(p[i])+1>sum(p[i+x[j]]):
            p[i+x[j]]=[p[i][k] for k in range(M)]
            p[i+x[j]][j]+=1

        elif p[i][0]>-1 and sum(p[i])+1==sum(p[i+x[j]]):
            tmp=[p[i][k] for k in range(M)]

            tmp[j]+=1
            for k in range(M-1,-1,-1):
                if tmp[k] > p[i+x[j]][k] :
                    p[i+x[j]]=[tmp[k] for k in range(M)]
                    break

for j in range(M):
    if x[j]==min(x): Mi=j

ans=[0 for i in range(M)]
for i in range(420):
    if N-i<0: break
    if (N-i)%x[Mi]==0 and (N-i)//x[Mi]+sum(p[i])>sum(ans):
        ans=p[i]
        ans[Mi]+=(N-i)//x[Mi]

for i in range(M-1,-1,-1):
    for j in range(ans[i]):
        print(a[i],end="")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
x=[0,2,5,5,4,5,6,3,7,6]
a=list(map(int,input().split()))
a.sort()
x=[ x[a[i]] for i in range(M) ]
 
p=[[-1 for j in range(M)] for i in range(430)]
p[0]=[0 for j in range(M)]
for i in range(420):
    for j in range(M):
        if p[i][0]>-1 and sum(p[i])+1>=sum(p[i+x[j]]):
            p[i+x[j]]=[p[i][k] for k in range(M)]
            p[i+x[j]][j]+=1
 
for j in range(M):
    if x[j]==min(x): Mi=j
 
ans=[0 for i in range(M)]
for i in range(420):
    if N-i<0: break
    if (N-i)%x[Mi]==0 and (N-i)//x[Mi]+sum(p[i])>sum(ans):
        ans=p[i]
        ans[Mi]+=(N-i)//x[Mi]
 
for i in range(M-1,-1,-1):
    for j in range(ans[i]):
        print(a[i],end="")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
x=[0,2,5,5,4,5,6,3,7,6]
a=list(map(int,input().split()))
a.sort()
x=[ x[a[i]] for i in range(M) ]
p=[[-1 for j in range(M)] for i in range(430)]
p[0]=[0 for j in range(M)]

for i in range(10):
    for j in range(M):
        if p[i][0]>-1 and sum(p[i])+1>sum(p[i+x[j]]):
            p[i+x[j]]=[p[i][k] for k in range(M)]
            p[i+x[j]][j]+=1

for j in range(M):
    if x[j]==min(x): Mi=j

ans=[0 for i in range(M)]
for i in range(420):
    if N-i<0: break
    if (N-i)%x[Mi]==0 and (N-i)//x[Mi]+sum(p[i])>sum(ans):
        ans=p[i]
        ans[Mi]+=(N-i)//x[Mi]

for i in range(M-1,-1,-1):
    for j in range(ans[i]):
        print(a[i],end="")

Submission status: Wrong Answer

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

p=[[-1 for j in range(M)] for i in range(430)]
p[0]=[0 for j in range(M)]
for i in range(10):
    for j in range(M):
        if p[i][0]>-1 and sum(p[i])+1>=sum(p[i+x[j]]):
            p[i+x[j]]=[p[i][k] for k in range(M)]
            p[i+x[j]][j]+=1

for j in range(M):
    if x[j]==min(x): Mi=j

ans=[0 for i in range(M)]
for i in range(420):
    if N-i<0: break
    if (N-i)%x[Mi]==0 and (N-i)//x[Mi]+sum(p[i])>sum(ans):
        ans=p[i]
        ans[Mi]+=(N-i)//x[Mi]

for i in range(M-1,-1,-1):
    for j in range(ans[i]):
        print(a[i],end="")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
from operator import itemgetter
#cost,value
matches = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
li = []
N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

def dfs(n,num,cand):
    if(n>=len(li) or num+li[n][1]>N):
        return False
    if(num+li[n][1]==N):
        if(li[n][0] in cand):
            cand[li[n][0]]+=1
        else:
            cand[li[n][0]]=1
        return True
    for i in range(n,len(li)):
        if(dfs(i,num+li[n][1],cand)):
            if(li[n][0] in cand):
                cand[li[n][0]]+=1
            else:
                cand[li[n][0]]=1
            return True
    return False

for x in A:
    li+=[(x,matches[x])]
li.sort(key=itemgetter(1,0))
cand={}
dfs(0,0,cand)
ans = ''
for i in cand:
    ans = str(i)*cand[i]+ans

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
from operator import itemgetter
#cost,value
matches = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
li = []
N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

def dfs(n,num,cand):
    if(n>=len(li) or num+li[n][1]>N):
        return False
    if(num+li[n][1]==N):
        if(li[n][0] in cand):
            cand[li[n][0]]+=1
        else:
            cand[li[n][0]]=1
        return True
    for i in range(n,len(li)):
        if(dfs(i,num+li[n][1],cand)):
            if(li[n][0] in cand):
                cand[li[n][0]]+=1
            else:
                cand[li[n][0]]=1
            return True
    return False


for x in A:
    li+=[(x,matches[x])]
li.sort(key=itemgetter(0))
li.reverse()
li.sort(key=itemgetter(1))
cand={}
dfs(0,0,cand)
ans = ''
for i in cand:
    ans = str(i)*cand[i]+ans

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from copy import deepcopy

from bisect import bisect_left as bl

N,M=map(int,input().split())
n=N
A=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dict=defaultdict(int)
list=[]
L=[]
for key in range(9,0,-1):
    if key in A:
        if dic[key] in dict.values():
            continue
        dict[key]=dic[key]
        list.append([key,dic[key]])
        L.append(key)
list.sort(key=lambda x:x[1])
cost=[]
for i in list:
    cost.append(i[1])
num=len(dict.keys())

dp=[[-1 for i in range(num+1)] for j in range(N+1)]
dp[0]=[0]*(num+1)
#dp[i] N=iでの最大値
Non=[-1]*(num+1)
for i in range(N):
    ini=[]
    for j in range(num):
        if i+1-cost[j]>=0 and dp[i+1-cost[j]]!=Non:
            a=dp[i+1-cost[j]][:]
            a[j+1]+=1
            a[0]+=1
            ini.append(a)
    if ini:
        dp[i+1]=max(ini)
s=""
s1=""
Num=N
Keys=dic.keys()
Ken=[]
for i in Keys:
  Ken.append(i)
Keys=Ken
Keys.reverse()
for i in range(dp[N][0]):
    for k in Keys:
        if Num-dic[k]>=0 and dp[Num][0]-1==dp[Num-dic[k]][0]:
            s1+=str(k)
            Num-=dic[k]
            break
print(s1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from copy import deepcopy

from bisect import bisect_left as bl

N,M=map(int,input().split())
n=N
A=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dict=defaultdict(int)
list=[]
L=[]
for key in range(9,0,-1):
    if key in A:
        if dic[key] in dict.values():
            continue
        dict[key]=dic[key]
        list.append([key,dic[key]])
        L.append(key)
list.sort(key=lambda x:x[1])
cost=[]
for i in list:
    cost.append(i[1])
num=len(dict.keys())

dp=[[-1 for i in range(num+1)] for j in range(N+1)]
dp[0]=[0]*(num+1)
#dp[i] N=iでの最大値
Non=[-1]*(num+1)
for i in range(N):
    ini=[]
    for j in range(num):
        if i+1-cost[j]>=0 and dp[i+1-cost[j]]!=Non:
            a=dp[i+1-cost[j]][:]
            a[j+1]+=1
            a[0]+=1
            ini.append(a)
    if ini:
        dp[i+1]=max(ini)
s=""

for l in L:
    for i in range(num):
        key,cost=list[i]
        if l==key:
            s+=str(key)*dp[N][i+1]

print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from copy import deepcopy

from bisect import bisect_left as bl

N,M=map(int,input().split())
n=N
A=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dict=defaultdict(int)
keys=list(dic.keys())
keys.reverse()
list=[]
L=[]
for key in keys:
    if key in A:
        if dic[key] in dict.values():
            continue
        dict[key]=dic[key]
        list.append([key,dic[key]])
        L.append(key)
list.sort(key=lambda x:x[1])
cost=[]
for i in list:
    cost.append(i[1])
num=len(dict.keys())

dp=[[-1 for i in range(num+1)] for j in range(N+1)]
dp[0]=[0]*(num+1)
#dp[i] N=iでの最大値
Non=[-1]*(num+1)
for i in range(N):
    ini=[]
    for j in range(num):
        if i+1-cost[j]>=0:
            a=dp[i+1-cost[j]][:]
            if a!=Non:
                a[j+1]+=1
                a[0]+=1
                ini.append(a)
    if ini:
        dp[i+1]=max(ini)
s=""
for l in L:
    for i in range(num):
        key,cost=list[i]
        if l==key:
            s+=str(key)*dp[N][i+1]
if len(s)>N/2:
    print(2/0)
print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from copy import deepcopy

from bisect import bisect_left as bl

N,M=map(int,input().split())
n=N
A=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dict=defaultdict(int)
keys=list(dic.keys())
keys.reverse()
list=[]
L=[]
for key in keys:
    if key in A:
        if dic[key] in dict.values():
            continue
        dict[key]=dic[key]
        list.append([key,dic[key]])
        L.append(key)
list.sort(key=lambda x:x[1])
cost=[]
for i in list:
    cost.append(i[1])
num=len(dict.keys())

dp=[[-1 for i in range(num+1)] for j in range(N+1)]
dp[0]=[0]*(num+1)
#dp[i] N=iでの最大値
Non=[-1]*(num+1)
for i in range(N):
    ini=[]
    for j in range(num):
        if i+1-cost[j]>=0:
            a=dp[i+1-cost[j]][:]
            if a!=Non:
                a[j+1]+=1
                a[0]+=1
                ini.append(a)
    if ini:
        dp[i+1]=max(ini)
s=""
for l in L:
    for i in range(num):
        key,cost=list[i]
        if l==key:
            s+=str(key)*dp[N][i+1]
print(s)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from copy import deepcopy

from bisect import bisect_left as bl

N,M=map(int,input().split())
n=N
A=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dict=defaultdict(int)
keys=list(dic.keys())
keys.reverse()
list=[]
L=[]
for key in keys:
    if key in A:
        if dic[key] in dict.values():
            continue
        dict[key]=dic[key]
        list.append([key,dic[key]])
        L.append(key)
list.sort(key=lambda x:x[1])
cost=[]
for i in list:
    cost.append(i[1])
num=len(dict.keys())

dp=[[-1 for i in range(num)] for j in range(N+1)]
dp[0]=[0]*num
#dp[i] N=iでの最大値
Non=[-1]*num
for i in range(N):
    for j in range(num):
        if i+1-cost[j]>=0:
            dp[i+1]=dp[i+1-cost[j]][:]
            if dp[i+1]!=Non:
                dp[i+1][j]+=1
                break
s=""
for l in L:
    for i in range(num):
        key,cost=list[i]
        if l==key:
            s+=str(key)*dp[N][i]
print(s)

Submission status: Wrong Answer

Solution code:
n,m = [int(i) for i in input().split()]
a = list(map(int,input().split()))

import sys
sys.setrecursionlimit(50000)

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

dig = [0] * (n+1)

inf = 10**9


for i in range(1, n + 1):
    lst = []
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if bef >= 0:
            lst.append(dig[bef])
        if lst:
            dig[i] = max(lst) + 1


ans = ""


def dp(i):
    k = -1
    if i == 0:
        return
    global ans
    maxi = 0
    for j in range(len(a)):
        num = a[j]
        mat = match[num]
        bef = i - mat
        if dig[i] == 1:
            if bef == 0:
                maxi = max(maxi, num)
                k = 0
        else:
            if bef >= 0:
                if dig[bef] == dig[i] - 1:
                    if num > maxi:
                        maxi = num
                        k = bef
    ans += str(maxi)
    if k >= 0:
        dp(k)


dp(n)
print(ans)

Submission status: Wrong Answer

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

import sys
INT_MIN = sys.maxsize * -1
match = [-100,2,5,5,4,5,6,3,7,6]
CHOICES = []
for i in A:
    if (i == 6) and (9 in A):
        continue
    if (i == 3) and (5 in A):
        continue
    if (i == 2) and (3 in A or 5 in A):
        continue
    CHOICES.append([i, match[i]])
CHOICES.sort(reverse=True)

ans = [0]
#print(CHOICES)
for i in range(1,N+1):
    ans.append(INT_MIN)
    for c in CHOICES:
        if  i - c[1] == 0:
            ans[i] = max(ans[i], int(str(c[0])))
            break
        elif i - c[1] >= 0 and ans[i - c[1]] != INT_MIN:
            ans[i] = max(ans[i], int(str(c[0]) + str(ans[i - c[1]])))
            break

print(ans[N])

Submission status: Wrong Answer

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

N, M = map(int, input().split())
A = [int(_) for _ in input().split()]
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0]*(N+1)
B = []

for i in A:
    itmp = i
    inum = match[i]
    for j in range(i+1, 10):
        if inum == match[j] and j in A:
            itmp = j
    B.append([itmp, match[itmp]])

B = sorted(B, key=lambda x: x[1])

for i in range(N+1):
    for a in B:
        if i - a[1] < 0:
            continue
        else:
            if dp[i-a[1]] == 0:
                tmp = a[0]
            else:
                tmp = a[0]*10**len(str(dp[i-a[1]]))+dp[i-a[1]]

            if tmp > dp[i]:
                dp[i] = tmp

print(dp[N])

Submission status: Wrong Answer

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

N, M = map(int, input().split())
A = [int(_) for _ in input().split()]
match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0]*(N+1)
B = set()

for i in A:
    itmp = i
    inum = match[i]
    for j in range(i+1, 10):
        if inum == match[j] and j in A:
            itmp = j
    B.add(itmp)

for i in range(N):
    for a in B:
        if i + match[a] > N:
            continue
        else:
            if dp[i+match[a]] == 0:
                tmp = a
            else:
                if dp[i] == 0:
                    continue
                else:
                    tmp = int(''.join(sorted(list(str(a*10**len(str(dp[i]))+dp[i])))[::-1]))

            if tmp > dp[i+match[a]]:
                dp[i+match[a]] = tmp

print(dp[N])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

from collections import defaultdict

N, M = map(int, input().rstrip().split(' '))
A = sorted(list(map(int, input().rstrip().split(' '))))[::-1]

numbers = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
temp = [False] * 8
temp_A = []
for a in A:
    if temp[numbers[a]] == False:
        temp_A.append(a)
        temp[numbers[a]] = True
A = temp_A

max_numbers = []
memo = defaultdict(lambda: defaultdict(lambda: [-1, -1]))
memo2 = defaultdict(lambda: defaultdict(lambda: []))
def recursive(n, honsu, sum_numbers, i):
    
    if memo[n][i][0] != -1:
        return memo[n][i][0], memo[n][i][1], memo2[n][i]
    if n == 0:
        return honsu, sum_numbers, [0] * (len(A) - i)
                
    max_honsu = -1
    max_sum_numbers = -1
    max_k = []
    for j in range(i, len(A)):
        a = A[j]
        for k in range(n // numbers[a] + 1):
            return_honsu, return_sum_numbers, return_ks = recursive(n - numbers[a] * k, honsu + k, sum_numbers + a * k, j + 1)
            
            if return_honsu > max_honsu:
                max_honsu = return_honsu
                max_sum_numbers = return_sum_numbers
                max_k = [k] + return_ks
            elif return_honsu == max_honsu:
                if return_sum_numbers > max_sum_numbers:
                    max_sum_numbers = return_sum_numbers
                    max_k = [k] + return_ks
            
    memo[n][i][0] = max_honsu
    memo[n][i][1] = max_sum_numbers
    memo2[n][i] = max_k
    
    return max_honsu, max_sum_numbers, max_k
    
honsu, sum_numbers, _ = recursive(N, 0, 0, 0)

honsu = sorted([[a, x] for a, x in zip(A, memo2[N][0])], key=lambda x: x[0])[::-1]
for a, x in honsu:
    for _ in range(x):
        print(a, end='')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

from collections import defaultdict

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

numbers = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}

max_numbers = []
memo = defaultdict(lambda: defaultdict(lambda: [-1, -1]))
memo2 = defaultdict(lambda: defaultdict(lambda: []))
def recursive(n, honsu, sum_numbers, i):
    
    if memo[n][i][0] != -1:
        return memo[n][i][0], memo[n][i][1], memo2[n][i]
    if n == 0:
        return honsu, sum_numbers, [0] * (len(A) - i)
                
    max_honsu = -1
    max_sum_numbers = -1
    max_k = []
    for j in range(i, len(A)):
        a = A[j]
        for k in range(n // numbers[a] + 1):
            return_honsu, return_sum_numbers, return_ks = recursive(n - numbers[a] * k, honsu + k, sum_numbers + a * k, j + 1)
            
            if return_honsu > max_honsu:
                max_honsu = return_honsu
                max_sum_numbers = return_sum_numbers
                max_k = [k] + return_ks
            elif return_honsu == max_honsu:
                if return_sum_numbers > max_sum_numbers:
                    max_sum_numbers = return_sum_numbers
                    max_k = [k] + return_ks
            
    memo[n][i][0] = max_honsu
    memo[n][i][1] = max_sum_numbers
    memo2[n][i] = max_k
    
    return max_honsu, max_sum_numbers, max_k
    
honsu, sum_numbers, _ = recursive(N, 0, 0, 0)

honsu = sorted([[a, x] for a, x in zip(A, memo2[N][0])], key=lambda x: x[0])[::-1]
for a, x in honsu:
    for _ in range(x):
        print(a, end='')

Submission status: Wrong Answer

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

V = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

memo = [-1] * (N + 1)
memo[N] = 0
next_memo = [-1] * (N + 1)


def reset_memo():
    global next_memo
    for i in range(N + 1):
        next_memo[i] = -1


def memo_to_next():
    global memo, next_memo
    for i in range(N + 1):
        memo[i] = next_memo[i]


while 1:
    next_memo[0] = memo[0]
    fin = True
    for i in range(N, 0, -1):
        # print(memo)
        if memo[i] < 0: continue

        for j in range(1, 10):
            if not j in A: continue
            idx = i - V[j]
            if idx >= 0:
                next_memo[idx] = max(next_memo[idx], memo[i] * 10 + j)
                if idx > 0:
                    fin = False
    if fin:
        break
    memo_to_next()
    reset_memo()
print(memo[0])

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 2 in a and 3 in a:
        a.remove(2)
    if 6 in a and 9 in a:
        a.remove(6)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        print(base)
        print(n)
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if len(use) == 1:
            base = base[:-1]
            n += needs[b[0]]
        elif max(use) == b[0]:
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
        else:
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, m, *a = map(int, string.split())
    needs = {i + 1: n for i, n in enumerate(map(int, "2 5 5 4 5 6 3 7 6".split()))}
    if 2 in a and 5 in a:
        a.remove(2)
    if 3 in a and 5 in a:
        a.remove(3)
    if 2 in a and 3 in a:
        a.remove(2)
    if 6 in a and 9 in a:
        a.remove(6)
    b = sorted(a, key=lambda x: needs[x])
    index = 0
    base = str(b[0]) * (n // needs[b[0]])
    n %= needs[b[0]]
    while n > 0:
        use = [_b for _b in b if needs[_b] <= needs[b[0]] + n]
        if max(use) == b[0]:
            return base
            tmp_n = use[-1]
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:-tmp_c] + str(tmp_n) * tmp_c
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
        else:
            tmp_n = max(use)
            tmp_c = n // (needs[tmp_n] - needs[b[0]])
            base = base[:index] + str(tmp_n) * tmp_c + base[index + tmp_c:]
            n -= (needs[tmp_n] - needs[b[0]]) * tmp_c
            index += tmp_c
    return base


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))

Submission status: Wrong Answer

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
dp=[-1 for i in range(10**4 + 1)]
Cost={(i+1):v for i,v in enumerate([2,5,5,4,5,6,3,7,6])}

for a in A:
    dp[Cost[a]] = a

for n in range(2, N+1):
    for a in A:
        if dp[n-Cost[a]] != -1:
            dp[n] = max(dp[n], dp[n-Cost[a]] * 10 + a)
print(dp[n])

Submission status: Wrong Answer

Solution code:
import math

n,m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

#値と本数のセット（本数が少ない順かつ値が大きい順）
set = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[6,6],[8,7]]

#同じ本数で値が小さい数字を使うことはない
if 2 in a:
  if 3 in a or 5 in a:
    a.remove(2)
    m -= 1

if 3 in a:
  if 5 in a:
    a.remove(3)
    m -= 1
  
if 6 in a:
  if 9 in a:
    a.remove(6)
    m -= 1

#上記の処理を施した上で与えられたaの数と本数の組み合わせを抽出
exist_set = [i for i in set if i[0] in a]

#本数の最大値。あとで使用
max_honsu = max([i[1] for i in exist_set])

#あとでexist_setからnumを除いた数字による探索を行うため
m -= 1

#最大桁数のうち値が大きいもの
max_keta = 0
ans_kouho = []

for exist_one in exist_set:
  keta_tmp = n//exist_one[1]
  num_tmp = exist_one[0]
  amari_tmp = n % exist_one[1]
  honsu_tmp = exist_one[1]
  
  ###print(keta_tmp,num_tmp)
  
  #余りが0出ない場合、aの本数の最大値は不採用（余りを調整できない）
  if amari_tmp != 0 and honsu_tmp == max_honsu:
    continue
  if keta_tmp >= max_keta:
    keta = keta_tmp
    num = num_tmp
    amari = amari_tmp
    honsu = honsu_tmp

    #余り0ならちょうどなので終了
    if amari == 0:
      ans_kouho.append(int(str(num)*keta))
      max_keta = keta
      continue
      
    #以下余りを調整

    #変更する値は必ずnum以外だからexist_setからnumを削除
    exist_yet = [inc for inc in exist_set if inc[0] != num]

    #1桁ずつ値を変更し、あまりを0にできるか調査
    for keta_num in range(1,min(max_honsu,keta+1)):
      
      kouho = []

      #bit全探索
      #候補に使用しないも追加
      bit = math.ceil(math.log2(m+1))
      for all_bit in range((2**m)*keta_num):
        change = []
        nokori = amari + honsu * keta_num
        for bit_conf in range(keta_num):
          bit_index =  (all_bit >> bit_conf*bit) & (2**m-1)

          #bit_indexは0~mだからm+1以上は終了
          if bit_index > m:
            break
            
          #使用しないに相当
          if bit_index == m:
            change.append(0)
            continue

          #bit_indexに従い数字を記録、残りの本数を減らす
          change.append(exist_yet[bit_index][0])
          nokori -= exist_yet[bit_index][1]

          if nokori < 0:
            break
            
        if bit_index > m or nokori < 0:
          continue

        #残りが0ならちょうど使い切る。数の組み合わせを候補に追加
        if nokori == 0:
          kouho.append(change)
          

      #候補があればループを抜ける
      if len(kouho) != 0:
        max_keta = keta
        break
      
    #候補から値の大きいものを抜き出す
    if len(kouho) != 0:
      
      #keta-del_lenがnumの数
      del_len = len(kouho[0])
        
      #0を削除
      kouho = [[inc_1 for inc_1 in inc_2 if inc_1 != 0] for inc_2 in kouho]
      
      #0を除いたときの最大桁が候補
      max_len = max([len(inc) for inc in kouho])
      kouho = [inc for inc in kouho if len(inc) == max_len]

      #候補を降順に並び替え
      kouho = [sorted(kouho_one,reverse=True) for kouho_one in kouho]

      #同じパターンを削除
      kouho_tmp = []
      for kouho_one in kouho:
        if kouho_one not in kouho_tmp:
          kouho_tmp.append(kouho_one)
      kouho = kouho_tmp

      #最大候補の抽出
      for kouho_one in range(len(kouho[0])):
        if len(kouho) == 1:
          break
        max_i = max([inc[kouho_one] for inc in kouho])
        kouho = [inc for inc in kouho if inc[kouho_one] == max_i]
      kouho = kouho[0]
        
      ans = [num]*(keta-del_len) + kouho
      ans.sort(reverse=True)
      ans_str = ''
      for ans_one in ans:
        ans_str += str(ans_one)
      ans_kouho.append(int(ans_str))

ans_kouho.sort()
###print(ans_kouho)
print(ans_kouho[-1])

Submission status: Wrong Answer

Solution code:
import math

n,m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

#値と本数のセット（本数が少ない順かつ値が大きい順）
set = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[6,6],[8,7]]

#同じ本数で値が小さい数字を使うことはない
if 2 in a:
  if 3 in a or 5 in a:
    a.remove(2)
    m -= 1

if 3 in a:
  if 5 in a:
    a.remove(3)
    m -= 1
  
if 6 in a:
  if 9 in a:
    a.remove(6)
    m -= 1

#上記の処理を施した上で与えられたaの数と本数の組み合わせを抽出
exist_set = [i for i in set if i[0] in a]

#本数の最大値。あとで使用
max_honsu = max([i[1] for i in exist_set])

#あとでexist_setからnumを除いた数字による探索を行うため
m -= 1

#最大桁数のうち値が大きいもの
max_keta = 0
ans_kouho = []

for exist_one in exist_set:
  keta_tmp = n//exist_one[1]
  num_tmp = exist_one[0]
  amari_tmp = n % exist_one[1]
  honsu_tmp = exist_one[1]
  
  ###print(keta_tmp,num_tmp)
  
  #余りが0出ない場合、aの本数の最大値は不採用（余りを調整できない）
  if amari_tmp != 0 and honsu_tmp == max_honsu:
    continue
  if keta_tmp >= max_keta:
    keta = keta_tmp
    num = num_tmp
    amari = amari_tmp
    honsu = honsu_tmp

    #余り0ならちょうどなので終了
    if amari == 0:
      ans_kouho.append(int(str(num)*keta))
      max_keta = keta
      continue
      
    #以下余りを調整

    #変更する値は必ずnum以外だからexist_setからnumを削除
    exist_yet = [inc for inc in exist_set if inc[0] != num]

    #1桁ずつ値を変更し、あまりを0にできるか調査
    for keta_num in range(1,min(max_honsu,keta+1)):
      
      kouho = []

      #bit全探索
      #候補に使用しないも追加
      bit = math.ceil(math.log2(m+1))
      for all_bit in range((2**m)*keta_num):
        change = []
        nokori = amari + honsu * keta_num
        for bit_conf in range(keta_num):
          bit_index =  (all_bit >> bit_conf*bit) & (2**m-1)

          #bit_indexは0~m-1だからm以上は終了
          if bit_index > m:
            break
            
          #使用しないに相当
          if bit_index == m:
            change.append(0)
            continue

          #bit_indexに従い数字を記録、残りの本数を減らす
          change.append(exist_yet[bit_index][0])
          nokori -= exist_yet[bit_index][1]

          if nokori < 0:
            break
            
        if bit_index > m or nokori < 0:
          continue

        #残りが0ならちょうど使い切る。数の組み合わせを候補に追加
        if nokori == 0:
          kouho.append(change)

      #候補があればループを抜ける
      if len(kouho) != 0:
        break
      
    #候補から値の大きいものを抜き出す
    if len(kouho) != 0:
      
      max_keta = keta

      #候補を降順に並び替え
      kouho = [sorted(kouho_one,reverse=True) for kouho_one in kouho]

      #同じパターンを削除
      kouho_tmp = []
      for kouho_one in kouho:
        if kouho_one not in kouho_tmp:
          kouho_tmp.append(kouho_one)
      kouho = kouho_tmp

      #最大候補の抽出
      for kouho_one in range(len(kouho[0])):
        if len(kouho) == 1:
          break
        max_i = max([inc[kouho_one] for inc in kouho])
        kouho = [inc for inc in kouho if inc[kouho_one] == max_i]
      kouho = kouho[0]
      kouho_non0 = [i for i in kouho if i != 0]
        
      ans = [num]*(keta-len(kouho)) + kouho_non0
      ans.sort(reverse=True)
      ans_str = ''
      for ans_one in ans:
        ans_str += str(ans_one)
      ans_kouho.append(int(ans_str))

ans_kouho.sort()
###print(ans_kouho)
print(ans_kouho[-1])

Submission status: Wrong Answer

Solution code:
import math

n,m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

#値と本数のセット（本数が少ない順かつ値が大きい順）
set = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[6,6],[8,7]]

#同じ本数で値が小さい数字を使うことはない
if 2 in a:
  if 3 in a or 5 in a:
    a.remove(2)
    m -= 1

if 3 in a:
  if 5 in a:
    a.remove(3)
    m -= 1
  
if 6 in a:
  if 9 in a:
    a.remove(6)
    m -= 1

#aの最大値。あとで使用
max_a = max(a)

#上記の処理を施した上で与えられたaの数と本数の組み合わせを抽出
exist_set = [i for i in set if i[0] in a]

#最大桁数のうち値が大きいもの
keta = 0
num = 0
for i in exist_set:
  keta_tmp = n//i[1]
  num_tmp = i[0]
  amari_tmp = n % i[1]
  #余りが0出ない場合、aの最大値は不採用（余りを調整できない）
  if amari_tmp != 0 and num_tmp == max_a:
    continue
  if keta_tmp >= keta and num_tmp > num:
    keta = keta_tmp
    num = num_tmp
    amari = amari_tmp
    honsu = i[1]

    #余り0ならちょうどなので終了
    if amari == 0:
      print(str(num)*keta)
      exit()
      
    #以下余りを調整

    #変更する値は必ずnum以外だからexist_setからnumを削除
    exist_yet = [i for i in exist_set if i[0] != num]
    m -= 1

    #1桁ずつ値を変更し、あまりを0にできるか調査
    for i in range(1,honsu):

      #bit全探索
      bit = math.ceil(math.log2(m))
      kouho = []
      for j in range((2**m)*i):
        change = []
        nokori = amari + honsu * i
        for k in range(i):
          bit_index =  (j >> k*bit) & (2**m-1)

          #bit_indexは0~m-1だからm以上は終了
          if bit_index >= m:
            break

          #bit_indexに従い数字を記録、残りの本数を減らす
          change.append(exist_yet[bit_index][0])
          nokori -= exist_yet[bit_index][1]

          if nokori < 0:
            break

        #残りが0ならちょうど使い切る。数の組み合わせを候補に追加
        if nokori == 0:
          kouho.append(change)
      
      #候補があればループを抜ける
      if len(kouho) != 0:
        break

    if len(kouho) == 0:
      continue
 
    #候補から値の大きいものを抜き出す

    #候補を降順に並び替え
    kouho = [sorted(i,reverse=True) for i in kouho]

    #同じパターンを削除
    kouho_tmp = []
    for i in kouho:
      if i not in kouho_tmp:
        kouho_tmp.append(i)
    kouho = kouho_tmp

    #最大候補の抽出
    for i in range(len(kouho[0])):
      if len(kouho) == 1:
        break
      max_i = max([j[i] for j in kouho])
      kouho = [j for j in kouho if j[i] == max_i]
    kouho = kouho[0]

    ans = [num]*(keta-len(kouho)) + kouho
    ans.sort(reverse=True)
    ans_str = ''
    for i in ans:
      ans_str += str(i)
    print(ans_str)
    exit()