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:
def search(N, idx):
    global a, M, count

    if N == 0:
        return True
    elif N < 0:
        return False
    elif idx == M:
        return False

    loop = N // a[idx][0]
    for i in range(loop, -1, -1):
        flag = search(N-a[idx][0]*i, idx+1)
        if flag:
            if i:
                count.append([a[idx][1], i])
            return True

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

if 6 in A and 9 in A:
    A.remove(6)

if 5 in A or 3 in A:
    if 2 in A:
        A.remove(2)
    if 5 in A and 3 in A:
        A.remove(3)
M = len(A)
x = [2,5,5,4,5,6,3,7,6]
a = [[x[A[i]-1],i] for i in range(M)]
count = []
a.sort()

search(N, 0)

nums = [[A[count[i][0]], count[i][1]] for i in range(len(count))]

nums.sort(reverse=True)

for i in range(len(nums)):
    print(str(nums[i][0]) * nums[i][1], end='')

Submission status: Wrong Answer

Solution code:
def search(N, idx):
    global a, M, count

    if N == 0:
        return True
    elif N < 0:
        return False
    elif idx == M:
        return False

    loop = N // a[idx][0]
    for i in range(loop, -1, -1):
        flag = search(N-a[idx][0]*i, idx+1)
        if flag:
            if i:
                count.append([a[idx][1], i])
            return True

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
x = [2,5,5,4,5,6,3,7,6]
a = [[x[A[i]-1],i] for i in range(M)]
count = []
a.sort()

search(N, 0)

nums = [[A[count[i][0]], count[i][1]] for i in range(len(count))]

nums.sort(reverse=True)

for i in range(len(nums)):
    print(str(nums[i][0]) * nums[i][1], end='')

Submission status: Wrong Answer

Solution code:
def printing(a_start, a_2, n):

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)

    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
            elif n % a_start[1] == 0:
                break
        else:
            n -= a_3[0][1]
            ans += str(a_3[0][0])

    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Wrong Answer

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
for _ in range(10**5):
    '''for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break'''
    dim -= 1
    if dim <= 0:
        break
print(ans if ans else 0)

Submission status: Wrong Answer

Solution code:
INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
dim = dp[N]
'''while(dim > 0):
    for i in src[::-1]:
        if dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
    dim -= 1'''
print(ans if ans else 0)

Submission status: Wrong Answer

Solution code:
def printing(a_start, a_2, n):

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)

    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
            elif n % a_start[1] == 0:
                break

    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Wrong Answer

Solution code:
def printing(a_start, a_2, n):

    a_3 = []
    mod_list = []
    for i in range(len(a_2)):
        if a_2[i][1] % a_start[1] not in mod_list and a_2[i][1] % a_start[1] != 0:
            a_3.append(a_2[i])
            mod_list.append(a_2[i][1] % a_start[1])
    a_3.sort(key=lambda x: x[1], reverse=True)

    ans = ""
    while n % a_start[1] != 0:
        for i in range(len(a_3)):
            if n % a_start[1] >= a_3[i][1] % a_start[1]:
                n -= a_3[i][1]
                ans += str(a_3[i][0])
                break
            else:
                continue

    ans = ans + str(a_start[0]) * (n // a_start[1])
    ans_list = sorted([ans[i] for i in range(len(ans))], reverse=True)
    print("".join(ans_list))

def main():
    n, m = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)
    number = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    a_list = []
    a_2 = []

    for i in range(m):
        if number[a[i]] not in a_list:
            a_2.append([a[i], number[a[i]]])
            a_list.append(number[a[i]])
    a_2.sort(key=lambda x: x[1])
    a_start = a_2.pop(0)
    printing(a_start, a_2, n)

