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:
import math

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

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

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

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

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

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

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

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

    #以下余りを調整

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

    #1桁ずつ値を変更し、あまりを0にできるか調査
    #調整は一番遅くて1ずつだから余りの値だけループを回せばよい
    for i in range(1,amari+1):

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

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

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

          if nokori < 0:
            break

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

      #候補があればループを抜ける
      if len(kouho) != 0:
        break
        
    if len(kouho) == 0:
      break

    #候補から値の大きいものを抜き出す

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

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

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

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

Submission status: Wrong Answer

Solution code:
import math

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

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

if 2 in a:
  if 3 in a or 5 in a:
    a.remove(2)
    m -= 1

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

exist = [i for i in set if i[0] in a]

num = 0
keta = 0
for i in exist:
  if i[0] > num and n//i[1] >= keta:
    num = i[0]
    honsu = i[1]
    keta = n//honsu
    amari = n%honsu
    break

if amari == 0:
  ans = [str(num)]*keta
  print(ans)
  exit()

exist_yet = [i for i in exist]
m -= 1
for l in range(1,keta+1):
  exist_tmp = [i for i in exist if i[0] != num]
  bit = math.ceil(math.log2(m))
  for i in range(1,keta+1):
    kouho = []
    for j in range((2**bit)**i):
      nokori = amari + honsu * i
      change = []
      for k in range(i):
        tmp = (j >> k*bit) & (2**bit-1)
        if tmp >= m:
          continue
        nokori -= exist_tmp[tmp][1]
        change.append(exist_tmp[tmp][0])
        if nokori < 0:
          break
      if nokori == 0:
        kouho.append(change)
    if len(kouho) != 0:
      break
  if len(kouho) != 0:
    break
  else:
    exist_yet = [i for i in exist_yet if i[0] != num]
    while True:
      keta -= 1
      num = 0
      for i in exist_yet:
        if i[0] > num and n//i[1] >= keta:
          num = i[0]
          honsu = i[1]
          amari = n%honsu
          break
      if num > 0:
        break

kouho = [sorted(i,reverse=True) for i in kouho]
kouho_tmp = []
for i in kouho:
  if i not in kouho_tmp:
    kouho_tmp.append(i)
kouho = kouho_tmp
kouho.sort(reverse=True)

if len(kouho) > 1:
  for i in range(len(kouho[0])):
    max_num = 0
    for j in range(len(kouho)):
      if kouho[j][i] > max_num:
        max_num = kouho[j][i]
    kouho = [k for k in kouho if k[i] == max_num]
    if len(kouho) == 1:
      break
      
ans = [num]*(keta-len(kouho[0])) + kouho[0]
ans.sort(reverse=True)

ans_txt = ''
for i in ans:
  ans_txt += str(i)
print(ans_txt)

Submission status: Wrong Answer

Solution code:
import math

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

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

if 2 in a:
  if [3,5] in a:
    a.remove(2)
    m -= 1

if 3 in a:
  if 5 in a:
    a.remove(3)
    m -= 1
  
if 6 in a:
  if 9 in a:
    a.remove(6)
    m -= 1
  
exist = [i for i in set if i[0] in a]

num = 0
keta = 0
for i in exist:
  if i[0] > num and n//i[1] >= keta:
    num = i[0]
    honsu = i[1]
    keta = n//honsu
    amari = n%honsu
    break

if amari == 0:
  ans = [str(num)]*keta
  print(ans)
  exit()

exist_yet = [i for i in exist]
m -= 1
for l in range(1,keta+1):
  exist_tmp = [i for i in exist if i[0] != num]
  bit = math.ceil(math.log2(m))
  for i in range(1,keta+1):
    kouho = []
    for j in range((2**bit)**i):
      nokori = amari + honsu * i
      change = []
      for k in range(i):
        tmp = (j >> k*bit) & (2**bit-1)
        if tmp >= m:
          continue
        nokori -= exist_tmp[tmp][1]
        change.append(exist_tmp[tmp][0])
        if nokori < 0:
          break
      if nokori == 0:
        kouho.append(change)
    if len(kouho) != 0:
      break
  if len(kouho) != 0:
    break
  else:
    exist_yet = [i for i in exist_yet if i[0] != num]
    keta -= 1
    num = 0
    for i in exist:
      if i[0] > num and n//i[1] >= keta:
        num = i[0]
        honsu = i[1]
        amari = n%honsu
        break

