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:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
cost = [0,2,5,5,4,5,6,3,7,6]
Acost = []
for i in A:
  Acost.append(cost[i])
micos = min(Acost)
minum = A[Acost.index(micos)]
keta = N // micos
amari = N % micos
ansstr = [minum]*keta
for i in range(keta-1, -1, -1):
  if amari == 0:
    break
  for j in range(len(A)):
    if (Acost[j]-micos)<=amari and A[j]>minum:
      ansstr[i]=A[j]
      amari -= Acost[j]-micos
      break
for i in range(keta):
  if amari == 0:
    break
  for j in range(len(A)):
    cc = 0
    cos = 0
    if (Acost[j]-micos)<amari and A[j]<minum:
      if Acost[j]>cos:
        cos = Acost[j]
        cc = j
      ansstr[i]=A[cc]
      amari -= Acost[cc]-micos
ans = 0
for i in range(keta):
  ans += ansstr[i] * (10**i)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
cost = [0,2,5,5,4,5,6,3,7,6]
Acost = []
for i in A:
  Acost.append(cost[i])
micos = min(Acost)
minum = A[Acost.index(micos)]
keta = N // micos
amari = N % micos
ansstr = [minum]*keta
for i in range(keta-1, -1, -1):
  if amari == 0:
    break
  for j in range(len(A)):
    if (Acost[j]-micos)<=amari and A[j]>minum:
      ansstr[i]=A[j]
      amari -= Acost[j]-micos
      break
for i in range(keta):
  if amari == 0:
    break
  for j in range(len(A)-1,-1,-1):
    if (Acost[j]-micos)<=amari and A[j]<minum:
      ansstr[i]=A[j]
      amari -= Acost[j]-micos
      break
ans = 0
for i in range(keta):
  ans += ansstr[i] * (10**i)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    match = [0,2,5,5,4,5,6,3,7,6]
    dp = [-1] * (N + 10)
    dp[0] = 0
    for a in A:
        cost = match[a]
        for i in range(N):
            if dp[i] != -1:
                tmp = str(dp[i]) + str(a)
                dp[i+cost] = max(dp[i+cost], int(tmp))
        
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    match = [0,2,5,5,4,5,6,3,7,6]
    dp = [-1] * (N + 10)
    dp[0] = 0
    for a in A:
        for i in range(N):
            if dp[i] != -1:
                tmp = str(dp[i]) + str(a)
                dp[i+match[a]] = max(dp[i+match[a]], int(tmp))
        
    print(dp[N])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# d={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()))

d={} # 本数→数字
if 1 in A:
    d[2]=2
if 7 in A:
    d[3]=7
if 4 in A:
    d[4]=4
if 5 in A:
    d[5]=5
elif 3 in A:
    d[5]=3
elif 2 in A:
    d[5]=2
if 9 in A:
    d[6]=9
elif 6 in A:
    d[6]=6
if 8 in A:
    d[7]=8

l=sorted(d.keys()) #本数

