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:
# -*- coding: utf-8 -*-
def  inpl(): return list(map(int, input().split()))
N, M = inpl()
A = sorted(inpl())
cost = [1e9, 2, 5, 5, 4, 5, 6, 3, 7, 6]
mincost = min([cost[a] for a in A])
maxcost = max([cost[a] for a in A])

DP = [0]*N
for a in A:
    if N - cost[a] >= 0:
        DP[N-cost[a]] = a

ans = DP[0]
for j in range(N//2 + 1):
    DP2 = [0]*N
    for i in range(max(0, N-maxcost*(j+1)), N-mincost*j):
        v = DP[i]
        if v == 0:
            continue
        for a in A:
            nk = i - cost[a]
            if nk >= 0:
                DP2[nk] = max(DP2[nk], 10*v + a)
    ans = max(ans, DP2[0])
    DP = DP2
    if sum(SP) == 0:
        break

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input().split())
l = list(map(int, raw_input().split()))
dic = dict(zip(range(1,10),(2,5,5,4,5,6,3,7,6)))
usenum = list(l)
if 5 in set(l):
    if 2 in set(l):
        usenum.remove(2)
    if 3 in set(l):
        usenum.remove(3)
    del dic[2]
    del dic[3]
elif 3 in set(usenum):
        if 2 in set(l):
            usenum.remove(2)
        del dic[2]
        del dic[5]
elif 2 in set(usenum):
    del dic[3]
    del dic[5]
else:
    del dic[2]
    del dic[3]
    del dic[5]

cid = dict([[v,k] for k,v in dic.items()])
usemtch = list(set(map(lambda i: dic[i],usenum)))
res = []
cid = dict([[v,k] for k,v in dic.items()])
usemtch = list(set(map(lambda i: dic[i],usenum)))
res = []

while True:
    if n < min(usemtch):
        break
    else:
        min_use = min(usemtch)
        mtch_count = n/min_use
        n = n - mtch_count*min_use
        res.append([cid[min_use]]*mtch_count)
        usemtch.remove(min_use)
        usemtch = sorted(usemtch)

res = sum(res,[])
usemtch = filter(lambda x: x <= n+min_use, usemtch)
if len(usemtch) >= 1:
    res.remove(cid[min_use])
    res.append(cid[max(usemtch)])
res = int("".join(map(str,sorted(res, reverse=True))))
print(res)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
can_cost = sorted([cost[a] for a in A])
D = {}
for a in A:
    c = cost[a]
    D[c] = max(a, D.setdefault(c, -1))

min_cost = can_cost[0]
min_cost_num = D[min_cost]


def f2(v, l, num):
    L = list(str(v))
    min_cost = cost[int(num)]
    num = D.setdefault(min_cost + l, -1)
    if num == -1:
        return -1

    min_cost_num = D[min_cost]
    L[L.index(str(min_cost_num))] = str(num)
    L.sort(reverse=True)
    return int("".join(L))


def f(v, l):
    L = list(str(v))
    set_L = set(L)
    L2 = [f2(v, l, num) for num in set_L]
    return max(L2)

def g(K, r)

    temp = int("".join([str(min_cost_num)] * K))
    dp = [[-1 for _ in range(min(r, K) + 1)] for __ in range(r + 1)]
    dp[0][0] = temp

    for k in range(min(r, K)):
        for n in range(r):
            v = dp[n][k]
            if v == -1:
                continue
            for l in range(1, r - n + 1):
                dp[n + l][k + 1] = max(dp[n + l][k + 1], f(v, l))
    return max(dp[r])

K = N // min_cost
r = N - K * min_cost
res = g(K, r)
if g(K, r) == -1:
    res = g(K - 1, r + min_cost)
print(res)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N, _ = map(int, input().split())
A = list(map(int, input().split()))
table = defaultdict(int)
for i, cost in zip(range(1, 10), [2,5,5,4,5,6,3,7,6]):
    if i in A:
        table[cost] = max(table[cost], i)