kouho = [sorted(i,reverse=True) for i in kouho]
kouho_tmp = []
for i in kouho:
  if i not in kouho_tmp:
    kouho_tmp.append(i)
kouho = kouho_tmp
kouho.sort(reverse=True)

if len(kouho) > 1:
  for i in range(len(kouho[0])):
    max_num = 0
    for j in range(len(kouho)):
      if kouho[j][i] > max_num:
        max_num = kouho[j][i]
    kouho = [k for k in kouho if k[i] == max_num]
    if len(kouho) == 1:
      break
      
ans = [num]*(keta-len(kouho[0])) + kouho[0]
ans.sort(reverse=True)

ans_txt = ''
for i in ans:
  ans_txt += str(i)
print(ans_txt)

Submission status: Wrong Answer

Solution code:
import math

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

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

exist = [i for i in set if i[0] in a] 

num = 0
keta = 0
for i in exist:
  if i[0] > num and n//i[1] >= keta:
    num = i[0]
    honsu = i[1]
    keta = n//honsu
    amari = n%honsu
    break

bit = math.ceil(math.log2(m))
for i in range(1,keta+1):
  kouho = []
  for j in range((2**bit)**i):
    nokori = amari + honsu * i
    change = []
    for k in range(i):
      tmp = (j >> k*bit) & (2**bit-1)
      if tmp >= m:
        continue
      nokori -= exist[tmp][1]
      change.append(exist[tmp][0])
      if nokori < 0:
        break
    if nokori == 0:
      kouho.append(change)
  if len(kouho) != 0:
    break


kouho = [sorted(i,reverse=True) for i in kouho]
kouho_tmp = []
for i in kouho:
  if i not in kouho_tmp:
    kouho_tmp.append(i)
kouho = kouho_tmp
kouho.sort(reverse=True)

if len(kouho) > 1:
  for i in range(len(kouho[0])):
    max_num = 0
    for j in range(len(kouho)):
      if kouho[j][i] > max_num:
        max_num = kouho[j][i]
    kouho = [k for k in kouho if k[i] == max_num]
    if len(kouho) == 1:
      break
      
ans = [num]*(keta-len(kouho[0])) + kouho[0]
ans.sort(reverse=True)

ans_txt = ''
for i in ans:
  ans_txt += str(i)
print(ans_txt)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
Match = [-1,2,5,5,4,5,6,3,7,6 ]
DD = [(Match[i],i) for i in A]
CC = []
DD.append((99,0))
for i in range(len(DD)-1):
  if DD[i][0] == DD[i+1][0]:
    continue
  else:
    CC.append(DD[i])
