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 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]))


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)

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]))


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:
def num(k):#各数字に使用するマッチ棒の本数を返す関数
    if k == 1:
        return 1
    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:
def num(k):#各数字に使用するマッチ棒の本数を返す関数
    if k == 1:
        return 1
    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()

def f(used_q, num):
    if used_q > N:
        return -float("inf")
    elif used_q == N:
        s = sorted(list(str(num)),reverse=True)
        print("".join(s))
        sys.exit()
        return num

    ret = 0
    for qa in QA:
        q = qa[0]
        a = qa[1]
        ret = max(ret,f(used_q + q, num * 10 + a))
    return ret

f(0,0)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
alist = list(sorted(map(int, input().split())))[::-1]
md = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

dp = [[0, []] for _ in range(n + 1)]

for i in range(2, n+1):
  maxn = 0
  maxt = []
  for a in alist:
    if i - md[a] < 0:
      continue
    if maxn < dp[i-md[a]][0] + 1:
      maxn = dp[i-md[a]][0] + 1
      maxt = dp[i-md[a]][1][:]
      maxt.append(a)
  dp[i] = [maxn, maxt]
print(*sorted(dp[n][1], key=lambda x: -x), sep='')

Submission status: Wrong Answer

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

dp = [[0, []] for _ in range(n + 1)]

for i in range(2, n+1):
  maxn = 0
  maxt = []
  for a in alist:
    if i - md[a] < 0:
      continue
    if maxn < dp[i-md[a]][0] + 1:
      maxn = dp[i-md[a]][0] + 1
      maxt = dp[i-md[a]][1][:]
      maxt.append(a)
  dp[i] = [maxn, maxt]
print(*sorted(dp[n][1], key=lambda x: -x), sep='')

Submission status: Wrong Answer

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

cost = sorted(list(zip([[2,5,5,4,5,6,3,7,6][a-1] for a in A],A)),key = lambda x: (x[0],-x[1]))

#同じ画数の数字を除く
tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1

stack = [[0]*(len(cost))]
while stack:
    ans_list = stack.pop()
    tmp = sum([n*cost[i][0] for i,n in enumerate(ans_list)])
    if tmp == N:
        break
    elif tmp < N:
        tmp2 = len(ans_list)
        for i in range(tmp2-1,-1,-1):
            stack.append([a + (i == j) for j,a in enumerate(ans_list)])

ans_out = sorted(list(zip(cost,ans_list)),key = lambda x: -x[0][1])

out_str = ""
for out in ans_out:
    out_str += str(out[0][1])*out[1]
print(out_str)

Submission status: Wrong Answer

Solution code:
N,M = map(int,(input().split()))
A = list(map(int,input().split()))
cost = sorted(list(zip([[2,5,5,4,5,6,3,7,6][a-1] for a in A],A)),key = lambda x: (x[0],-x[1]))

#同じ画数の数字を除く
tmp = len(cost)
i = 1
while i < tmp:
    if cost[i][0] == cost[i-1][0]:
        cost.pop(i)
        tmp = len(cost)
    else:
        i += 1

stack = [[1]+[0]*(len(cost)-1)]
while stack:
    ans_list = stack.pop()
    tmp = 0
    for i,n in enumerate(ans_list):
        tmp += n * cost[i][0]
    if tmp == N:
        break
    elif tmp < N:
        tmp2 = len(ans_list)
        for i in range(tmp2-1,-1,-1):
            stack.append([a + (i == j) for j,a in enumerate(ans_list)])

ans_out = sorted(list(zip(cost,ans_list)),key = lambda x: -x[0][1])

out_str = ""
for out in ans_out:
    out_str += str(out[0][1])*out[1]
print(out_str)

Submission status: Wrong Answer