candy = sorted(table)
res = defaultdict(int)
for k in range(len(candy)):
    bits = 1
    for i in candy[k + 1:]:
        bits = bits | (bits << i)
    for i in range(1, len(format(bits, 'b'))):
        if bits & (1 << i):
            if N - i >= 0 and (N - i) % candy[k] == 0:
                res[table[candy[k]]] = ((N - i) // candy[k])
                N = i
                break
    if N == candy[k]:
        res[table[candy[k]]] = 1
        N = 0
#swap
for _ in range(2):
    for candy1 in candy:
        for candy2 in candy:
            for candya in candy:
                sum1 = candy1 + candy2 + candya
                for candy3 in candy:
                    for candy4 in candy:
                        for candyb in candy:
                            sum2 = candy3 + candy4 + candyb
                            if sum1 == sum2:
                                x = sorted([table[candy1], table[candy2], table[candya]], reverse=True)
                                y = sorted([table[candy3], table[candy4], table[candyb]], reverse=True)
                                if x < y:
                                    a, b, ab = x
                                    c, d, cd = y
                                    t = min(res[a], res[b], res[ab])
                                    if len({res[a], res[b], res[ab]}) == 1:
                                        t = res[a] // 3
                                    elif res[a] == res[b]:
                                        t = min(res[a] // 2, res[c])
                                    elif res[b] == res[c]:
                                        t = min(res[a], res[c]//2)
                                    elif res[c] == res[a]:
                                        t = min(res[a]//2, res[b])
                                    res[a] -= t
                                    res[b] -= t
                                    res[ab] -= t
                                    res[c] += t
                                    res[d] += t
                                    res[cd] += t
for _ in range(2):
    for candy1 in candy:
        for candy2 in candy:
            sum1 = candy1 + candy2
            for candy3 in candy:
                for candy4 in candy:
                    sum2 = candy3 + candy4
                    if sum1 == sum2:
                        x = sorted([table[candy1], table[candy2]], reverse=True)
                        y = sorted([table[candy3], table[candy4]], reverse=True)
                        if x < y:
                            a, b = x
                            c, d = y
                            t = min(res[a], res[b])
                            if res[a] == res[b]:
                                t = res[a] // 2
                            res[a] -= t
                            res[b] -= t
                            res[c] += t
                            res[d] += t
tmp = []
for i, d in res.items():
    tmp += [i] * d
print(''.join(map(str, sorted(tmp, reverse=True))))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
Match = [2, 5, 5, 4, 5, 6, 3, 7, 6]

MM = []
for i in range(0, M):
    MM.append(Match[A[i] - 1])

MMM = np.array(MM)
MMMM = MMM.argsort()

AA = i // MMM[MMMM[0]] + 1

for i in range(0, N):
    if (N - i) % MMM[MMMM[0]] == 0 and i % MMM[MMMM[1]] == 0:
        print(str(A[MMMM[1]]) * (i // MMM[MMMM[1]]) + str(A[MMMM[0]]) * ((N - i) // MMM[MMMM[0]]))
        sys.exit()

for i in range(0, N)[::-1]:
    for j in range(0, N - i + 1)[::-1]:
        if i % MMM[MMMM[0]] == 0 and j % MMM[MMMM[1]] == 0 and (N - i - j) % MMM[MMMM[1]]:
            print(str(A[MMMM[2]]) * ((N - i - j) // MMM[MMMM[1]]) + str(A[MMMM[1]]) * (j // MMM[MMMM[1]]) + str(A[MMMM[0]]) * (i // MMM[MMMM[0]]))
            sys.exit()

Submission status: Runtime Error

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

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

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

for a in A:
  _dict[num_matches[a]]=_dict.get(num_matches[a],[]) + [a]

print(_dict)

memo = [None for _ in range(N+1)] # return memo[N]
# Nほんのマッチを使って作れる整数の最大値．（作れなければ0）

def max_int_with_match(n):
  if memo[n]:
    return memo[n]
  
  if n in _dict.keys():
    memo[n] = max(max(_dict[n]),
                  max(map(lambda x: max(_dict[x]) + 10 * max_int_with_match(n-x), _dict.keys()
                         )
                     )
                 )
  	return memo[n]
  
  if n < min(_dict.keys()):
    memo[n] = 0
    return memo[n]
  
  memo[n] = max(map(lambda x: max(_dict[x]) + 10 * max_int_with_match(n-x), _dict.keys()))
  return memo[n]

print(max_int_with_match(N))

Submission status: Runtime Error

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())|	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import collections
import math
from functools import reduce

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

for ind in range(M):
  m_dic ={
  1:2,
  2:5,
  3:5,
  4:4,
  5:5,
  6:6,
  7:3,
  8:7,
  9:6
  }

  ans_d = {}
  use_dic = {}

  for A_i in A:
      use_dic[A_i] = m_dic[A_i]

  sl = sorted(use_dic.items(), key=lambda x: x[1])
  # print(sl)
  use_m = sl[ind]
  max_len = int(N/use_m[1])
  tmp_use_mk = use_m[0]
  tmp_use_m = use_m[1]
  amari = N%use_m[1]
  # ans = ans + str(use_m[0])*max_len
  ans_d[use_m[0]] = max_len
  del use_dic[sl[0][0]]

  flag = False
  while(amari!=0):
    sl = sorted(use_dic.items(), key=lambda x: x[1])[::-1]
    use_m = sl[0]
    if use_m[1]-tmp_use_m>amari:
      del use_dic[use_m[0]]
      if len(use_dic) == 0:
        flag = True
        break
      continue
    max_len = int(amari/(use_m[1]-tmp_use_m))
    amari -= max_len*(use_m[1]-tmp_use_m)
    ans_d[tmp_use_mk] -= max_len
    ans_d[use_m[0]] = max_len
    del use_dic[use_m[0]]
    if len(use_dic) == 0:
      flag = True
      break
  if not flag:
      break


k = ""
for i, j in sorted(ans_d.items(), key=lambda x: x[0])[::-1]:
  k = k + str(i)*j
print(k)

Submission status: Runtime Error

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

B = [0] * M
for i in range(M):
    B[i] = c[A[i]]

x = min(B)
value = 0
for i in range(M):
    if B[i] == x:
        value = max(A[i], value)
y = N % x
if y == 0:
    print(str(value) * (N / x))
else:
    k = 10
    for i in range(M):
        if B[i] % x == y:
            if k > B[i]:
                k = B[i]
                l = A[i]
            elif k == B[i]:
                l = max(l, A[i])
    if value > l:
        print(str(value) * ((N - k) // x) + str(l))
    else:
        print(str(l) + str(value) * ((N - k) / x))

Submission status: Runtime Error

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

Num_All={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
Num=list(set([Num_All[a] for a in A]))

Num.sort()
Gyaku={n:0 for n in Num}
for a in A:
    if a>Gyaku[Num_All[a]]:
        Gyaku[Num_All[a]]=a


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


for j in range(len(Num)):
    if dp[Num[j]][0]==0:
        dp[Num[j]]=[1,[[Num[j]]]]
    for i in range(Num[j],N+1):
        if dp[i-Num[j]][0]==0:
            continue
        if dp[i-Num[j]][0]+1>dp[i][0]:
            dp[i]=[dp[i-Num[j]][0]+1,[k+[Num[j]] for k in dp[i-Num[j]][1]]]
        elif dp[i-Num[j]][0]+1==dp[i][0]:
            for k in dp[i-Num[j]][1]:
                dp[i][1].append(k+[Num[j]])
          

Num_koho=dp[N][1]

Koho=[[Gyaku[k] for k in nk] for nk in Num_koho]
Ans_koho=[]
for k in Koho:
    k.sort(reverse=True)
    Ans_koho.append(sum((10**(len(k)-i-1))*k[i] for i in range(len(k))))
    
print max(Ans_koho)

Submission status: Runtime Error

Solution code:
N, M = input().split()
N = int(N)
ori_N = N
M = int(M)
tmp_A = list(map(int, input().split()))
nums = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

new_nums = {}
for i in tmp_A:
    new_nums[i] = nums[i]

nums = {}
for i in new_nums:
    nums[new_nums[i]] = []

for i in new_nums:
    nums[new_nums[i]].append(i)

for i in nums:
    nums[i] = max(nums[i])

my_nums = []
for i in nums:
    my_nums.append(i)
my_nums.sort()
min_my_nums = min(my_nums)
x = 0

best_nums = {}
for i in my_nums:
    best_nums[i] = nums[i]
    for j in my_nums:
        best_nums[i + j] = max(nums[i], nums[j]) * 10 + min(nums[i], nums[j])


while N % min_my_nums != 0:
    for i in best_nums:
        if (N - i) % min_my_nums == 0:
            N = N - i
            new_N = best_nums[i]
            break
max_min = N // min_my_nums
ans = ""
for i in range(N // min_my_nums):
    ans = str(nums[min_my_nums]) + ans
ans = str(new_N) + ans
print(ans)

Submission status: Runtime Error

Solution code:
def inv(x, ava):
    if x == 2:
        if 1 in ava:
            return 1
        else:
            return -1
    if x == 3:
        if 7 in ava:
            return 7
        else:
            return -1
    if x == 4:
        if 4 in ava:
            return 4
        else:
            return -1
    if x == 5:
        if 5 in ava:
            return 5
        if 3 in ava:
            return 3
        if 2 in ava:
            return 2
        else:
            return -1
    if x == 6:
        if 9 in ava:
            return 9
        if 6 in ava:
            return 6
        else:
            return -1
    if x == 7:
        if 8 in ava:
            return 8
        else:
            return -1
n, m = map(int, input().split())
ava = list(map(int, input().split()))
dp = [[] for _ in range(n+1)]
number = [inv(x,ava) for x in range(2,8)]
avapre = []
for i in range(6):
    if number[i] != -1:
        avapre.append(i+2)
avapresort = sorted(key = lambda x: number[x-2], avapre)
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):
    if i < avapre[0]:
        dp[i] = -1
    else:
        dp[i] = -1
        for pre in avapre:
            if i - pre >= 0:
                dp[i] = max(dp[i], dp[i-pre]+1)
i = n
while(i > 0):
    for pre in avapresort:
        if i - pre >= 0 and dp[i] == dp[i-pre] + 1:
            print(number[pre-2], end='')
            i -= pre
            break
print()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
import sys

r = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
rate = [i/r[i] for i in range(1, 10)]
#    -  1  2  3  4  5  6  7  8  9
memo = {} #  N : int

def main():
    N0, _ = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    A = sorted(A, reverse=True)
    #print(N0, A, file=sys.stderr)

    if len(A) == 1:
        a = A[0]
        print(
            "".join(
                [str(a)] * (N0 // r[a])
            )
        )
        return

    def greedy(N): # int -> (int or None)
        #print("greedy(N=%d)" % N)
        if N in memo:
            #print("hit", file=sys.stderr)
            return memo[N]
        M = 0
        result = None
        for a in A:
            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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  r = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)
  n, _ = list(map(int, input().split()))
  ps = list(map(int, input().split()))

  cs = [(p, r[p]) for p in ps]
  cs.sort(key=lambda x: x[1])
  a = []
  s, b = cs[0]

  while n - b > 0:
    a.append(s)
    n -= b

  cs.sort(key=lambda x:-x[0])
  cs = [(p, c - b) for p, c in cs if c != b]

  for i in range(1, len(cs) + 1):
    for ps in itertools.product(range(len(cs)), repeat=i):
      if sum(cs[p][1] for p in ps) == n:
        ds = [cs[p][0] for p in ps]
        break

  uds = [d for d in ds if d >= s]
  lds = [d for d in ds if d < s][::-1]

  a = uds + a[len(uds):]
  a = a[-len(lds):] + lds

  print(''.join(str(v) for v in a), flush=True)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
Matches = {num: c for num, c in zip([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 5, 4, 5, 6, 3, 7, 6])}

memos = {}

def psolve(N, digit, Ms):
    if N == 0:
        return digit
    if N < min([m for m in Ms.values()]):
        return -1
    ans = 0
    if (N, digit) in memos:
        return memos[(N, digit)]

    for (dc, dnum) in sorted([(c, num) for (num, c) in Ms.items()], key=lambda x: -x[0]):
        if digit + str(dnum) > str(dnum) + digit:
            p = psolve(N - dc, digit + str(dnum), Ms)
            if p != -1:
                ans = max(ans, int(p))
        else:
            p = psolve(N - dc, str(dnum) + digit, Ms)
            if p != -1:
                ans = max(ans, int(p))
    memos[(N, digit)] = ans
    return memos[(N, digit)]


def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if num in As}
    return psolve(N, "", Ms)

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    As = list(map(int, input().split(" ")))
    print(solve(N, M, As))

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)
    return ''.join(max(s, t))

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

mini = min(D.keys())

for i in range(1, 5002):
    for j in range(N+1):
        if dp[i][j] == '':
            continue
        for n, s in D.items():
            if j+n > N or j+n > mini*(i+2):
                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:
import copy

n, m = map(int, input().rstrip().split())
number_list = list(map(int, input().rstrip().split()))
number_list.sort()
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
new_match = []
answer = []

for i in number_list:
    new_match.append(match[i-1])


for index in range(m):
    value = new_match[index]
    new_match_tmp = copy.copy(new_match)
    new_match_tmp.remove(value)
    maximum = max(new_match_tmp)
    #商と余りを計算
    quotient = int(n / value)
    remainder = n % value
    answer_tmp = [number_list[index]] * quotient
    #余りがあるなら余りをなくすように組み合わせを考える
    if remainder != 0:
        while True:
            quotient -= 1
            remainder += value
            answer_tmp.pop(0)
            if remainder in new_match:
                answer_tmp.append(number_list[new_match.index(remainder)])
                break
            elif remainder == n:
                answer_tmp = []
                break

    if len(answer_tmp) != 0:
        answer.append(answer_tmp)

answer.sort(key=lambda x:len(x), reverse=True)
ans = reversed(answer[0])

print(*ans, sep='')
print()

Submission status: Runtime Error

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())|	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import collections
import math
from functools import reduce

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

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

ans_d = {}
use_dic = {}

for A_i in A:
  use_dic[A_i] = m_dic[A_i]

for ind in range(M):
  sl = sorted(use_dic.items(), key=lambda x: x[1])
  # print(sl)
  use_m = sl[ind]
  max_len = int(N/use_m[1])
  tmp_use_mk = use_m[0]
  tmp_use_m = use_m[1]
  amari = N%use_m[1]
  # ans = ans + str(use_m[0])*max_len
  ans_d[use_m[0]] = max_len
  del use_dic[sl[0][0]]

  flag = False
  while(amari!=0):
    sl = sorted(use_dic.items(), key=lambda x: x[1])[::-1]
    use_m = sl[0]
    if use_m[1]-tmp_use_m>amari:
      del use_dic[use_m[0]]
      if len(use_dic) == 0:
        flag = True
        break
      continue
    max_len = int(amari/(use_m[1]-tmp_use_m))
    amari -= max_len*(use_m[1]-tmp_use_m)
    ans_d[tmp_use_mk] -= max_len
    ans_d[use_m[0]] = max_len
    del use_dic[use_m[0]]
    if len(use_dic) == 0:
      flag = True
      break
  if not flag:
      break


k = ""
for i, j in sorted(ans_d.items(), key=lambda x: x[0])[::-1]:
  k = k + str(i)*j
print(k)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Feb 16 19:31:10 2019
ABC118D
@author: maezawa
"""

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

nmatch = [2,5,5,4,5,6,3,7,6]
rmatch = list(reversed(nmatch))

a_n = [(ai, nmatch[ai-1]) for ai in a]
a_n.sort(key = lambda x: x[0], reverse=True)
a_n.sort(key = lambda x: x[1])
a_n2 = [ai[1] for ai in a_n]
#print(a_n)

for j in range(1, m):
    number = a_n[0][0]
    n_order = n // a_n[0][1] - j
    rem = n % a_n[0][1] + a_n[0][1]*j
    ans = str(number) * n_order
    
    if rem in a_n2:
        one = a_n[a_n2.index(rem)][0]
        if number > one:
            ans = ans+str(one)
        else:
            ans = str(one)+ans
        break
            
print(ans)

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()))
inf = float("INF")
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    dp[i+q[j][1]] = q[j][0]
                else:dp[i+q[j][1]] = str(dp[i])+str(q[j][0])
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(dp[n])
s.sort()
s = s[::-1]
print(''.join(s))

Submission status: Runtime Error

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

items = {
    1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6
}
dp = [0] * (N + 1)

b_list = []
for a in a_list:
    need = items[a]
    if need <= N:
        dp[need] = a
        b_list.append(a)

M = len(b_list)
b_list.sort()
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != 0:
                cnt = 0
                num = dp[i - items[b]]
                while num > 1:
                    cnt += 1
                    num /= 10
                tmp = max(b * (10 ** cnt) + dp[i - items[b]], dp[i - items[b]] * 10 + b)
                dp[i] = max(tmp, dp[i])
print(dp[N])

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)
    return ''.join(max(s, t))

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

mini = min(D.keys())

for i in range(1, 5002):
    for j in range(N+1):
        if dp[i][j] == '':
            continue
        for n, s in D.items():
            if j+n > N or j+n > mini * i + mini:
                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:
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()))
inf = float("INF")
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n+10:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    dp[i+q[j][1]] = q[j][0]
                else:dp[i+q[j][1]] = str(dp[i])+str(q[j][0])
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(dp[n])
s.sort()
s = s[::-1]
print(''.join(s))

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())

    A = list(map(int, input().split()))  # 使っていい数字

    match_dic = {9: 6, 8: 7, 7: 3, 6: 6, 5: 5, 4: 4, 3: 5, 2: 5, 1: 2}
    available_dic = {k: v for k, v in match_dic.items() if k in A }
    availables = sorted(available_dic.items(), key=lambda x: x[1])

    def dfs(cost, nums):
        if cost == 0:
            nums.sort(key=lambda x: -x)
            return int(''.join(map(str, nums)))

        candidates = [dfs(cost - avs[1], nums + [avs[0]]) for avs in availables if cost >= avs[1]]
        if len(candidates) == 0:
            return 0
        else:
            return max(candidates)

    print(dfs(N, []))


main()

Submission status: Runtime Error

Solution code:
n_dic = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
n,m = map(int,input().split())
l = list(map(int,input().split()))
dic = {}
for i in l:
    if n_dic[i] not in dic or dic[n_dic[i]] < i:
        dic[n_dic[i]] = i
if n % min(dic) == 0:
    ans = str(dic[min(dic)]) * int(n / min(dic))
else:
    ans = str(dic[min(dic)]) * int(n / min(dic))
    sub = n - min(dic) * int(n / min(dic))
    ind = 0
    while sub > 0 and ind < len(ans):
        dif = 0
        v = int(ans[ind])
        for i in range(min(dic) + 1,min(dic) + sub + 1):
            if i in dic and int(dic[i]) > v:
                v = dic[i]
                dif = i - min(dic)
        sub -= dif
        ans = ans[:ind] + str(v) + ans[ind+1:]
        ind += 1
ind = 1
while sub != 0:
    for i in range(sub):
        if min(dic) + sub - i in dic:
            ans = ans[:-ind] + str(dic[min(dic) + sub - i]) + ans[len(ans) - ind + 1:]
            sub -= sub-i
            break
    ind += 1
print(ans)

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()))
inf = float("INF")
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n+10000000:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    dp[i+q[j][1]] = q[j][0]
                else:dp[i+q[j][1]] = str(dp[i])+str(q[j][0])
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(dp[n])
s.sort()
s = s[::-1]
print(''.join(s))

Submission status: Runtime Error

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

dp = [0] * (N+1)

for i in A:
    if dp[cost[i-1]] == 0:
        dp[cost[i-1]] = i
    else:
        dp[cost[i-1]] = min(i, dp[cost[i-1]])

for i in range(1, N+1):
    for j in A:
        if i - cost[j-1] >= 0:
            if not dp[i-cost[j-1]] == 0:
                if dp[i] == 0:
                    dp[i] = int("".join(sorted(str(dp[i-cost[j-1]])+str(j), reverse=True)))
                else:
                    dp[i] = max(int("".join(sorted(str(dp[i-cost[j-1]])+str(j), reverse=True))), dp[i])

print(dp[N])

Submission status: Runtime Error

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

Num_All={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
Num=list(set([Num_All[a] for a in A]))

Num.sort()
Gyaku={n:0 for n in Num}
for a in A:
    if a>Gyaku[Num_All[a]]:
        Gyaku[Num_All[a]]=a


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


for j in range(len(Num)):
    if dp[Num[j]][0]==0:
        dp[Num[j]]=[1,[[Num[j]]]]
    for i in range(Num[j]+1,N+1):
        if dp[i-Num[j]][0]==0:
            continue
        if dp[i-Num[j]][0]+1>dp[i][0]:
            dp[i]=[dp[i-Num[j]][0]+1,[k+[Num[j]] for k in dp[i-Num[j]][1]]]
        elif dp[i-Num[j]][0]+1==dp[i][0]:
            for k in dp[i-Num[j]][1]:
                dp[i][1].append(k+[Num[j]])
          

Num_koho=dp[N][1]

Koho=[[Gyaku[k] for k in nk] for nk in Num_koho]
Ans_koho=[]
for k in Koho:
    k.sort(reverse=True)
    Ans_koho.append(sum((10**(len(k)-i-1))*k[i] for i in range(len(k))))
    
print max(Ans_koho)

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)
    return ''.join(max(s, t))

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

mini = min(D.keys())

for i in range(1, 5002):
    for j in range(N+1):
        if dp[i][j] == '':
            continue
        for n, s in D.items():
            if j+n > N or j+n > mini * i + 10:
                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))