ans=int(str(d[l[0]])*(N//l[0]))

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["" for i in range(N+1)]
ans = 0
tmp = set()
for x in num:
    if x[1] > N:
        continue
    for i in range(1, N+1-x[1]):
        for n, k in num:
            if i - k in tmp:
                dp[i] = dp[i-k]+str(n)
                tmp.add(i)
                break
            else:
                if i == k:
                    dp[i] = str(n)
                    tmp.add(k)
                    break
    tmp2 = list(dp[N-x[1]])
    tmp2.append(str(x[0]))
    tmp2.sort(reverse=True)
    ans = max(int("".join(map(str, tmp2))), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["0" for i in range(N+1)]

base = num[0]
num = num[1:]

k = N % base[1]
l = 0
ans = 0
if k == 0:
    print("".join([str(base[0])]*(N // base[1])))
for x in range(k, N, base[1]):
    for i in range(2**len(num)):
        tmp = []
        tmp2 = 0
        for j in range(len(num)):
            if (i >> j) % 2 == 1:
                tmp.append(num[j][0])
                tmp2 += num[j][1]

        if tmp2 != 0 and x % tmp2 == 0:
            tmp = tmp*(x//tmp2)
            tmp += [base[0]] * ((N - x) // base[1])
            tmp.sort(reverse=True)
            ans = max(ans, int("".join(map(str, tmp))))

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["0" for i in range(N+1)]

base = num[0]
num = num[1:]

k = N % base[1]
l = 0
ans = 0
for i in range(2**len(num)):
    tmp = []
    tmp2 = 0
    for j in range(len(num)):
        if (i >> j) % 2 == 1:
            tmp.append(num[j][0])
            tmp2 += num[j][1]

    if (N - tmp2) % base[1] == 0:
        tmp += [base[0]] * ((N - tmp2) // base[1])
        tmp.sort(reverse=True)
        ans = max(ans, int("".join(map(str, tmp))))

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["" for i in range(N+1)]


tmp = set()

for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = dp[i-k]+str(n)
            tmp.add(i)
            break
        else:
            if i == k:
                dp[i] = str(n)
                tmp.add(k)
                break
ans = list(dp[N])
ans.sort(reverse=True)
print("".join(map(str, ans)))

Submission status: Wrong Answer

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

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

# n 本使ってできる最大の桁数
dp = [-1 for _ in range(n + 1)]
dp[0] = 0

digs = [[] for _ in range(n + 1)]

available = {}
for x in a:
    available[t[x]] = x

for v, k in sorted([(v, k) for k, v in available.items()]):
    for i in range(len(dp)):
        if dp[i] >= 0 and i + k < len(dp):
            if dp[i + k] <= dp[i] + 1:
                dp[i + k] = dp[i] + 1
                s = list(digs[i])
                s.append(v)
                digs[i + k] = s

print(''.join(map(str, reversed(sorted(digs[n])))))

Submission status: Wrong Answer

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

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

# n 本使ってできる最大の桁数
dp = [-1 for _ in range(n + 1)]
dp[0] = 0

digs = [[] for _ in range(n + 1)]

available = {}
for x in a:
    available[t[x]] = x

for k, v in available.items():
    for i in range(len(dp)):
        if dp[i] >= 0 and i + k < len(dp):
            if dp[i + k] < dp[i] + 1:
                dp[i + k] = dp[i] + 1
                s = list(digs[i])
                s.append(v)
                digs[i + k] = list(reversed(sorted(s)))
            elif dp[i + k] == dp[i] + 1:
                s = list(digs[i])
                s.append(v)
                nxt = list(reversed(sorted(s)))
                if digs[i + k] < nxt:
                    dp[i + k] = dp[i] + 1
                    digs[i + k] = nxt

print(''.join(map(str, reversed(sorted(digs[n])))))

Submission status: Wrong Answer

Solution code:
inf = 1 << 20
need = -1, 2, 5, 5, 4, 5, 6, 3, 7, 6

n, m = map(int, input().split())
a = map(int, input().split())
d = {need[x]: x for x in sorted(a)}
# {必要本数:数字}
# sortedで昇順にすることで、同じ本数のとき最大値が残る

dp = [-inf] * (n + 1)
dp[0] = 0
# dp[k]:=k本で構成可能な最大桁数

for j in range(1, n + 1):
    dp[j] = max((dp[j - cnt] for cnt in d if j - cnt >= 0), default=-inf) + 1

ret = []
r = dp[n]

if r < 0:
    print(0)
    exit()

curr = n
while r > 0:
    for cnt, num in d.items():
        if dp[curr - cnt] == r - 1:
            ret.append(num)
            r -= 1
            curr -= cnt
            break

ret.sort(reverse=True)
print(''.join(map(str, ret)))

Submission status: Wrong Answer

Solution code:
inf = 1 << 20
need = -1, 2, 5, 5, 4, 5, 6, 3, 7, 6

n, m = map(int, input().split())
a = map(int, input().split())
d = {need[x]: x for x in sorted(a)}
# {必要本数:数字}
# sortedで昇順にすることで、同じ本数のとき最大値が残る

dp = [-inf] * (n + 1)
dp[0] = 0
# dp[k]:=k本で構成可能な最大桁数

for j in range(1, n + 1):
    dp[j] = max((dp[j - cnt] for cnt in d if j - cnt >= 0), default=-inf) + 1

ret = []
r = dp[n]
curr = n
while r > 0:
    for cnt, num in d.items():
        if dp[curr - cnt] == r - 1:
            ret.append(num)
            r -= 1
            curr -= cnt
            break

ret.sort(reverse=True)
print(''.join(map(str, ret)))

Submission status: Wrong Answer

Solution code:
#解答例
N,M=map(int,input().split())
A=list(map(int,input().split()))#使える数字の種類
weight=[0,2,5,5,4,5,6,3,7,6]#作るのに何本必要か、また0は作れないので0になっている
dp=[-1]*(N+1)#とりあえずこれくらい確保しておけばok
dp[0]=0#0本では0しか作れない
#dp[i]はちょうどi本で作れる最高の数を入れることにする
for i in range((N+1)//2):
    for a in A:
        if i+weight[a]<N+1:#今あるi本にa本を加えてもN本を超えないか
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)#今まで作ったi+weight[a]のときのdpの値と、今作ったdp[i]*10+aの値を比べ、大きい方を格納する
                                                           #なぜdp[i]*10+aになるのかに関しては、右から数字を追加していく場合のみを考えることで、重複せずに全通り試せるから
print(dp[N])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  if nokori == 0:
    return current
  if nokori < 0:
    return -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          # 98 ok, 89 重複するので最後の桁以外は skip
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  return max(temps)

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
def hoge():
  for key, nums in list(d.items()):
      for num in nums:
        if enable[num]:
          return (num, key)
num, key = hoge()
cs = []
while n > 30:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Wrong Answer

Solution code:
NUM = (None, 2, 5, 5, 4, 5, 6, 3, 7, 6)

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

# maximum value to make using exactly sticks
dp = [0] * (nSticks + 1)
for digit in a:
    if NUM[digit] <= nSticks:
        dp[NUM[digit]] = digit
for sticks in range(2, nSticks + 1):
    for digit in a:
        if sticks - NUM[digit] >= 0 and dp[sticks - NUM[digit]] > 0:
            dp[sticks] = max(dp[sticks], dp[sticks - NUM[digit]] * 10 + digit)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  k = (nokori, current)
  if nokori <= 0:
    return current if nokori == 0 else -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        temps.append(f(nokori-key, current*10+num))
        break
  return max(temps)

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 30:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}  # key=match, val=num
d[2] = [1]
d[3] = [7]
d[4] = [4]
d[5] = [5, 3, 2]
d[6] = [9, 6]
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
# マッチをk(=2..7)本使う場合の一番大きい値を総当たり
def f(nokori, current):
  k = (nokori, current)
  if nokori <= 0:
    return current if nokori == 0 else -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    for num in nums:
      if enable[num]:
        temps.append(f(nokori-key, current*10+num))
        break
  return max(temps)

# 余裕があるうちは一番マッチの本数が少ないモノをヤケクソで詰めまくる
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 15:
  n -= key
  cs.append(str(num))

# ヤケクソで詰めたやつと総当たりで調べたマックスを並び替えて辞書順で大きくする
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split(' ')))
l = list(map(int, input().split(' ')))
d = {}
# 1 = 2 = 0.5
d[2] = [1]
# 7 = 3 = 2.3 
d[3] = [7]
# 4 = 4 = 1
d[4] = [4]
# 5 = 5 = 1
# 3 = 5 = .6
# 2 = 5 = .4
d[5] = [5, 3, 2]
# 9 = 6 = 1.5
# 6 = 6 = 1
d[6] = [9, 6]
# 8 = 7 = 1.1...
d[7] = [8]
enable = [False] * 10
for a in l:
  enable[a] = True
memo = {}
def f(nokori, current):
#  print(nokori, current)
  k = (nokori, current)  # 順不同
  if k in memo:
    return memo[k]
  if nokori == 0:
    return current
  if nokori < 0:
    return -1
  temps = []
  for key, nums in list(d.items())[::-1]:
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        if nokori-key != 0 and current % 10 != 0 and current % 10 < num:
          continue
        temps.append(f(nokori-key, current*10+num))
        break
  memo[k] = max(temps)
  return memo[k]

# pre
hoge = False
for key, nums in list(d.items()):
    # print(key, nums, type(nums))
    for num in nums:
      if enable[num]:
        hoge = True
        break
    if hoge:
      break
cs = []
while n > 10:
  n -= key
  cs.append(str(num))
num_ans = str(f(n, 0))
print(''.join(sorted(list(num_ans) + cs)[::-1]))

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = [-1 for i in range(N+1)]
dp[0] = 0


tmp = set()

for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = max(dp[i], int(str(n)+str(dp[i-k])))
            tmp.add(i)

        else:
            if i == k:
                dp[i] = n
                tmp.add(k)
                break

ans = list(str(dp[N]))
ans.sort(reverse=True)
print("".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = [-1 for i in range(N+1)]
dp[0] = 0


tmp = set()

for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = max(dp[i], int(str(n)+str(dp[i-k])))
            tmp.add(i)
            break

        else:
            if i == k:
                dp[i] = n
                tmp.add(k)
                break

ans = list(str(dp[N]))
ans.sort(reverse=True)
print("".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[1])
dp = [-1 for i in range(N+1)]
dp[0] = 0


tmp = set()

for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = max(dp[i], int(str(n)+str(dp[i-k])))
            tmp.add(i)
            if i != N:
                break
        else:
            if i == k:
                dp[i] = n
                tmp.add(k)

ans = list(str(dp[N]))
ans.sort(reverse=True)
print("".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[1])
dp = [-1 for i in range(N+1)]
dp[0] = 0


tmp = set()

for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:

            dp[i] = max(int(str(n)+str(dp[i-k])), dp[i])
            tmp.add(i)
        else:
            if i == k:
                dp[i] = n
                tmp.add(k)

ans = list(str(dp[N]))
ans.sort(reverse=True)
print("".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[1])
dp = [-1 for i in range(N+1)]
dp[0] = 0


tmp = set()

for i in range(N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = int(str(n)+str(dp[i-k]))
            tmp.add(i)
            break
        else:
            if i == k:
                dp[i] = n
                tmp.add(k)

ans = list(str(dp[N]))
ans.sort(reverse=True)
print("".join(map(str, ans)))

Submission status: Wrong Answer

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

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    x = table[i]
    if N - x >= 0 and dp[N] == dp[N - x] + 1:
        answer.append(i)
        N -= x

print(''.join(map(str, answer)))

Submission status: Wrong Answer

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


# リストの後ろから検索
def rindex(wanted_value, list_name):
    indexes = [i for i, x in enumerate(list_name) if x == wanted_value]
    return indexes[-1]


table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

a_min = min(a)
A_min = A[rindex(a_min, a)]
q = N // a_min
r = N % a_min
answer = []

cost_sorted_a, cost_sorted_A = zip(*sorted(zip(a, A), reverse=True))

while r:
    for i in cost_sorted_A:
        tmp = table[i] - a_min
        if table[i] != a_min and r >= tmp:
            q -= r // tmp
            answer.extend([i] * (r // tmp))
            r %= tmp

answer.extend([A_min] * q)
answer.sort(reverse=True)

print(''.join(map(str, answer)))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[int(i) for i in input().split()]
req=[0,2, 5, 5, 4, 5, 6, 3, 7, 6]
l.sort(key=lambda x:[req[x],-x])
ans=''
i=0 
while n:
    if i==m:
        break 
    if n>=req[l[i]]:
        n-=req[l[i]]
        ans+=str(l[i])
    else:
        i+=1 
ans=list(ans)
#print(ans)
rem=n 
ans=list(ans)
for i in range(len(ans)-1,-1,-1):
    for j in range(m):
        need=-req[int(ans[i])]+req[l[j]]
        if need<=n:
            n-=need 
            ans[i]=l[j]
print(*ans,sep='')

Submission status: Wrong Answer

Solution code:
# D - Match Matching

import itertools

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

n_match = [-1,2,5,5,4,5,6,3,7,6]
tmp = []
for x in A:
    tmp.append([x, n_match[x]])
n_match = tmp

n_match = sorted(n_match, key=lambda x: x[0], reverse=True)
n_match = sorted(n_match, key=lambda x: x[1])
rep_number = n_match[0][0]
rep_match = n_match[0][1]

if N % n_match[0][1] == 0:
    print(str(rep_number) * (N//rep_match))
else:
    n_match = n_match[1:]
    n_match = sorted(n_match, key=lambda x: x[0], reverse=True)
    for n_break in range(1, N//rep_match + 1):
        match_comb_list = []
        rest_match = rep_match*n_break + N % rep_match
        for n_add in range(1,n_break+1):
            for match_comb in list(itertools.combinations_with_replacement([n_match[idx][1] for idx in range(len(n_match))], n_add)):
                if sum(match_comb) == rest_match:
                    match_comb_list.append([n_break, match_comb])
        if match_comb_list:
            break
    ans_list = []
    for idx in range(len(match_comb_list)):
        match_comb = match_comb_list[idx][1]
        tmp = []
        for x in match_comb:
            for idx2 in range(len(n_match)):
                if x == n_match[idx2][1]:
                    tmp.append(n_match[idx2][0])
        tmp += [rep_number] * (N//rep_match - match_comb_list[idx][0])
        tmp = sorted(tmp, reverse = True)
        ans_list.append(int("".join(list(map(str, tmp)))))
    print(max(ans_list))

Submission status: Wrong Answer

Solution code:
# D - Match Matching

import itertools

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

n_match = [-1,2,5,5,4,5,6,3,7,6]
tmp = []
for x in A:
    tmp.append([x, n_match[x]])
n_match = tmp

n_match = sorted(n_match, key=lambda x: x[0], reverse=True)
n_match = sorted(n_match, key=lambda x: x[1])
rep_number = n_match[0][0]
rep_match = n_match[0][1]

if N % n_match[0][1] == 0:
    print(str(rep_number) * (N//rep_match))
else:
    n_match = n_match[1:]
    n_match = sorted(n_match, key=lambda x: x[0], reverse=True)
    n_break = 1
    while 1:
        rest_match = rep_match*n_break + N % rep_match
        for n_add in range(1,n_break+1):
            match_comb_list = []
            for match_comb in list(itertools.combinations_with_replacement([n_match[idx][1] for idx in range(len(n_match))], n_add)):
                if sum(match_comb) == rest_match:
                    match_comb_list.append(match_comb)
            if len(match_comb_list) >= 1:
                break
        else:
            n_break += 1
            continue
        break
    add_numbers = []
    for match_comb in match_comb_list:
        tmp = []
        for x in match_comb:
            for idx in range(len(n_match)):
                if x == n_match[idx][1]:
                    tmp.append(n_match[idx][0])
        add_numbers.append(tmp)
    add_number = 0
    for x_list in add_numbers:
        x_list = sorted(x_list, reverse = True)
        x_list = list(map(str, x_list))
        add_number = max(add_number, int("".join(x_list)))
    add_number = list(str(add_number))
    ans = [str(rep_number)] * (N//rep_match - n_break) + add_number
    ans = list(map(int, ans))
    ans = sorted(ans, reverse=True)
    print("".join(list(map(str,ans))))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N, M = map(int, input().split())
nums = list(map(int, input().split()))

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

dp = [''] * (N + 1)
for n in range(1, N + 1):
    for k in nums:
        d = 0
        cnt = n - matchNum[k]
        if cnt < 0 or cnt >= 1 and dp[cnt] == '':
            continue
        if cnt == 0 or dp[n] == '' or dp[n] <= dp[cnt] * 10:
            oldVal = list(str(dp[cnt]))[:: -1]
            adder = bisect_left(oldVal, str(k))
            newVal = oldVal[:adder] + [str(k)] + oldVal[adder:]
            newVal = int(''.join(newVal[:: -1]))
            d = max(d, newVal)
        if d == 0:
            continue
        elif dp[n] == '':
            dp[n] = d
        else:
            dp[n] = max(dp[n], d)

print(dp[N])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(999999)
dicte = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
n, m = map(int, input().split())
arr = list(map(int, input().split()))
dp = [-1 for i in range(n+1)]
def cast(a, b):
    return int(str(a)+str(b))
def solve(curn):
    maxi = -1
    if dp[curn] != -1:
        return dp[curn] 
    for j in arr:
        if curn - dicte[j] >= 0:
            dp[curn-dicte[j]] = solve(curn-dicte[j])
            if dp[curn-dicte[j]] == None:
                maxi = max(j, maxi)
            else:
                maxi = max(cast(j, dp[curn-dicte[j]]), maxi)
    if maxi == -1:
        return None
    return maxi
print(solve(n))

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())


def cast(a, b):
    return int(str(a)+str(b))


n, m = mi()
match = [2,5,5,4,5,6,3,7,6]
vals = [1,2,3,4,5,6,7,8,9]
arr = lmi()
dp = [-1 for i in range(n+2)]
dp[0] = 0
for i in range(n):
    if dp[i] != -1:
        for j in range(9):
            if i+match[j] <= n+1:
                tmp = cast(vals[j], dp[i])
                if tmp > dp[i+match[j]]:
                    dp[i+match[j]] = tmp
print(str(dp[-1])[:-1])

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
lmi = lambda: list(map(int, input().split()))
mi = lambda: map(int, input().split())


def cast(a, b):
    return int(str(a)+str(b))


n, m = mi()
match = [2,5,5,4,5,6,3,7,6]
vals = [1,2,3,4,5,6,7,8,9]
arr = lmi()
dp = [-1 for i in range(n+2)]
dp[0] = 0
for i in range(n):
    if dp[i] != -1:
        for j in range(9):
            if i+match[j] <= n+1:
                tmp = cast(vals[j], dp[i])
                if tmp > dp[i+match[j]]:
                    dp[i+match[j]] = tmp
print(str(dp[-1])[:-2])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(9999999)
dicte = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
n, m = map(int, input().split())
arr = list(map(int, input().split()))
dp = [-1 for i in range(n+1)]
def cast(a, b):
    return int(str(a)+str(b))
def solve(curn):
    maxi = -1
    if dp[curn] != -1 or dp[curn] == None:
        return dp[curn]

    for j in arr:
        if curn - dicte[j] >= 0:
            dp[curn-dicte[j]] = solve(curn-dicte[j])
            if dp[curn-dicte[j]] == None:
                maxi = max(j, maxi)
            else:
                maxi = max(cast(j, dp[curn-dicte[j]]), maxi)
    if maxi == -1:
        return None
    return maxi
print(solve(n))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(999999)
dicte = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
n, m = map(int, input().split())
arr = list(map(int, input().split()))
dp = [-1 for i in range(n+1)]
def cast(a, b):
    return int(str(a)+str(b))
def solve(curn):
    maxi = -1
    if dp[curn] != -1:
        return dp[curn]

    for j in arr:
        if curn - dicte[j] >= 0:
            dp[curn-dicte[j]] = solve(curn-dicte[j])
            if dp[curn-dicte[j]] == None:
                maxi = max(j, maxi)
            else:
                maxi = max(cast(j, dp[curn-dicte[j]]), maxi)
    if maxi == -1:
        return None
    return maxi
print(solve(n))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(999999)
dicte = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
n, m = map(int, input().split())
arr = list(map(int, input().split()))
dp = [-1 for i in range(n+1)]
def cast(a, b):
    return int(str(a)+str(b))
def solve(curn):
    maxi = -1
    if dp[curn] != -1:
        return dp[curn]
    if curn in dicte.values():
        for j in arr:
            if curn - dicte[j] == 0:
                maxi = max(j, maxi)
        if maxi == -1:
            return None
        return maxi
    for j in arr:
        if curn - dicte[j] >= 0:
            z = solve(curn-dicte[j])
            if z == None:
                maxi = max(j, maxi)
            else:
                maxi = max(cast(j, solve(curn - dicte[j])), maxi)
    if maxi == -1:
        return None
    dp[curn] = maxi
    return maxi
print(solve(n))

Submission status: Wrong Answer

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

num = [
    [1, 2],
    [2, 5],
    [3, 5],
    [4, 4],
    [5, 5],
    [6, 6],
    [7, 3],
    [8, 7],
    [9, 6]
]
num = [x for x in num if x[0] in A]
num.sort(key=lambda x: x[1])

ans = []


def solve(k):
    for x in num:
        if x[1] <= k:
            k -= x[1]
            ans.append(x[0])
            break
    return k


def solve2(k, l):
    cost = 0
    for x in num:
        if x[0] == l:
            cost = x[1]
            break
    for x in num:
        if x[0] > l and k >= x[1]-cost:
            k -= x[1]-cost
            return (x[0], k)

    return (0, k)


prev = 0
k = N

while(prev != k):
    prev = k
    k = solve(k)
num.sort(reverse=True)


for i in range(len(ans)):
    tmp = solve2(k, ans[i])
    if tmp[0] != 0:
        ans[i] = tmp[0]
        k = tmp[1]
    else:
        break
num.sort(key=lambda x: x[1], reverse=True)

for i in reversed(range(len(ans))):
    if k == 0:
        break
    for x in num:
        if x[0] == ans[-1]:
            k += x[1]
            break
    for x in num:
        if x[1] <= k:
            ans[i] = x[0]
            k -= x[1]
            break
print("".join(map(str, ans)))