main()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc118/tasks/abc118_d


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}
    availables = {}
    for k, v in match_dic.items():
        if k in A:
            if k in [9, 8, 7, 5, 4, 1]:
                availables[k] = v
            else:
                if k == 6 and 9 not in A:
                    availables[k] = v
                elif k == 3 and 5 not in A:
                    availables[k] = v
                elif k == 2 and [3, 5] not in A:
                    availables[k] = v
    # print(availables)

    dp = [0 for _ in range(N + 1)]  # i 本マッチを使った時の最大の桁数を格納する
    for i in range(1, N + 1):
        for k, v in availables.items():
            if v > i:
                dp[i] = max(dp[i], dp[i - 1])
            else:
                dp[i] = max(dp[i], dp[i - v] + 1)

    # 戻す
    # print(dp[N])
    nums = []
    i = N
    while i > 0:
        for k, v in availables.items():
            # print("i = {}, k = {}, v = {}".format(i, k, v))
            if dp[i] - 1 == dp[i - v]:
                if dp[i - v] != 0 or (i - v == 0 and dp[i - v] == 0):
                    nums.append(k)
                    i = i - v
                    # print("i = {}, k = {}, v = {}, numd = {}".format(i, k, v, nums))
                    break

    # print(nums)
    nums.sort(key=lambda x: -x)
    print(int(''.join(map(str, nums))))


main()

Submission status: Wrong Answer

Solution code:
import math
def keta(a):
    return int(math.log10(a)+1)

def add(dp,i,before,k): #kは追加する数字
    tens = keta(before)
    if before*10 + k >= k * (10**tens) + before:
        return before*10 + k
    else:
        return k * (10**tens) + before

make = {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(map(int,input().split()))

use = dict()
for i in range(m):
    use[a[i]] = make[a[i]]

dp = [0 for i in range(n+1)]
for i in use:
    if n >= use[i]:
        if dp[use[i]] == 0:
            dp[use[i]] = i
        else:
            if i > dp[use[i]]:
                dp[use[i]] = i

for i in range(1,n+1):
    for k in use:
        if i-use[k] >= 0:
            before = dp[i-use[k]]
            if before != 0:
                temp = add(dp,i,before,k)
                #print(before,temp)
                if temp > dp[i]:
                    dp[i] = temp
print(dp[n])

Submission status: Wrong Answer

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


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [-1 for _ in range(N + 1)]
    dp[0] = 0
    for i in range(1, N + 1):
        for a in A:
            if i < costs[a - 1]:
                continue
            dp[i] = max(dp[i], dp[i - costs[a - 1]] * 10 + a)
    print(dp)


main()

Submission status: Wrong Answer

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] * 100000

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 dp[i] != 0:
            dp[i + items[b]] = max(dp[i] * 10 + b, dp[i + items[b]])
print(dp[N])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  
  if len(digits) == 0:
    return False

  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

    #  replaces = [digits[i][0] for i in idxs]
    #  uppers = [d for d in replaces if d > base_digit]
    #  lowers = [d for d in replaces if d < base_digit]

      num = number[:]

    #  if len(uppers) > 0:
    #    num = uppers + num[len(uppers):]

    #  if len(lowers) > 0:
    #    num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  print(''.join(str(d) for d in number), flush=True)
  return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

    #  replaces = [digits[i][0] for i in idxs]
    #  uppers = [d for d in replaces if d > base_digit]
    #  lowers = [d for d in replaces if d < base_digit]

      num = number[:]

    #  if len(uppers) > 0:
    #    num = uppers + num[len(uppers):]

    #  if len(lowers) > 0:
    #    num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import numpy as np
def num_match(n):
    if n==1:
        return 2
    elif n==2 or n==3 or n==5:
        return 5
    elif n==4:
        return 4
    elif n==6:
        return 6
    elif n==7:
        return 3
    elif n==8:
        return 7
    elif n==9:
        return 6
N,M = map(int, input().split())
A = list(map(int,input().split()))
match = np.array([[a,num_match(a)] for a in A])
sorted_num = match[np.argsort(match[:,0])[::-1]]
sorted_match = match[np.argsort(match[:,1])]
min_num_match = sorted_match[0][1]
max_k = int(N/min_num_match)#一番小さいマッチ数の整数を使える数
rem = N%min_num_match + min_num_match
#rem+match[min_match_index][1]*kがmin以外の組み合わせの合計
ans_exist = False
ans = 0
used_match = []
for k in range(max_k):#remを更新していく？
    if rem in sorted_match[:,1]:
        ans_exist = True
        used_match.append(rem)
        break
    else:
        for n in sorted_match[:,1]:
            if n < rem and n!=min_num_match :
                used_match.append(n)
                rem = rem-n
                break
    if ans_exist:
        #max_k = max_k-k
        break
    else:
        rem = rem + min_num_match