CC.sort()
S = ""
D  = N
if D > 24:
  D = N - 24
  S = str(CC[0][1])*(D//CC[0][0])
  N = 24 + (D % CC[0][0])

def solve(N):
	if N == 0:
		return -1
	else:
		res = -2
	for i in CC:
		if N-i[0] < 0:
			continue
		ns = solve(N-i[0])
		if ns == -1:
			res = max(res,max(int(str(i[1])),int(str(i[1]))))
		elif ns == -2:
			continue
		else:
			res = max(res,max(int(str(i[1])+str(ns)),int(str(ns)+str(i[1]))))
	return res
d = solve(N)
print(str(solve(N))+S)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = [2,5,5,4,5,6,3,7,6]
A = list(map(int, input().split()))
mina = [0,9]
for a in A:
    if l[a-1] < mina[1]:
        mina[0] = a
        mina[1] = l[a-1]
    elif l[a-1] == mina[1] and mina[0] < a:
        mina[0] = a
    else:
        continue
keta = n // mina[1]
k = keta
A.sort(reverse=True)
anslist = [mina[0]]*(keta)
for i in range(keta):
    k -= 1
    for a in A:
        if n-l[a-1]>=k*mina[1]:
            n -=l[a-1]
            anslist[i]=a
            break
        else:
            continue
ans = list(map(str,anslist))
print("".join(ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

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

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

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

for i in range(N + 1):
        for a in A:
                if i + need[a] <= N:
                        dp[i + need[a]] = max(dp[i + need[a]], dp[i] * 10 + a)

print(dp)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

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

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

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

for num in A:
        required = need[num]

        for i in range(N - required + 1):
                if dp[i] == -1:
                        continue
                
                dp[i + required] = max(dp[i + required], dp[i] * 10 + num)

print(dp[-1])

Submission status: Wrong Answer

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

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

def sort_str(s):
    ret = list(s)
    ret.sort(reverse=True)
    return ''.join(ret)

def is_greater(a, b):
    if len(a) > len(b):
        return True
    elif len(a) < len(b):
        return False
    for i in range(len(a)):
        if a[i] > b[i]:
            return True
        else:
            return False
    return False

def _solve(n: int, m: int, A: "List[int]"):
    dp = [None] * (n + 1)
    dp[0] = ''
    for c in A:
        for i in range(n + 1):
            if i - a[c] >= 0 and dp[i - a[c]] is not None:
                tmp = sort_str(dp[i - a[c]] + str(c))
                if dp[i] is None or is_greater(tmp, dp[i]):
                    dp[i] = tmp
        #print(dp)
    print(dp[n])
    return

def solve(n: int, m: int, A: "List[int]"):
    dp = [-1] * (n + 1)
    memo = ['' for _ in range(n + 1)]
    dp[0] = 0
    A.sort(reverse=True)
    for c in A:
        for i in range(n + 1):
            if i - a[c] >= 0 and dp[i - a[c]] >= 0:
                if dp[i] <= dp[i - a[c]] + 1:
                    dp[i] = dp[i - a[c]] + 1
                    memo[i] = memo[i - a[c]] + str(c)
        #print(dp)
        #print(memo)
    ret = list(memo[n])
    ret.sort(reverse=True)
    ret = ''.join(ret)
    print(ret)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

def sort_str(s):
    ret = list(s)
    ret.sort(reverse=True)
    return ''.join(ret)

def is_greater(a, b):
    if len(a) > len(b):
        return True
    elif len(a) < len(b):
        return False
    for i in range(len(a)):
        if a[i] > b[i]:
            return True
        else:
            return False
    return False

def solve(n: int, m: int, A: "List[int]"):
    dp = [None] * (n + 1)
    dp[0] = ''
    for c in A:
        for i in range(n + 1):
            if i - a[c] >= 0 and dp[i - a[c]] is not None:
                tmp = sort_str(dp[i - a[c]] + str(c))
                if dp[i] is None or is_greater(tmp, dp[i]):
                    dp[i] = tmp
        #print(dp)
    print(dp[n])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
NUMS = np.array([0,2,5,5,4,5,6,3,7,6])

def get_usenum(available):
    min_match_nums = (NUMS == min(NUMS[available]))
    vals_has_min_match_nums = min_match_nums * np.arange(10)
    return max(vals_has_min_match_nums[available])

def solve(target_num, available):
    if len(available) == 0:
        return None
    use_num = get_usenum(available)
    max_digit = target_num // NUMS[use_num]
    if target_num % NUMS[use_num] == 0:
        return [str(use_num)] * max_digit
    else:
        available_new = available[(NUMS != NUMS[use_num])[available]]
        for digit in range(max_digit - 1, -1, -1):
            ret = solve(target_num - NUMS[use_num] * digit,available_new)
            if ret is not None:
                use_num_new = get_usenum(available_new)
                if use_num_new > use_num:
                    return ret + [str(use_num)] * digit
                else:
                    return [str(use_num)] * digit + ret
    return None

N,M = map(int,input().split(" "))
As = np.array(list(map(int,input().split(" "))))
print("".join(solve(N,As)))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+1)
ans=[0]*(n+1)
num=[0,2,5,5,4,5,6,3,7,6]
INF=10**18
for i in range(1,n+1):
  stack=[]
  for j in a:
    if i-num[j]>=0:
      stack.append(dp[i-num[j]])
    else:
      stack.append(-INF)
  dp[i]=max(stack)+1
  if dp[i]>0:
    ans[i] += ans[i-num[stack.index(max(stack))]]+num[stack.index(max(stack))]*10**(dp[i]-1)
print(ans[n])

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import OrderedDict
MATCH_USE = np.array([2,5,5,4,5,6,3,7,6])

def make_combination_dict(total_num, nums_list):
    retdict = {}
    if len(nums_list) == 0 or total_num < nums_list[0]:
        return {}
    max_digit = total_num // nums_list[0]
    if total_num % nums_list[0] == 0:
        retdict[nums_list[0]] = max_digit
        return retdict
    else:
        for i in range(max_digit, -1, -1):
            combinations = make_combination_dict(total_num - i * nums_list[0],nums_list[1:])
            if len(combinations) != 0:
                retdict[nums_list[0]] = i
                retdict.update(combinations)
                return retdict
    return retdict

def matchnum_sorted(matchnum_list,usable_nums):
    retdict = OrderedDict()
    for matchnum in matchnum_list:
        if matchnum in [2,3,4,7]:
            retdict[matchnum] = [0,0,1,7,4,0,0,8][matchnum]
        elif matchnum == 5:
            for val in [5,3,2]:
                if val in usable_nums:
                    retdict[matchnum] = val
                    break
        else: #matchnum==6
            for val in [9,6]:
                if val in usable_nums:
                    retdict[matchnum] = val
                    break
    return sorted(retdict.items(),key=lambda x:-x[1])

N,M = map(int,input().split(" "))
As = list(map(int,input().split(" ")))
assert(len(As) == M)
As = np.array(As)
usable_match_nums = sorted(np.unique(MATCH_USE[As - 1]))
combinationd = make_combination_dict(N,usable_match_nums)
matchnum_val_combination = matchnum_sorted(np.unique(np.array(list(combinationd.keys()))),As)
retstr = ""
for k,v in matchnum_val_combination:
    retstr += "".join([str(v)] * combinationd[k])
print(retstr)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import OrderedDict
MATCH_USE = np.array([2,5,5,4,5,6,3,7,6])

def make_combination_dict(total_num, nums_list):
    retdict = {}
    if len(nums_list) == 0 or total_num < nums_list[0]:
        return {}
    max_digit = total_num // nums_list[0]
    if total_num % nums_list[0] == 0:
        retdict[nums_list[0]] = max_digit
        return retdict
    else:
        for i in range(max_digit - 1, -1, -1):
            combinations = make_combination_dict(total_num - i * nums_list[0],nums_list[1:])
            if len(combinations) != 0:
                retdict[nums_list[0]] = i
                retdict.update(combinations)
                return retdict
    return retdict

def matchnum_sorted(matchnum_list,usable_nums):
    retdict = OrderedDict()
    for matchnum in matchnum_list:
        if matchnum in [2,3,4,7]:
            retdict[matchnum] = [0,0,1,7,4,0,0,8][matchnum]
        elif matchnum == 5:
            for val in [5,3,2]:
                if val in usable_nums:
                    retdict[matchnum] = val
                    break
        else: #matchnum==6
            for val in [9,6]:
                if val in usable_nums:
                    retdict[matchnum] = val
                    break
    return sorted(retdict.items(),key=lambda x:-x[1])

N,M = map(int,input().split(" "))
As = list(map(int,input().split(" ")))
assert(len(As) == M)
As = np.array(As)
usable_match_nums = sorted(np.unique(MATCH_USE[As - 1]))
combinationd = make_combination_dict(N,usable_match_nums)
matchnum_val_combination = matchnum_sorted(np.unique(np.array(list(combinationd.keys()))),As)
retstr = ""
for k,v in matchnum_val_combination:
    retstr += "".join([str(v)] * combinationd[k])
print(retstr)

Submission status: Wrong Answer

Solution code:
from math import floor,log10
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,M = read_int()

A = read_int()
# for index arrangement
A.append(-1)
A.sort()

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

dp = [-1 for j in range(N+1)]
def solve():
    dp[0] = 0
    for i in range(M):
        for j in range(N+1):
            if j - W[A[i + 1]] >= 0 and dp[j - W[A[i + 1]]] >= 0:
                d = 0
                if dp[j - W[A[i + 1]]] > 0:
                    d = floor(log10(dp[j - W[A[i + 1]]])) + 1
                v = A[i + 1]*10**d
                dp[j] = max(dp[j], dp[j - W[A[i + 1]]] + v)

                
if __name__ == "__main__":
    solve()
    print(dp[N])

Submission status: Wrong Answer

Solution code:
from math import floor,log10
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,M = read_int()

A = read_int()
# for index arrangement
A.append(-1)
A.sort()

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

dp = [-1 for j in range(N+1)]
def solve():
    dp[0] = 0
    for i in range(M):
        for j in range(N+1):
            v = A[i + 1]
            if j - W[A[i + 1]] >= 0 and dp[j - W[A[i + 1]]] >= 0:
                # log(0) = -INFを省く
                if dp[j - W[A[i + 1]]] > 0:
                    d = floor(log10(dp[j - W[A[i + 1]]])) + 1
                    v = A[i + 1]*10**d
                dp[j] = max(dp[j], dp[j - W[A[i + 1]]] + v)

if __name__ == "__main__":
    solve()
    print(dp[N])

Submission status: Wrong Answer

Solution code:
from math import floor,log10
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,M = read_int()

A = read_int()
# for index arrangement
A.append(-1)
A.sort()

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

dp = [[0 if j == 0 else -1 for j in range(N+1)] for i in range(M+1)]
def solve():
    for i in range(M):
        for j in range(N+1):
            if dp[i][j] >= 0:
                dp[i+1][j] = dp[i][j]
            v = A[i + 1]
            for k in range(2):
                if j - W[A[i + 1]] >= 0 and dp[i + 1 - k][j - W[A[i + 1]]] >= 0:
                    # get rid of log(0)
                    if dp[i + 1 - k][j - W[A[i + 1]]] > 0:
                        d = floor(log10(dp[i + 1 - k][j - W[A[i + 1]]])) + 1
                        v = A[i + 1]*10**d
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1 - k][j - W[A[i + 1]]] + v)