Solution code:
nn=[2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
a=input().split()
b=[]
for i in range(m):
  a[i]=int(a[i])
  
if 5 in a:
  if 2 in a:
    a.remove(2)
  if 3 in a:
    a.remove(3)
elif 3 in a:
  if 2 in a:
    a.remove(2)
if 9 in a:
  if 6 in a:
    a.remove(6)
    
a.sort(reverse=True)
for i in range(len(a)):
  b.append(nn[a[i]-1])
  
dp=[-10*18 for _ in range(n)]
dp[0]=0
for i in range(n):
  for j in range(len(b)):
    if i+b[j]>n-1:
      continue
    dp[i+b[j]]=max(dp[i+b[j]],dp[i]+1)
    
k=dp[n-1]
ans=""
for i in range(k):
  for j in range(len(b)):
    if dp[n-1-b[j]]==dp[n-1]-1:
      ans+=str(a[j])
      n-=b[j];
      break
      
print(ans)

Submission status: Wrong Answer

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

numbers.sort(reverse=True)
use_nums = []
for n in numbers:
    use_nums.append([n, cost[n - 1]])
use_nums.sort(key=lambda x: x[1])

def find_num(remain, num_list):
    if remain == 0:
        return num_list
    for nc in use_nums:
        if nc[1] <= remain:
            r2 = remain - nc[1]
            nl2 = num_list + [nc[0]]
            nn = find_num(r2, nl2)
            if nn != None:
                return nn
    return None

answer = ""
for i in range(len(use_nums)):
    init_count = N // use_nums[i][1]
    init_remain = N - use_nums[i][1] * init_count
    init_list = [use_nums[i][0]] * init_count

    result = None
    while True:
        result = find_num(init_remain, init_list)
        if result != None:
            break
        init_remain += use_nums[i][1]
        init_list = init_list[:-1]

    result.sort(reverse=True)
    total = ""
    for r in result:
        total += str(r)
    l1 = len(answer)
    l2 = len(total)
    if l1 < l2:
        answer = total
    elif l1 == l2 and answer < total:
        answer = total
print(answer)

Submission status: Wrong Answer

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

numbers.sort(reverse=True)
use_nums = []
for n in numbers:
    use_nums.append([n, cost[n - 1]])
use_nums.sort(key=lambda x: x[1])

def find_num(remain, num_list):
    if remain == 0:
        return num_list
    for nc in use_nums:
        if nc[1] <= remain:
            r2 = remain - nc[1]
            nl2 = num_list + [nc[0]]
            nn = find_num(r2, nl2)
            if nn != None:
                return nn
    return None

max_digits = 0
use_idx = 0

for i, nc in enumerate(use_nums):
    digits = N // nc[1]
    if max_digits < digits:
        max_digits = digits
        use_idx = i
    elif max_digits == digits and nc[0] > use_nums[use_idx][0]:
        max_digits = digits
        use_idx = i

init_count = N // use_nums[use_idx][1]
init_remain = N - use_nums[use_idx][1] * init_count
init_list = [use_nums[use_idx][0]] * init_count

result = None
while True:
    result = find_num(init_remain, init_list)
    if result != None:
        break
    init_remain += use_nums[use_idx][1]
    init_list = init_list[:-1]

result.sort(reverse=True)
total = ""
for r in result:
    total += str(r)

print(total)

Submission status: Wrong Answer

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

numbers.sort(reverse=True)
use_nums = []
for n in numbers:
    use_nums.append([n, cost[n - 1]])
use_nums.sort(key=lambda x: x[1])

def find_num(remain, num_list):
    if remain == 0:
        return num_list
    for nc in use_nums:
        if nc[1] <= remain:
            r2 = remain - nc[1]
            nl2 = num_list + [nc[0]]
            nn = find_num(r2, nl2)
            if nn != None:
                return nn
    return None

init_count = N // use_nums[0][1]
init_remain = N - use_nums[0][1] * init_count
init_list = [use_nums[0][0]] * init_count

result = None
while True:
    result = find_num(init_remain, init_list)
    if result != None:
        break
    num = init_list[len(init_list) - 1]
    init_remain += cost[num - 1]
    init_list = init_list[:-1]

result.sort(reverse=True)
total = ""
for r in result:
    total += str(r)

print(total)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = {}
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

dp = ["" for n in range(10010)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
        

for m in match:
    dp[cost[m]] = m

for i in range(length + 1):
    # print(dp, i)
    if dp[i]:
        for m in match:
            # if i + cost[m] <= length:
            dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = {}
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

dp = ["" for n in range(11000)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
        

for m in match:
    dp[cost[m]] = m

for i in range(length + 1):
    # print(dp, i)
    if dp[i]:
        for m in match:
            if i + cost[m] <= length:
                dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = {}
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

dp = ["" for n in range(10010)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
        

for m in match:
    dp[cost[m]] = m

for i in range(length + 1):
    # print(dp, i)
    if dp[i]:
        for m in match:
            if i + cost[m] <= length:
                dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = defaultdict(int)
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

dp = ["" for n in range(10010)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
        

for m in match:
    dp[cost[m]] = m

for i in range(length + 1):
    # print(dp, i)
    if dp[i] != "":
        for m in match:
            if i + cost[m] <= length:
                dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
length, types = map(int, input().split(" "))
match = [n for n in input().split(" ")]
cost = defaultdict(int)
cost.update({"1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6})

dp = ["" for n in range(10010)]

def compare_str(a, b):
    if a == "":
        return b
    elif len(a) == len(b):
        return a if a > b else b
    elif len(a) > len(b):
        return a
    return b
        

for m in match:
    dp[cost[m]] = m

for i in range(length + 1):
    # print(dp, i)
    if dp[i]:
        for m in match:
            if i + cost[m] <= length:
                dp[i + cost[m]] = compare_str(dp[i + cost[m]], dp[i] + m)
print(dp[length])

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max(n-210, 0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 10 < i < n-50:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
ans = ans[:10] + str(r[0])*k + ans[10:]
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max(n-500, 0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 100 < i < n-100:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
ans = ans[:100] + str(r[0])*k + ans[100:]
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max(n-200, 0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 49 < i < n-50:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
ans = ans[:50] + str(r[0])*k + ans[50:]
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max(n-100, 0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 42 < i < n-42:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
ans = ans[:50] + str(r[0])*k + ans[50:]
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max(n-84, 0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  if 42 < i < n-42:
    _max[i] = max(_max[i], _max[i-r[1]]*10 + r[0])
  else:
    for x in l:
      ind = i-x[1]
      if ind >= 0:
        _max[i] = max(_max[i], _max[ind]*10 + x[0])
ans = str(_max[n])
ans = ans[:42] + str(r[0])*k + ans[42:]
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max((n - 210),0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  for x in l:
    if x[1] <= i:
      _max[i] = max(_max[i], _max[i-x[1]]*10 + x[0])
ans = str(_max[n]) + str(r[0])*k
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max((n - 100),0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
  for x in l:
    if x[1] <= i:
      _max[i] = max(_max[i], _max[i-x[1]]*10 + x[0])
ans = str(_max[n]) + str(r[0])*k
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max((n - 100),0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
    if 100 < i:
        _max[i] = _max[i-r[1]]*10 + r[0]
    else:
        for x in l:
            if x[1] <= i:
                _max[i] = max(_max[i], _max[i-x[1]]*10 + x[0])
ans = str(_max[n]) + str(r[0])*k
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max((n - 49),0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
    if 49 < i:
        _max[i] = _max[i-r[1]]*10 + r[0]
    else:
        for x in l:
            if x[1] <= i:
                _max[i] = max(_max[i], _max[i-x[1]]*10 + x[0])
ans = str(_max[n]) + str(r[0])*k
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max((n - 84),0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
    if 42 < i < n-42:
        _max[i] = _max[i-r[1]]*10 + r[0]
    else:
        for x in l:
            if x[1] <= i:
                _max[i] = max(_max[i], _max[i-x[1]]*10 + x[0])
ans = str(_max[n]) + str(r[0])*k
print(ans)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [2, 5, 5, 4, 5, 6, 3, 7, 6]
l = [[x, cost[x-1]] for x in a]
l = sorted(l, key = lambda x: x[1]*10-x[0])
r = l[0]
k = max((n - 42),0)//r[1]
n -= r[1]*k
_max = [0] + [-INF]*n
for i in range(1, n+1):
    if 42 < i:
        _max[i] = _max[i-r[1]]*10 + r[0]
    else:
        for x in l:
            if x[1] <= i:
                _max[i] = max(_max[i], _max[i-x[1]]*10 + x[0])
ans = str(_max[n]) + str(r[0])*k
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
a = sorted(a, reverse=True)
l = [2, 5, 5, 4, 5, 6, 3, 7, 6]
_min = 10
ind = 10
for x in a:
  _ind = x-1
  if l[_ind] < _min:
    _min = l[_ind]
    ind = x
    
l = list(map(lambda x: x-_min, l))
mod = n % _min
k = n // _min
ans = str()
for i in range(k):
  for x in a:
    _ind = x-1
    if not l[_ind]:
      continue
    else:
      _mod = mod - l[_ind]
      if _mod >= 0:
        mod = _mod
        ans += str(x)
        break
      else:
        continue
  if mod <=0:
    break
ans += str(ind)*(k - len(ans))
print(int(ans))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
a = sorted(a, reverse=True)
l = [2, 5, 5, 4, 5, 6, 3, 7, 6]
_min = 10
ind = 10
for x in a:
  _ind = x-1
  if l[_ind] < _min:
    _min = l[_ind]
    ind = x
    
l = list(map(lambda x: x-_min, l))
mod = n % _min
k = n // _min
ans = str()
for i in range(k):
  for x in a:
    _ind = x-1
    if not l[_ind]:
      continue
    else:
      _mod = mod - l[_ind]
      if _mod >= 0:
        mod = _mod
        ans += str(x)
        break
      else:
        continue
ans += str(ind)*(k - len(ans))
print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			d = dfs(num - ma_map[p])
			if d == -1: continue
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

print(ma_map[2])
ma.sort()
print("{}".format(dfs(N)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			d = dfs(num - ma_map[p])
			if d == -1: continue
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

print(ma_map[2])
ma.sort()
print(dfs(N))

Submission status: Wrong Answer

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

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

cost = []
for i in range(M):
    cost.append([A[i], match[A[i]]])

for i in range(N):
    for k in range(M):
        if i + 1 - cost[k][1] >= 0:
            dp[i + 1] = max(dp[i + 1], dp[i + 1 - cost[k][1]] + 1)

tmp = 0 #使ったマッチの数
res = ''
cost.sort(key=lambda x: x[0], reverse=True)
for i in range(dp[N]):
    if i != dp[N] - 1:
        for j in range(M):
            if dp[N - cost[j][1] - tmp] == dp[N - tmp] - 1:
                res = res + str(cost[j][0])
                tmp += cost[j][1]
                break
            
    else:
        for j in range(M):
            if cost[j][1] == N - tmp:
                res = res + str(cost[j][0])
                break
    
print(res)

Submission status: Wrong Answer

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

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

cost = []
for i in range(M):
    cost.append([A[i], match[A[i]]])

for i in range(N):
    for k in range(M):
        if i + 1 - cost[k][1] >= 0:
            dp[i + 1] = max(dp[i + 1], dp[i + 1 - cost[k][1]] + 1)

tmp = 0 #使ったマッチの数
res = ''
cost.sort(key=lambda x: x[0], reverse=True)
for i in range(dp[N]):
    if i != dp[N] - 1:
        for j in range(M):
            if dp[N - cost[j][1] - tmp] == dp[N - tmp] - 1:
                res = res + str(cost[j][0])
                tmp += cost[j][1]
                break
            
    else:
        for j in range(M):
            if cost[j][1] == N - tmp:
                res = res + str(cost[j][0])
    
print(res)

Submission status: Wrong Answer

Solution code:
def solve(pos, rest, a):
    if pos == len(a):
        if rest == 0:
            return True
        else:
            return False

    digit, match = a[pos]
    for k in range(rest // match, -1, -1):
        next_rest = rest - match * k
        if next_rest >= 0 and solve(pos + 1, next_rest, a):
            ans[pos] = k
            return True
    return False


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

N, M = map(int, input().split())
c = list(map(int, input().split()))
a = [(i, m[i]) for i in c]
a.sort(key=lambda x: x[1])

pd, pm = a[0]
b = []
for d, m in a[1:]:
    if pm == m:
        if pd < d:
            pd = d
    else:
        b.append((pd, pm))
        pm = m
        pd = d
b.append((pd, pm))

ans = [0] * len(b)
solve(0, N, b)
ans2 = []
for i in range(len(ans)):
    ans2.append((b[i][0], ans[i]))

ans2.sort(reverse=True)
for d, c in ans2:
    print(str(d) * c, end="")
print()

Submission status: Wrong Answer

Solution code:
def solve(pos, rest, a):
    if pos == len(a):
        if rest == 0:
            return True
        else:
            return False

    digit, match = a[pos]
    for k in range(rest // match, -1, -1):
        if solve(pos + 1, rest - match * k, a):
            ans[pos] = k
            return True
    return False


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

N, M = map(int, input().split())
c = list(map(int, input().split()))
a = [(i, m[i]) for i in c]
a.sort(key=lambda x: x[1])

# pd, pm = a[0]
# b = []
# for d, m in a[1:]:
#     if pm == m:
#         if pd < d:
#             pd = d
#     else:
#         b.append((pd, pm))
#         pm = m
#         pd = d
# b.append((pd, pm))
#
# ans = [0] * len(b)
# solve(0, N, b)
# ans2 = []
# for i in range(len(ans)):
#     ans2.append((b[i][0], ans[i]))

ans = [0] * len(a)
solve(0, N, a)
ans2 = []
for i in range(len(ans)):
    ans2.append((a[i][0], ans[i]))

ans2.sort(reverse=True)
for d, c in ans2:
    print(str(d) * c, end="")
print()

Submission status: Wrong Answer

Solution code:
def solve(pos, rest, a):
    if pos == len(a):
        if rest == 0:
            return True
        else:
            return False

    digit, match = a[pos]
    for k in range(rest // match, -1, -1):
        if solve(pos + 1, rest - match * k, a):
            ans[pos] = max(ans[pos], k)
            return True
    return False

m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
c = list(map(int, input().split()))
a = [(i, m[i]) for i in c]
a.sort(key=lambda x:x[1])
pd, pm = a[0]
b = []
for d, m in a[1:]:
    if pm == m:
        if pd < d:
            pd = d
    else:
        b.append((pd, pm))
        pm = m
        pd = d
b.append((pd, pm))
ans = [0] * len(b)
solve(0, N, b)
ans2 = []
for i in range(len(ans)):
    ans2.append((b[i][0], ans[i]))
ans2.sort(reverse=True)
for d, c in ans2:
    print(str(d)*c, end="")
print()

Submission status: Wrong Answer

Solution code:
def solve(pos, rest, a):
    if pos == len(a):
        if rest == 0:
            return True
        else:
            return False

    digit, match = a[pos]
    for k in range(rest // match, -1, -1):
        if solve(pos + 1, rest - match * k, a):
            ans[pos] = k
            return True
    return False

m = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = map(int, input().split())
c = list(map(int, input().split()))
a = [(i, m[i]) for i in c]
a.sort(key=lambda x:x[1])
pd, pm = a[0]
b = []
for d, m in a[1:]:
    if pm == m:
        if pd < d:
            pd = d
    else:
        b.append((pd, pm))
        pm = m
        pd = d
b.append((pd, pm))
ans = [0] * len(b)
solve(0, N, b)
ans2 = []
for i in range(len(ans)):
    ans2.append((b[i][0], ans[i]))
ans2.sort(reverse=True)
for d, c in ans2:
    print(str(d)*c, end="")
print()

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

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

for i in range(n+1):
    max_tmp = -float("inf")
    for j in am:
        if i-c[j-1]>=0:
            max_tmp = max(dp[i-c[j-1]]+1, max_tmp)
    dp[i] = max(dp[i],max_tmp)

tmp_n = n
ans =""
for i in range(dp[n]):
    for j in range(m):
        if i==dp[n]-1 and tmp_n- c[am[j]-1] != 0:
            continue
        if tmp_n - c[am[j]-1] >= 0 and dp[tmp_n - c[am[j]-1]] == dp[tmp_n] -1:
            ans+=(str(am[j]))
            tmp_n -= c[am[j]-1]
            break


print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

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

for i in range(n+1):
    max_tmp = -float("inf")
    for j in am:
        if i-c[j-1]>=0:
            max_tmp = max(dp[i-c[j-1]]+1, max_tmp)
    dp[i] = max(dp[i],max_tmp)

tmp_n = n
ans =[]
for i in range(dp[n]):
    for j in range(m):
        if i==dp[n]-1 and tmp_n- c[am[j]-1] != 0:
            continue
        if tmp_n - c[am[j]-1] >= 0 and dp[tmp_n - c[am[j]-1]] == dp[tmp_n] -1:
            ans.append(am[j])
            tmp_n -= c[am[j]-1]
            break


print(ans)