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: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
numA = [2,5,5,4,5,6,3,7,6]
useA = []
if 1 in A:
    if N%2 == 0:
        ans = 0
        for i in range(int(N/2)):
            ans+=10**i
    else:
        if 7 in A:
            ans = 0
            for i in range(int(N/2)):
                if i == int(N/2)-1:
                    ans+=7*(10**i)
                else:
                    ans+=10**i
        elif 5 in A:
            ans = 0
            for i in range(int(N/2)):
                if i == int(N/2)-1:
                    ans+=5*(10**i)
                else:
                    ans+=10**i
        elif 3 in A:
            ans = 0
            for i in range(int(N/2)):
                if i == int(N/2)-1:
                    ans+=3*(10**i)
                else:
                    ans+=10**i
        else:
            ans = 0
            for i in range(int(N/2)):
                if i == int(N/2)-1:
                    ans+=2*(10**(i))
                else:
                    ans+=10**i
elif 7 in A:
    if N%3 == 0:
        ans = 0
        for i in range(int(N/3)):
            ans+=7*(10**i)
    elif N%3 == 1 and 4 in A:
        ans = 0
        for i in range(int(N/3)):
            if i == 0:
                ans+=4
            else:
                ans+=7*(10**i)
    elif N%3 == 2 and (5 in A or 3 in A or 2 in A):
        ans = 0
        if 5 in A:
            for i in range(int(N/3)):
                if i == 0:
                    ans+=5
                else:
                    ans+=7*(10**i)
        elif 3 in A:
            for i in range(int(N/3)):
                if i == 0:
                    ans+=3
                else:
                    ans+=7*(10**i)
        elif 2 in A:
            for i in range(int(N/3)):
                if i == 0:
                    ans+=2
                else:
                    ans+=7*(10**i)
    else:
        ans = 0
        for i in range(int(N/3)-1):
            if i == int(N/3)-2:
                ans+=8*(10**i)
            else:
                ans+=7*(10**i)