if __name__ == "__main__":
    solve()
    print(dp[M][N])

Submission status: Wrong Answer

Solution code:
from math import floor,log10
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,M = read_int()

A = read_int()
# for index arrangement
A.append(-1)
A.sort()

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

dp = [[0 if j == 0 else -1 for j in range(N+1)] for i in range(M+1)]
def solve():
    for i in range(M):
        for j in range(N+1):
            if dp[i][j] >= 0:
                dp[i+1][j] = dp[i][j]
            v = A[i + 1]
            for k in range(i + 1):
                if j - W[A[i + 1]] >= 0 and dp[i + 1 - k][j - W[A[i + 1]]] >= 0:
                    # get rid of log(0)
                    if dp[i + 1 - k][j - W[A[i + 1]]] > 0:
                        d = floor(log10(dp[i + 1 - k][j - W[A[i + 1]]])) + 1
                        v = A[i + 1]*10**d
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1 - k][j - W[A[i + 1]]] + v)


if __name__ == "__main__":
    solve()
    print(dp[M][N])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, namedtuple
from itertools import combinations_with_replacement


fin = sys.stdin.readline
num_matches_required = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

N, M = map(int, fin().split())
nums = set(map(int, fin().split()))

chosen_nums = defaultdict(int)
for num in nums:
    nmatches = num_matches_required[num]
    if chosen_nums[nmatches] < num:
        chosen_nums[nmatches] = num