used_match.append(min_num_match)
used_num = []
for um in used_match:
    for i in range(sorted_num.shape[0]):
        if um == sorted_num[i][1]:
            used_num.append(sorted_num[i][0])
            break
base_num=used_num.pop()
sorted_used_num = sorted(used_num,reverse=True)
upper  =[]
lower = []
for s in sorted_used_num:
    if s > base_num:
        upper.append(s)
    else:
        lower.append(s)
lower = sorted(lower)
ans_list = [base_num]*max_k
if len(upper) > 0:
    for i in range(len(upper)):
        ans_list[i] = upper[i]
if len(lower) > 0:
    for j in range(len(lower)):
        ans_list[len(ans_list)-1-j] = lower[j]
ans = ""
for a in ans_list:
    ans = ans + str(a)
ans = int(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
def using(stack):
    return sum([Match[i] * stack[i] for i in range(len(stack))])
def stackStack(stack):
    out = stack[:]
    while len(out) < M:
        r = N - using(out)
        out.append(r // Match[len(out)])
    return out
def update(stack):
    out = stack[:]
    if stack[-1] > 0:
        out[-1] -= 1
        return stackStack(out)
    else:
        out.pop()
        return update(out)
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
MATCH_ALL = [2, 5, 5, 4, 5, 6, 3, 7, 6]
Match = []
for i in [1, 7, 4, 5, 3, 2, 9, 6, 8]:
    if i in A:
        B.append(i)
        Match.append(MATCH_ALL[i - 1])
remain = N
stack = stackStack([])
while remain != 0:
    remain = N - using(stack)
    stack_prev = stack[:]
    stack = update(stack)
B_sort = sorted(B)[::-1]
for b_item in B_sort:
    for j in range(stack_prev[B.index(b_item)]):
        print(b_item, end="")
print("")

Submission status: Wrong Answer

Solution code:
"""
Match Matching
提出 #4299735 を参考に作成
"""


def solve():
	# 初期値の設定
	num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
	N, M = map(int, input().split())
	A = [int(i) for i in input().split()]
	A.sort(reverse=True)
	# 丁度n本で作成できる最大桁数を格納する.
	# 初期値は -inf (丁度使い切ることは不可能) としておく
	dp = [-1 * float("inf")] * (N + 1)

	# 動的計画法で丁度n本のマッチを使うときに作れる最大桁数を計算する
	dp[0] = 0
	for n in range(1, N + 1):
		for a in A:
			if n - num[a] >= 0:
				# マッチがnum[a]本あるときにaが作れるなら,
				# n - num[a]本の時よりも1桁多く作れるはず.
				# これをすべてのAに対して行い、その中で最大となった桁数を求める.
				dp[n] = max(dp[n], dp[n - num[a]] + 1)
	print('各本数丁度で作れる最大桁数')
	print(dp)

	# 回答となる数値を算出
	ans = ''
	for i in range(dp[N]):  # dp[N]桁の数を上位の桁から決定していく
		for a in A:
			# num[a]本使って数を作ったとき,
			# N - num[a] 本で作れる桁数よりも N 本で作れる桁数のほうが1多い場合,
			# numを作っても最終的に作れる数の桁数は変わらない.
			# そのため dp[N] - 1 == dp[N - num[a]] を満たすような最大のAを作り,
			# 作成する数の上位桁に使用すればよい.
			# 同じ本数のマッチを使用する場合はより大きい数を採用する.
			# そのためAはあらかじめ降順にソートしておく.
			# 最初の条件で配列外アクセスを防ぐ
			if N - num[a] > -1 and dp[N] - 1 == dp[N - num[a]]:
				ans += str(a)
				N -= num[a]
				break
		# print('現在の残本数', N, '採用された数', a)

	print(ans)


if __name__ == '__main__':
	solve()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lst = list(map(int,input().split()))
lst = [[lst[i]] for i in range(M)]

import numpy as np
import copy 

lst_weight = copy.deepcopy(lst)
weight_lst = copy.deepcopy(lst)
weight = [2,5,5,4,5,6,3,7,6]

for i in range(M):
    lst_weight[i].append(weight[lst[i][0]-1])
    weight_lst[i].insert(0,weight[lst[i][0]-1])

lst_weight.sort()
weight_lst.sort()

memo = []
ans = -1
index = 0
tmp = N % weight_lst[0][0]
memo = [0 for i in range(M)]

while(True):#重みが同じ数字の最大値をとる
    try:#index out of range
        if weight_lst[0][0] == weight_lst[index+1][0]:
            index += 1
        else:
            break
    except:
        break
memo[index] = N // weight_lst[index][0]

while(True):
    if tmp == 0:#マッチ棒を使い切ったら終了
        break
    else:
        if min(weight_lst[index+1:])[0] <= tmp:
            for i in range(index+1,M):#見送ったインデックス以降から最適な数字がないか探索
                if tmp % weight_lst[i][0] == 0:
                    while(True):#重みが同じ数字の最大値をとる
                        try:#index out of range
                            if weight_lst[i][0] == weight_lst[i+1][0]:
                                i += 1
                            else:
                                break
                        except:
                            break
                    memo[i] = tmp // weight_lst[i][0]
                    tmp -= weight_lst[i][0] * memo[i]
                    break
            else:
                while(True):#重みが同じ数字の最大値をとる
                    try:#index out of range
                        if weight_lst[index+1][0] == weight_lst[index+2][0]:
                            index += 1
                        else:
                            break
                    except:
                        break
                memo[index+1] += 1
                tmp -= weight_lst[index+1][0]
        else:
            for j in range(M-1,-1,-1):#memoを逆順に探索
                if memo[j] != 0:#1以上の値を見つけたら，その数字の採用を見送って（-1），最適解を探索し直す
                    index = j#見送ったインデックス
                    memo[j] -= 1
                    tmp += weight_lst[j][0]

lst_memo = [[weight_lst[i][1]] for i in range(M)]
for i in range(M):
    lst_memo[i].append(memo[i])            

lst_memo.sort()
ans = 0
scope = 1
while(True):
    for i in range(M):
        for j in range(lst_memo[i][1]):
            ans += scope * lst_memo[i][0]
            scope *= 10
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
mtch = {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 = sorted(list(map(int, input().split())))

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

for i in range(N + 1):
    for j in range(N + 1):
        for a in A:
            if dp[i][j] != "-" and j + mtch[a] <= N:
                dp[i + 1][j + mtch[a]] = str(a) + dp[i][j]

for i in range(N, -1, -1):
    if dp[i][N] != "-":
        print("".join(sorted([c for c in dp[i][N]], reverse=True)))
        break

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lst = list(map(int,input().split()))
lst = [[lst[i]] for i in range(M)]

import numpy as np
import copy 

lst_weight = copy.deepcopy(lst)
weight_lst = copy.deepcopy(lst)
weight = [2,5,5,4,5,6,3,7,6]

for i in range(M):
    lst_weight[i].append(weight[lst[i][0]-1])
    weight_lst[i].insert(0,weight[lst[i][0]-1])

lst_weight.sort()
weight_lst.sort()

memo = []
ans = -1
index = 0
tmp = N % weight_lst[0][0]
memo = [0 for i in range(M)]

while(True):#重みが同じ数字の最大値をとる
    try:#index out of range
        if weight_lst[0][0] == weight_lst[index+1][0]:
            index += 1
        else:
            break
    except:
        break
memo[index] = N // weight_lst[index][0]

while(True):
    if tmp == 0:#マッチ棒を使い切ったら終了
        break
    else:
        if min(weight_lst[index+1:])[0] <= tmp:
            for i in range(index+1,M):#見送ったインデックス以降から最適な数字がないか探索
                if tmp % weight_lst[i][0] == 0:
                    while(True):#重みが同じ数字の最大値をとる
                        try:#index out of range
                            if weight_lst[i][0] == weight_lst[i+1][0]:
                                i += 1
                            else:
                                break
                        except:
                            break
                    memo[i] = tmp // weight_lst[i][0]
                    tmp -= weight_lst[i][0] * memo[i]
                    break
            else:
                memo[index+1] += 1
                tmp -= weight_lst[index+1][0]
        else:
            for j in range(M-1,-1,-1):#memoを逆順に探索
                if memo[j] != 0:#1以上の値を見つけたら，その数字の採用を見送って（-1），最適解を探索し直す
                    index = j#見送ったインデックス
                    memo[j] -= 1
                    tmp += weight_lst[j][0]

lst_memo = [[weight_lst[i][1]] for i in range(M)]
for i in range(M):
    lst_memo[i].append(memo[i])            

lst_memo.sort()
ans = 0
scope = 1
while(True):
    for i in range(M):
        for j in range(lst_memo[i][1]):
            ans += scope * lst_memo[i][0]
            scope *= 10
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = sorted(map(int, input().split()))[::-1]
c = [0,2,5,5,4,5,6,3,7,6]
dp = {}
def dfs(n, i=0):
    if (n,i) in dp:
        return dp[n,i]
    if n<0 or i==len(a):
        return -1
    if n==0:
        return 0
    dp[n,i] = dfs(n, i+1)
    v = dfs(n-c[a[i]], i)
    if v == 0:
        v = a[i]
    elif v > 0:
        v = int(str(a[i])+str(v))
    dp[n,i] = max(dp[n,i], v)
    return dp[n,i]
i = min(a, key=lambda x: c[x])
q, r = divmod(n, c[i])
while 1:
    r += c[i]
    q -= 1
    v = dfs(r)
    if v > 0:
        break
print(''.join(sorted(str(v)+str(i)*q)[::-1]))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = sorted([i for i in input().split()], reverse=True)

# dp[i] = i本使ってできる最大の数

def mx(a, b):
    if len(a) != len(b):
        if len(a) > len(b):
            return a
        else:
            return b
    return max(a, b)

# xを作るために使うマッチの本数
h = {'1':2, '2':5, '3':5, '4':4, '5':5, '6':6, '7':3, '8':7, '9':6}

dp = [''] * (N + 1)
dp[0] = ' '

for i in range(N + 1):
    for a in A:
        if i - h[a] < 0: continue
        dp[i] = mx(dp[i-h[a]] + a, dp[i])

print(dp[N])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lst = list(map(int,input().split()))
lst = [[lst[i]] for i in range(M)]

import numpy as np
import copy 

lst_weight = copy.deepcopy(lst)
weight_lst = copy.deepcopy(lst)
weight = [2,5,5,4,5,6,3,7,6]

for i in range(M):
    lst_weight[i].append(weight[lst[i][0]-1])
    weight_lst[i].insert(0,weight[lst[i][0]-1])

lst_weight.sort()
weight_lst.sort()

memo = []
ans = -1
index = 0
tmp = N % weight_lst[0][0]
memo = [0 for i in range(M)]
memo[0] = N // weight_lst[0][0]

while(True):
    if tmp == 0:#マッチ棒を使い切ったら終了
        break
    else:
        if min(weight_lst[index+1:])[0] <= tmp:
            for i in range(1,M):#見送ったインデックス以降から最適な数字がないか探索
                if tmp % weight_lst[i][0] == 0:
                    while(True):#重みが同じ数字の最大値をとる
                        try:#index out of range
                            if weight_lst[i][0] == weight_lst[i+1][0]:
                                i += 1
                            else:
                                break
                        except:
                            break
                    memo[i] = tmp // weight_lst[i][0]
                    tmp -= weight_lst[i][0] * memo[i]
                    break
            else:
                memo[index+1] += 1
                tmp -= weight_lst[index+1][0]
        else:
            for j in range(M-1,-1,-1):#memoを逆順に探索
                if memo[j] != 0:#1以上の値を見つけたら，その数字の採用を見送って（-1），最適解を探索し直す
                    index = j#見送ったインデックス
                    memo[j] -= 1
                    tmp += weight_lst[j][0]

weight_memo = [[weight_lst[i][1]] for i in range(M)]
for i in range(M):
    weight_memo[i].append(memo[i])            

weight_memo.sort()
ans = 0
scope = 1
while(True):
    for i in range(M):
        for j in range(weight_memo[i][1]):
            ans += scope * weight_memo[i][0]
            scope *= 10
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [i for i in input().split()]

# dp[i] = i本使ってできる最大の数

def mx(a, b):
    if len(a) != len(b):
        if len(a) > len(b):
            return a
        else:
            return b
    return max(a, b)

# xを作るために使うマッチの本数
h = {'1':2, '2':5, '3':5, '4':4, '5':5, '6':6, '7':3, '8':7, '9':6}


dp = [''] * (N + 1)
dp[0] = ' '

for i in range(N + 1):
    for a in A:
        if i - h[a] < 0: continue
        dp[i] = mx(dp[i-h[a]] + a, dp[i])

print(dp[N])

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lst = list(map(int,input().split()))
lst = [[lst[i]] for i in range(M)]

import numpy as np
import copy 

lst_weight = copy.deepcopy(lst)
weight_lst = copy.deepcopy(lst)
weight = [2,5,5,4,5,6,3,7,6]

for i in range(M):
    lst_weight[i].append(weight[lst[i][0]-1])
    weight_lst[i].insert(0,weight[lst[i][0]-1])

lst_weight.sort()
weight_lst.sort()

memo = []
ans = -1
index = 0
tmp = N % weight_lst[0][0]
memo = [0 for i in range(M)]
memo[0] = N // weight_lst[0][0]

while(True):
    if tmp == 0:#マッチ棒を使い切ったら終了
        break
    else:
        if min(weight_lst[index+1:])[0] <= tmp:
            for i in range(1,M):#見送ったインデックス以降から最適な数字がないか探索
                if tmp % weight_lst[i][0] == 0:
                    memo[i] = tmp // weight_lst[i][0]
                    tmp -= weight_lst[i][0] * memo[i]
                    break
            else:
                memo[index+1] += 1
                tmp -= weight_lst[index+1][0]
        else:
            for j in range(M-1,-1,-1):#memoを逆順に探索
                if memo[j] != 0:#1以上の値を見つけたら，その数字の採用を見送って（-1），最適解を探索し直す
                    index = j#見送ったインデックス
                    memo[j] -= 1
                    tmp += weight_lst[j][0]

weight_memo = [[weight_lst[i][1]] for i in range(M)]
for i in range(M):
    weight_memo[i].append(memo[i])            

weight_memo.sort()
ans = 0
scope = 1
while(True):
    for i in range(M):
        for j in range(weight_memo[i][1]):
            ans += scope * weight_memo[i][0]
            scope *= 10
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
dp = [0] * (n+1)
for i in range(1, n+1):
    for j in a:
        cost_j = int("0255456376"[j])
        if i- cost_j >= 0:
            dp[i] = max(dp[i], j+dp[i-cost_j]*10)
print(dp[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]  # マッチ棒の本数との変換
f = [0] + [0] * 10000  # DP

# マッチ棒の本数分だけ回す
for i in range(n):
    # 入力の1番目(k)は不必要
    i += 1
    for x in a:
        # 数字が大きいほうが良いから全探索
        # ソートしても出来るけれど作るの面倒

        o = c[x]  # マッチ棒の本数に変換

        if i - o >= 0:  # マッチ棒の上限を超えないように判定
            # マッチ棒の本数分だけ減らして桁を繰り上げて足す
            f[i] = max(f[i], f[i - o] * 10 + x)

print(f[n])