elif 4 in A:
    if N%4 == 0:
        ans = 0
        for i in range(N%4):
            ans+=4*(10**i)
    else:
        if N%4 == 1 and (5 in A or 3 in A or 2 in A):
            ans = 0
            if 5 in A:
                for i in range(int(N/4)):
                    if i == int(N/4)-1:
                        ans+=5*(10**i)
                    else:
                        ans+=4*(10**i)
            elif 3 in A:
                for i in range(int(N/4)):
                    if i == 0:
                        ans+=3
                    else:
                        ans+=4*(10**i)
            elif 2 in A:
                for i in range(int(N/4)):
                    if i == 0:
                        ans+=2
                    else:
                        ans+=4*(10**i)
        elif N%4 == 2 and (9 in A or 6 in A):
            ans = 0
            if 9 in A:
                for i in range(int(N/4)):
                    if i == int(N/4)-1:
                        ans+=9*(10**i)
                    else:
                        ans+=4*(10**i)
            elif 6 in A:
                for i in range(int(N/4)):
                    if i == int(N/4)-1:
                        ans+=6*(10**i)
                    else:
                        ans+=4*(10**i)
        elif N%4 == 3 and 8 in A:
            ans = 0
            for i in range(int(N/4)):
                if i == int(N/4)-1:
                        ans+=8*(10**i)
                else:
                        ans+=4*(10**i)
        elif N%4 == 2 and (5 in A or 3 in A or 2 in A):
            ans = 0
            if 5 in A:
                for i in range(int(N/4)):
                    if i == int(N/4)-1:
                        ans+=5*(10**i)
                    else:
                        ans+=4*(10**i)
            elif 3 in A:
                for i in range(int(N/4)):
                    if i == 0:
                        ans+=3
                    else:
                        ans+=4*(10**i)
            elif 2 in A:
                for i in range(int(N/4)):
                    if i == 0:
                        ans+=2
                    else:
                        ans+=4*(10**i)
        elif N%4 == 3 and ((5 in A or 3 in A or 2 in A) and (9 in A or 6 in A)):
            ans = 0
            if 5 in A:
                if 9 in A:
                    for i in range(int(N/4)):
                        if i == int(N/4) -1:
                            ans+=9*(10**i)
                        elif i == int(N/4)-2:
                            ans+=5*(10**i)
                        else:
                            ans+=4*(10**i)
                elif 6 in A:
                    for i in range(int(N/4)):
                        if i == int(N/4) -1:
                            ans+=6*(10**i)
                        elif i == int(N/4)-2:
                            ans+=5*(10**i)
                        else:
                            ans+=4*(10**i)
            elif 3 in A:
                if 9 in A:
                     for i in range(int(N/4)):
                        if i == int(N/4) -1:
                            ans+=9*(10**i)
                        elif i == 0:
                            ans+=3*(10**i)
                        else:
                            ans+=4*(10**i)
                elif 6 in A:
                    for i in range(int(N/4)):
                        if i == int(N/4) -1:
                            ans+=6*(10**i)
                        elif i == 0:
                            ans+=3*(10**i)
                        else:
                            ans+=4*(10**i)
            elif 2 in A:
                if 9 in A:
                    for i in range(int(N/4)):
                        if i == int(N/4) -1:
                            ans+=9*(10**i)
                        elif i == 0:
                            ans+=2*(10**i)
                        else:
                            ans+=4*(10**i)
                elif 6 in A:
                    for i in range(int(N/4)):
                        if i == int(N/4) -1:
                            ans+=6*(10**i)
                        elif i == 0:
                            ans+=2*(10**i)
                        else:
                            ans+=4*(10**i)

                    
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
hon=[2,5,5,4,5,6,3,7,6]
a=list(map(int, input().split()))
s=sorted(set([hon[i-1] for i in a]))
x=s[0]*s[1]+1
dp=[[-100]*(x+1) for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(x+1):
        if j%s[i-1]==0:
            dp[i][j]=max(dp[i][j],j//s[i-1])
        for k in range(1,j+1):
            if (j-k)%s[i-1]==0:
                dp[i][j]=max(dp[i][j],(j-k)//s[i-1]+dp[i-1][k])
ans=[]
if n>x:
    ans+=[min(s)]*-(-(n-x)//min(s))
    n=n+(-(n-x)//min(s))*min(s)
from itertools import product
for i in product(s,repeat=dp[-1][n]):
    if sum(i)==n:break
ans+=list(i)
import bisect
ansf=[]
for i in ans:
    t=9-hon[::-1].index(i)
    bisect.insort_left(ansf,t)
print(*ansf[::-1],sep='')

Submission status: Runtime Error

Solution code:
numbers = {'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(input().split())
cands = [(a, numbers[a]) for a in A]

dp = {i: None for i in range(1, N+1)}
for c in cands:
    dp[c[1]] = int(c[0])
for i in range(2, N+1):
    for c in cands:
        j = i - c[1]
        if j >= 1 and dp[j] is not None:
            if dp[i] is None:
                dp[i] = int(''.join(str(dp[j]) + c[0]))
            else:
                if len(str(dp[i])) <  len(str(dp[j]) + c[0]):
                    dp[i] = int(str(dp[j]) + c[0])
                elif len(str(dp[i])) ==  len(str(dp[j]) + c[0]):
                    dp[i] = max(dp[i], int(''.join(sorted(str(dp[j]) + c[0], reverse=True))))
print(''.join(sorted(dp[N], reverse=True)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
D = {}
if 1 in A:
    D[2] = '1'
if 7 in A:
    D[3] = '7'
if 4 in A:
    D[4] = '4'
if 2 in A:
    D[5] = '2'
if 3 in A:
    D[5] = '3'
if 5 in A:
    D[5] = '5'
if 6 in A:
    D[6] = '6'
if 9 in A:
    D[6] = '9'
if 8 in A:
    D[8] = '8'

def chmax(s, t):
    s, t = sorted(s, reverse=True), sorted(t, reverse=True)
    if len(s) > len(t):
        return ''.join(s)
    elif len(s) < len(t):
        return ''.join(t)
    else:
        return ''.join(max(s, t))

dp = [['' for _ in range(N+1)] for _ in range(10000)]
for n, s in D.items():
    dp[1][n] = s

for i in range(1, 10000):
    for j in range(N+1):
        if dp[i][j] == '':
            continue
        for n, s in D.items():
            if j+n > N:
                continue
            dp[i+1][j+n] = chmax(dp[i+1][j+n], dp[i][j]+s)

for a in dp:
    if a[-1] != '':
        tmp = a[-1]
print(int(tmp))

Submission status: Runtime Error

Solution code:
def mina(t, i, L):
  t -= i
  if t == 0:
    return True
  elif t < 0:
    return False
  else:
    for i in L:
      if mina(t, i, L) == True:
        return True
    return False

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

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

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

A.sort(reverse = True)
D = {}
L = []
X = []
for i in A:
  if t[i - 1] not in D:
    D[t[i - 1]] = i
    L.append(t[i - 1])
    X.append([i, t[i - 1]])

L.sort()

Lmin = N // L[0]
Lmod = N % L[0]

F = True
if Lmod != 0:
  while F:
    Lmin -= 1
    Lmod += L[0]
    t = Lmod
    for i in L[1:]:
      if mina(t, i, L[1:]) == True:
        F = False
        break
  
  X.sort(reverse = True)
  for i in X:
    if i != L[0]:
      k = t - i[1]
      if k == 0:
        List = [i[0]]
        break
      elif k > 0:
        for j in X:
          if i != L[0]:
            if k - j[1] == 0:
              List = [i[0], j[0]]
              F = True
              break
        if F:
          break

Ans = [str(D[L[0]]) for i in range(Lmin)]
if Lmod != 0:
  if len(List) == 1:
    if L[0] < List[0]:
      Ans = [str(List[0])] + Ans
    else:
      Ans = Ans + [str(List[0])]
  else:
    List.sort(reverse = True)
    if L[0] > List[0]:
      Ans += [str(List[0]), str(List[1])]
    elif L[0] < List[1]:
      Ans = [str(List[0]), str(List[1])] + Ans
    else:
      Ans = [str(List[0])] + Ans + [str(List[1])]

print("".join(Ans))

Submission status: Runtime Error

Solution code:
import sys
N,M=map(int,input().split())
A=list(map(int,input().split()))
n=[0,2,5,5,4,5,6,3,7,6]
num=[0]*8
for a in A:
    num[n[a]]=max(num[n[a]],a)
nums=[]
for i in range(8):
    if num[i]: nums.append((i,num[i]))

dp=[0]*(N+1)
start=nums[0][0]
for x,y in nums:
    dp[x]=y
for i in range(start+1,N+1):
    t=dp[i]
    for x,y in nums:
        if i-x>0:
            if dp[i-x]:
                dp[i]=max([dp[i],int(str(y)+str(dp[i-x])),dp[i-x]*10+y])
    if dp[i]!=0 and (N-i)%start==0: break

if i==N: print(dp[N])
else:
    for s in str(dp[i]):
        if int(s)>nums[0][1]:
            print(str(dp[i])+str(nums[0][1])*((N-i)//start))
            sys.exit()
        if int(s)<nums[0][1]:
            print(str(nums[0][1])*((N-i)//start)+str(dp[i]))
            sys.exit()
    print(str(dp[i])+str(nums[0][1])*((N-i)//start))

Submission status: Runtime Error

Solution code:
from sys import stdin

N, M, *A = map(int, stdin.read().split())
req = {1: 2,
       2: 5,
       3: 5,
       4: 4,
       5: 5,
       6: 6,
       7: 3,
       8: 7,
       9: 6}

num = sorted([(a, req[a]) for a in A], key=lambda x: x[1])
k_min, n_min = num[0]
gt = sorted([(k, n-n_min) for k, n in num[1:] if k > k_min],
            key=lambda x: x[0], reverse=True)
lt = sorted([(k, n-n_min) for k, n in num[1:] if k < k_min],
            key=lambda x: x[0])
order = N // n_min
sum_rem = N - n_min*order

lst = []
for k, n in gt:
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
for k, n in lt:
    m = sum_rem // n
    lst.extend([k]*m)
    sum_rem -= n*m
lst.extend([k_min]*(order-len(lst)))

Submission status: Runtime Error

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

example = [2,5,5,4,5,6,3,7,6]
A_cost = [example[i-1] for i in A]

min_cost = min(A_cost)
min_bookmark = A_cost.index(min_cost)
num_standard = A[min_bookmark]
digit = N // min_cost
surplus = N - (digit * min_cost)
result = str(num_standard) * digit

now = 0
bookmark = 0
while surplus > 0:
    if A_cost[bookmark] - min_cost > surplus:
        bookmark += 1
        if bookmark == min_bookmark:
            break
        else:
            continue
    
    result = result[:now] + str(A[bookmark]) + result[now+1:]
    surplus -= A_cost[bookmark] - min_cost

    now += 1
    if now == digit:
        break

now = digit-1
big_cost = max(A_cost)
big_cost_num = A[A_cost.index(big_cost)]
while surplus > 0:
    cost = A_cost[A.index(int(result[now]))]
    if big_cost-cost <= surplus:
        surplus -= big_cost-cost
        result = result[:now] + str(big_cost_num) + result[now+1:]
        now -= 1
    else:
        big_cost -= 1
        while big_cost not in A_cost:
            big_cost -= 1
        big_cost_num = A[A_cost.index(big_cost)]
    
print(result)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
num = list(map(int,input().split()))
num_dic = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

dp = [0]*(n+1)

def creat_num(original,num):#original=431,num=1 return 4311
    if original == 0:
        return num
    new = list(map(int,list(str(original)))) + [num]
    new.sort()
    new.reverse()
    return int("".join(list(map(str,new))))

def match_dp(dp,num,num_dic,n):
    for i in num:
        if n - num_dic[i] >= 0:
            new_num = creat_num(dp[n],i)
            dp[n-num_dic[i]] = max(new_num, dp[n-num_dic[i]])
            match_dp(dp,num,num_dic,n-num_dic[i])

match_dp(dp,num,num_dic,n)

print(dp[0])

Submission status: Runtime Error

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

COST = [None, 2,5,5,4,5,6,3,7,6]

mem = [None]*(N+1)

def getScore(c):
    if mem[c] is not None:
        return mem[c]
    score = 0
    flag = False
    for a in A:
        if c >= COST[a]:
            flag = True
            score = max(getScore(c-COST[a])*10 + a, score)
    if c > 0 and flag == False:
        score = -1
    mem[c] = score
    return score

print(getScore(N))

Submission status: Runtime Error

Solution code:
def main():
    r = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    #    -  1  2  3  4  5  6  7  8  9

    N0, _ = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    memo = {} #  N : int

    def greedy(N): # int -> (int or None)
        """
        """
        #print("ENTER greedy(N=%s)" % N, A, N in memo)
        if N in memo:
            return memo[N]
        M = 0
        result = None
        for a in A:
            #print("  greedy(N=%s) a=%s, M=%s" % (N, a, M))
            if r[a] > N:
                continue
            elif r[a] == N:
                n = a
            else:
                g = greedy(N - r[a])
                if g is None:
                    continue
                n = int(
                        "".join(sorted(list(str(g)) +[str(a)], reverse=True))
                    )
            if M < n:
                result = n
                M = n
        memo[N] = result
        return result

    answer = greedy(N0)
    print(answer)

main()

Submission status: Runtime Error

Solution code:
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7
    if x == 9:
        return 6
n,m = map(int,input().split())
a = list(map(int,input().split()))
if 2 in a and 3 in a:
    a.remove(2)
    m -=1
if 2 in a and 5 in a:
    a.remove(2)
    m -=1
if 3 in a and 5 in a:
    a.remove(3)
    m -=1
if 6 in a and 9 in a:
    a.remove(6)
    m -=1
for w in range(1,10):
    if n < f(w):
        a.remove(w)
        m -=1
a.sort()
m = len(a)

dp = [[0]*(m+1) for i in range(n+2)]


def g(k):
    cand = [0]*(m+1)
    for i in range(m):
        if k - f(a[i])>=0:
            if cand[0] <= dp[k-f(a[i])][0]+1 and dp[k-f(a[i])][0] != 0:
                for r in range(m+1):
                    cand[r] = dp[k-f(a[i])][r]
                cand[0] += 1
                cand[i+1] += 1
    if sum(cand) != 0:
        dp[k] = cand
for i in range(m):
    if f(a[i]) <= n:
        dp[f(a[i])][0] = 1
        dp[f(a[i])][i+1] = 1
print(1)

Submission status: Runtime Error

Solution code:
def mina(t, i, L):
  t -= i
  if t == 0:
    return True
  elif t < 0:
    return False
  else:
    for i in L:
      if mina(t, i, L) == True:
        return True
    return False

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

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

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

A.sort(reverse = True)
D = {}
L = []
X = []
for i in A:
  if t[i - 1] not in D:
    D[t[i - 1]] = i
    L.append(t[i - 1])
    X.append([i, t[i - 1]])

L.sort()

Lmin = N // L[0]
Lmod = N % L[0]

F = True
if Lmod != 0:
  while F:
    Lmin -= 1
    Lmod += L[0]
    t = Lmod
    for i in L[1:]:
      if mina(t, i, L[1:]) == True:
        F = False
        break
  
  X.sort(reverse = True)
  for i in X:
    k = t - i[1]
    if k == 0:
      List = [i[0]]
      break
    elif k > 0:
      for j in X:
        if k - j[1] == 0:
          List = [i[0], j[0]]

Ans = [str(D[L[0]]) for i in range(Lmin)]
if Lmod != 0:
  if len(List) == 1:
    if L[0] < List[0]:
      Ans = [str(List[0])] + Ans
    else:
      Ans = Ans + [str(List[0])]
  else:
    List.sort(reverse = True)
    if L[0] > List[0]:
      Ans += [str(List[0]), str(List[1])]
    elif L[0] < List[1]:
      Ans = [str(List[0]), str(List[1])] + Ans
    else:
      Ans = [str(List[0])] + Ans + [str(List[1])]

print("".join(Ans))

Submission status: Runtime Error

Solution code:
L = [2,5,5,4,5,6,3,7,6 ]

n,m = map(int,input().split()) # n <= 10**4
A = list(map(int,input().split()))
usable_num = sorted([[i,L[i-1]] for i in A], key=lambda x:(x[1],-x[0]))
usable_num = [usable_num[i] for i in range(m) if i == 0 or usable_num[i-1][1] != usable_num[i][1]]
ans = ""
t = 0
i = 0
j = 0
while n != 0:
    if n - usable_num[i][1] < 0:
        n += usable_num[i][1]
        ans = ans[1:]
        i = (i + 1) % len(usable_num)
        if i == 0:
            tmp = ans[j]
            n += L[int(ans[j])-1]
            ans = ans[:j] + ans[j+1]
            i += 1
            j += 1
        continue
    n -= usable_num[i][1]
    ans = str(usable_num[i][0]) + ans
print(''.join(sorted(ans,reverse=True)))

Submission status: Runtime Error

Solution code:
from operator import itemgetter
tik = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[8,7],[6,6]]
dic = {"1":2,"7":3,"4":4,"5":5,"3":5,"2":5,"9":6,"8":7,"6":6}
n,k = map(int, input().split())
x = list(map(int, input().split()))
#print(x)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])
#print(q)
q = sorted(q, key=itemgetter(1), reverse=False)
#print(q)
if (2 not in x or 7 not in x) and 4 in x and 6 in x:
    s = []
    p=0
    t = 0
    while n>0:
        #print(s)
        if n>=q[p][1]:
            n-=q[p][1]
            s.append(str(q[p][0]))
            t = 1
        elif t == 1:
            p+=1
            n+=int(dic[str(s[0])])
            s = s[1:]
        else:
            p+=1
else:

    s = []
    p=0
    t = 0
    while n>0:
        #print(s)
        if n>=q[p][1]:
            n-=q[p][1]
            s.append(str(q[p][0]))
            t = 1
        elif t == 1:
            n+=q[p][1]
            p+=1
            s.pop()
        else:
            p+=1

#print(s)
s.sort()
s=s[::-1]
print(''.join(s))

Submission status: Runtime Error

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

dp = [[] for k in range(n+1)]

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

#dpの初期化
for i in range(m):
    dp[cost[a[i]]]= [a[i]]


for i in range(0,n+1):
    for k in range(m):
        if i > cost[a[k]]:

            tmp = copy.copy(dp[i-cost[a[k]]])
            tmp.append(a[k])
            tmp.sort(reverse = True)
            #print(i,tmp)
            if len(tmp) > len(dp[i]) and len(tmp) != 1:
                dp[i] = tmp
            elif len(tmp) == len(dp[i]) and len(tmp) != 1:
                big = 1
                for s in range(len(tmp)):
                    if tmp[s] < dp[i][s]:
                        big = 0
                if(big):
                    dp[i] = tmp

ans = ""
for cha in dp[n]:
    ans = ans + str(cha)
print(ans)

Submission status: Runtime Error

Solution code:
def greedy(N, M):
    """
    20      マッチの本数
    3 7 8 4 使える数
    """
    pass

def main():
    r = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    #    -  1  2  3  4  5  6  7  8  9

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

    rate = [a/r[a] for a in A]
    rate.sort()

    memo = {} #  N : int

    def greedy(N): # int -> [char]
        """
        """
        #print("ENTER greedy(N=%s)" % N, A, N in memo)
        if N in memo:
            return memo[N]
        M = 0
        result = None
        for a in A:
            #print("  greedy(N=%s) a=%s, M=%s" % (N, a, M))
            if r[a] > N:
                continue
            elif r[a] == N:
                n = a
            else:
                g = greedy(N - r[a])
                if g is None:
                    continue
                n = int(
                        "".join(sorted(list(str(g)) +[str(a)], reverse=True))
                    )
            if M < n:
                result = n
                M = n
        if result is None:
            memo[N] = None
        memo[N] = result
        return result

    answer = greedy(N)
    print(answer)

main()

Submission status: Runtime Error

Solution code:
N,M= map(int,raw_input().split())

A = map(int,raw_input().split())

ans = [0]*9

if 1 in A:
    cnt = 2
    num = 1
elif 7 in A:
    cnt = 3
    num = 7
elif 4 in A:
    cnt = 4
    num = 4
elif 5 in A:
    cnt = 5
    num = 5
elif 3 in A:
    cnt = 5
    num = 3
elif 2 in A:
    cnt = 5
    num = 2
elif 9 in a:
    cnt = 6
    num = 9
elif 6 in a:
    cnt = 6
    num = 6
else:
    cnt = 7
    num = 8

ans[num-1] += N/cnt-1
N -= cnt*(N/cnt-1)

while N != 0:
    flag = False
    if 8 in A and N >= 7 and num != 8:
        ans[7] += 1
        N -= 7
        flag = True
    elif 9 in A and N >= 6 and num != 9:
        ans[8] += 1
        N -= 6
        flag = True
    elif 6 in A and N >= 6 and num != 6:
        ans[5] += 1
        N -= 6
        flag = True
    elif 5 in A and N >= 5 and num != 5:
        ans[4] += 1
        N -= 5
        flag = True
    elif 3 in A and N >= 5 and num != 3:
        ans[2] += 1
        N -= 5
        flag = True
    elif 2 in A and N >= 5 and num != 2:
        ans[1] += 1
        N -= 5
        flag = True
    elif 4 in A and N >= 4 and num != 4:
        ans[3] += 1
        N -= 4
        flag = True
    elif 7 in A and N >= 3 and num != 7:
        ans[6] += 1
        N -= 3
        flag = True
    elif 1 in A and N >= 2 and num != 1:
        ans[0] += 1
        N -= 2
        flag = True

    if flag == False:
        N += cnt
        ans[num-1] -= 1


run = ''
for i in range(9)[::-1]:
    run += str(i+1)*ans[i]

print run

Submission status: Runtime Error

Solution code:
M = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

def max_int(n, a, prefix):
        if n == 0:
                return int(prefix)
        ma = -1
        for v in a:
                if n < M[v]:
                        continue
                ma = max(ma, max_int(n - M[v], a, prefix + str(v)))
        return ma


n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
print(max_int(n, a, ''))

Submission status: Runtime Error

Solution code:
# cook your dish here
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7
    if x == 9:
        return 6
n,m = map(int,input().split())
a = list(map(int,input().split()))
if 2 in a and 3 in a:
    a.remove(2)
    m -=1
if 2 in a and 5 in a:
    a.remove(2)
    m -=1
if 3 in a and 5 in a:
    a.remove(3)
    m -=1
if 6 in a and 9 in a:
    a.remove(6)
    m -=1
for w in range(1,10):
    if n < f(w):
        a.remove(w)
        m -=1
a.sort()

dp = [[0]*(m+1) for i in range(n+1)]


def g(k):
    cand = [0]*(m+1)
    for i in range(m):
        if k - f(a[i])>=0:
            if cand[0] <= dp[k-f(a[i])][0]+1 and dp[k-f(a[i])][0] != 0:
                for r in range(m+1):
                    cand[r] = dp[k-f(a[i])][r]
                cand[0] += 1
                cand[i+1] += 1
    if sum(cand) != 0:
        dp[k] = cand
for i in range(m):
    if f(a[i]) <= n:
        dp[f(a[i])][0] = 1
        dp[f(a[i])][i+1] = 1

for j in range(1,n+1):
    g(j)

ass = ''

for i in range(m):
    for k in range(dp[n][m-i]):
        ass += str(a[m-i-1])
print(ass)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=sorted(map(int,input().split()),key=lambda x:-x)
qq=[1,2,3,4,5,6,7,8,9]
rr=[2,5,5,4,5,6,3,7,6]
q=[]
r=[]
for i in range(m):
    q.append(qq[a[i]-1])
    r.append(rr[a[i]-1])

memo={}
def ff(n,m):
    if (n,m) in memo:
        return memo[(n,m)]
    global q,r
    if n==0:
        return ''
    s=0
    f=0
    for i in range(m):
        if (n-r[i])>=0:
            tmp=ff(n-r[i],m)
            if tmp!=None:
                s=max(s,int(str(q[i])+tmp))
            else:
                f+=1
        else:
            f+=1
    if f==m:
        return None
    memo[(n,m)]=str(s)
    return str(s)
print(ff(n,m))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
math_inf = float('inf')  # the Python of AtCoder is too old

def solve(n, m, a):
    cost = [ math_inf, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]

    small = [ None ] * min(100, n)
    small[0] = 0
    for i in range(1, len(small)):
        small[i] = max([ small[i - cost[a_i]] * 10 + a_i for a_i in a if cost[a_i] <= i ] + [ - math_inf ])

    min_cost, min_cost_a_i = min([ (cost[a_i], a_i) for a_i in a ])
    s = ''
    while n:
        k = (n - min_cost) // min_cost
        c = min_cost_a_i
        k, c = max([ ((n - cost[a_i]) // min_cost, a_i) for a_i in a if n - cost[a_i] >= 100 or small[n - cost[a_i]] >= 0 ])
        n -= cost[c]
        s += str(c)
    return s


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

Submission status: Runtime Error

Solution code:
# cook your dish here
n,m = map(int,input().split())
a = list(map(int,input().split()))
if 2 in a and 3 in a:
    a.remove(2)
    m -=1
if 2 in a and 5 in a:
    a.remove(2)
    m -=1
if 3 in a and 5 in a:
    a.remove(3)
    m -=1
if 6 in a and 9 in a:
    a.remove(6)
    m -=1
a.sort()

dp = [[0]*(m+1) for i in range(n+2)]
def f(x):
    if x == 1:
        return 2
    if x == 2:
        return 5
    if x == 3:
        return 5
    if x == 4:
        return 4
    if x == 5:
        return 5
    if x == 6:
        return 6
    if x == 7:
        return 3
    if x == 8:
        return 7
    if x == 9:
        return 6

def g(k):
    cand = [0]*(m+1)
    for i in range(m):
        if k - f(a[i])>=0:
            if cand[0] <= dp[k-f(a[i])][0]+1 and dp[k-f(a[i])][0] != 0:
                for r in range(m+1):
                    cand[r] = dp[k-f(a[i])][r]
                cand[0] += 1
                cand[i+1] += 1
    if sum(cand) != 0:
        dp[k] = cand
for i in range(m):
    dp[f(a[i])][0] = 1
    dp[f(a[i])][i+1] = 1

for j in range(1,n+1):
    g(j)

ass = ''

for i in range(m):
    for k in range(dp[n][m-i]):
        ass += str(a[m-i-1])
print(ass)

Submission status: Runtime Error

Solution code:
d = [2,5,5,4,5,6,3,7,6]

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

memo = [ "-" for _ in range(N + 1)]

def find(N):
    global memo
    if memo[N] != "-":
        return memo[N]

    mval = ""
    val = ""
    for a in A:
        if d[a - 1] < N:
            val = find(N - d[a - 1])
            if val == "":
                continue
            val = val + str(a)
        elif d[a - 1] == N:
            val = str(a)
        else:
            continue

        if len(mval) < len(val) or (len(mval) == len(val) and mval < val):
            mval = val
    memo[N] = mval
    return memo[N]

m = find(N)
print(m)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
cost = [0,2,5,5,4,5,6,3,7,6]

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

A = sorted(A, reverse=True)

for num in A:
    c = cost[num]
    dp[c] = max(dp[c], num)

for i in range(N+1):
    for num in A:
        c = cost[num]
        if i-c >= 0:
            prev = dp[i - c]
            cur = dp[i]
            if prev > 0:
                prev_str = str(prev)
                if int(prev_str[0]) > num:
                    nxt_str = prev_str + str(num)
                    nxt = int(nxt_str)
                else:
                    nxt_str = str(num) + prev_str
                    nxt = int(nxt_str)
                if nxt > cur:
                    dp[i] = nxt
                # if i == N:
                #     print(cur, prev, nxt)

print(dp[N])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import math

def solve(n, m, a):
    cost = [ math.inf, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]

    small = [ None ] * min(100, n)
    small[0] = 0
    for i in range(1, len(small)):
        small[i] = max([ small[i - cost[a_i]] * 10 + a_i for a_i in a if cost[a_i] <= i ] + [ - math.inf ])

    min_cost, min_cost_a_i = min([ (cost[a_i], a_i) for a_i in a ])
    s = ''
    while n:
        k = (n - min_cost) // min_cost
        c = min_cost_a_i
        k, c = max([ ((n - cost[a_i]) // min_cost, a_i) for a_i in a if n - cost[a_i] >= 100 or small[n - cost[a_i]] >= 0 ])
        n -= cost[c]
        s += str(c)
    return s


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