chosen_nums = set(num for num in chosen_nums.values())
# print(chosen_nums)

NumWithNumMatches = namedtuple("NumWithNumMatches", ('num', 'nmatches'))
num = next(iter(chosen_nums))
base = NumWithNumMatches(num, num_matches_required[num])
for num in chosen_nums:
    if num_matches_required[num] < base.nmatches:
        base = NumWithNumMatches(num, num_matches_required[num])

# print(base)
other_nums = chosen_nums - {base.num}
# NumWithRemainder = namedtuple("NumWithRemainder", ("num", "rem"))
other_nums = tuple(NumWithNumMatches(num, num_matches_required[num]) 
    for num in other_nums)
# print(other_nums)

if N % base.nmatches == 0:
    print(str(base.num) * (N // base.nmatches))
    exit(0)

max_num = 0
for num_others in range(1, base.nmatches):
    good_candidates, num_matches = "", float('inf')
    for candidates in combinations_with_replacement(other_nums, r=num_others):
        consumed_matches = sum(candidate.nmatches for candidate in candidates)
        if consumed_matches % base.nmatches == N % base.nmatches:
            if consumed_matches < num_matches:
                good_candidates, num_matches = "".join(sorted("".join(str(candidate.num) for candidate in candidates), reverse=True)), consumed_matches
            elif consumed_matches == num_matches:
                str_candidates = "".join(sorted("".join(str(candidate.num) for candidate in candidates), reverse=True))
                good_candidates = max(good_candidates, str_candidates)
    if good_candidates != "":
        break

# print(good_candidates)
num_matches_by_others = sum(num_matches_required[int(digit)] for digit in good_candidates)
if good_candidates > str(base.num) * len(good_candidates):
    print(good_candidates + str(base.num) * ((N - num_matches_by_others) // base.nmatches))
else:
    print(str(base.num) * ((N - num_matches_by_others) // base.nmatches) + good_candidates)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
Q = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

QA = [(Q[A[i]], A[i]) for i in range(M)]


n2 = QA.count((5,2))
n3 = QA.count((5,3))
n5 = QA.count((5,5))
n6 = QA.count((6,6))
n9 = QA.count((6,9))

if (n3 > 0 and n2 > 0) or  (n5 > 0 and n2 > 0) :
    QA.remove((5,2))
if n5 > 0 and n3 > 0:
    QA.remove((5,3))
if n9 > 0 and n6> 0:
    QA.remove((6,6))

QA.sort()

def f(used_q, used_a):
    if used_q > N:
        return
    elif used_q == N:
        s = sorted(used_a, reverse=True)
        s = [str(i) for i in s]
        print("".join(s))
        sys.exit()

    for qa in QA:
        q, a = qa[0], qa[1]
        used_a.append(a)
        f(used_q + q, used_a)
        del used_a[-1]

l = []
f(0, l)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 10

def num(k):#各数字に使用するマッチ棒の本数を返す関数
    if k == 1:
        return 2
    elif k == 7:
        return 3
    elif k == 4:
        return 4
    elif k == 2 or k == 3 or k == 5:
        return 5
    elif k == 6 or k == 9:
        return 6
    elif k == 8:
        return 7

n, m = map(int,input().split())
l = list(map(int,input().split()))
l.sort(reverse = True)
         
dp = [(-1) * INF] * (n+1)

dp[0] = 0

for i in range(2,n+1):
    can = []
    for x in l:
        if i-num(x)>=0:
            can.append(dp[i-num(x)]+1)
    if can == []:
        dp[i] = 0
    else:
        dp[i] = max(can)
        
#print(dp)

anslist = [0] * dp[n]

left = n

for j in range(dp[n],0,-1):#jは桁数
    if j == 1:
        for x in l:
            if num(x) == left:
                anslist[j-1] = x
                break
    else:
        for x in l:
            if dp[left-num(x)] == j - 1:
                anslist[j-1] = x#j桁目は10^(j-1)の位
                left = left-num(x)
                break
            
    #print([j,x,left])
#print(anslist)
            
            
ans = 0

for j in range(0,dp[n]):
    ans = ans + anslist[j] * (10 ** j)

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 6

def num(k):#各数字に使用するマッチ棒の本数を返す関数
    if k == 1:
        return 2
    elif k == 7:
        return 3
    elif k == 4:
        return 4
    elif k == 2 or k == 3 or k == 5:
        return 5
    elif k == 6 or k == 9:
        return 6
    elif k == 8:
        return 7

n, m = map(int,input().split())
l = list(map(int,input().split()))
l.sort(reverse = True)
         
dp = [(-1) * INF] * (n+1)

dp[0] = 0

for i in range(2,n+1):
    can = []
    for x in l:
        if i-num(x)>=0:
            can.append(dp[i-num(x)]+1)
    if can == []:
        dp[i] = 0
    else:
        dp[i] = max(can)
        
#print(dp)

anslist = [0] * dp[n]

left = n

for j in range(dp[n],0,-1):#jは桁数
    if j == 1:
        for x in l:
            if num(x) == left:
                anslist[j-1] = x
                break
    else:
        for x in l:
            if dp[left-num(x)] == j - 1:
                anslist[j-1] = x#j桁目は10^(j-1)の位
                left = left-num(x)
                break
            
    #print([j,x,left])
#print(anslist)
            
            
ans = 0

for j in range(0,dp[n]):
    ans = ans + anslist[j] * (10 ** j)

print(ans)

Submission status: Wrong Answer

Solution code:
def num(k):#各数字に使用するマッチ棒の本数を返す関数
    if k == 1:
        return 2
    elif k == 7:
        return 3
    elif k == 4:
        return 4
    elif k == 2 or k == 3 or k == 5:
        return 5
    elif k == 6 or k == 9:
        return 6
    elif k == 8:
        return 7

n, m = map(int,input().split())
l = list(map(int,input().split()))
l.sort(reverse = True)
         
dp = [0] * (n+1)

for i in range(2,n+1):
    can = []
    for x in l:
        if i-num(x)>=0:
            can.append(dp[i-num(x)]+1)
    if can == []:
        dp[i] = 0
    else:
        dp[i] = max(can)
        
#print(dp)

anslist = [0] * dp[n]

left = n

for j in range(dp[n],0,-1):#jは桁数
    if j == 1:
        for x in l:
            if num(x) == left:
                anslist[j-1] = x
                break
    else:
        for x in l:
            if dp[left-num(x)] == j - 1:
                anslist[j-1] = x#j桁目は10^(j-1)の位
                left = left-num(x)
                break
            
    #print([j,x,left])
#print(anslist)
            
            
ans = 0

for j in range(0,dp[n]):
    ans = ans + anslist[j] * (10 ** j)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
Q = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

QA = [(Q[A[i]], A[i]) for i in range(M)]
QA.sort()

n2 = QA.count((5,2))
n3 = QA.count((5,3))
n5 = QA.count((5,5))
n6 = QA.count((6,6))
n9 = QA.count((6,9))

if n2 > 0 and n3 > 0:
    QA.remove((5,2))
if n3 > 0 and n5 > 0:
    QA.remove((5,3))
if n6 > 0 and n9 > 0:
    QA.remove((6,6))



def f(used_q, used_a):
    if used_q > N:
        return
    elif used_q == N:
        s = sorted(used_a, reverse=True)
        s = [str(i) for i in s]
        print("".join(s))
        sys.exit()

    for qa in QA:
        q, a = qa[0], qa[1]
        used_a.append(a)
        f(used_q + q, used_a)
        del used_a[-1]

l = []
f(0, l)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000)

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
Q = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

QA = [(Q[A[i]], A[i]) for i in range(M)]
# QA.sort(key=lambda x:(x[0],-x[1]))
QA.sort()

def f(used_q, used_a):
    if used_q > N:
        return
    elif used_q == N:
        if 2 in used_a and 3 in used_a:
            return
        if 2 in used_a and 5 in used_a:
            return
        if 3 in used_a and 5 in used_a:
            return
        if 6 in used_a and 9 in used_a:
            return

        s = sorted(used_a, reverse=True)
        s = [str(i) for i in s]
        print("".join(s))
        sys.exit()

    for qa in QA:
        q, a = qa[0], qa[1]
        used_a.append(a)
        f(used_q + q, used_a)
        del used_a[-1]

l = []
f(0, l)