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(100000)
def greed(old_N, p, ans):
    if p >= len(A):
        return ''
    # print(old_N, A[p])
    new_N = old_N - cost[p]
    if new_N < 0:
        return greed(old_N, p+1, ans)
    elif new_N > 0:
        s = greed(new_N, p, ans)
        if s == '':
            s = greed(new_N, p+1, ans)
        else:
            ans += str(A[p]) + s
            return ans
    elif new_N == 0:
        ans += str(A[p])
        return ans
    if s == '':
        # print(old_N, A[p])
        return greed(old_N, p+1, ans)
    else:
        return s + str(A[p])

N, M = map(int, input().split())
A = list(map(int, input().split()))
cost = [10**5, 2, 5, 5, 4, 5, 6, 3, 7, 6]
cost = [cost[Ai] for Ai in A]
tmp = list(zip(cost, A))
tmp.sort()
cost = [t[0] for t in tmp]
A = [t[1] for t in tmp]
# print(cost)
# print(A)
ans = ''
ans = greed(N, 0, ans)
print(''.join(sorted(ans, reverse=True)))

Submission status: Wrong Answer

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

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

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

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

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

my_nums = []
for i in nums:
    my_nums.append(i)
my_nums.sort()
min_my_nums = min(my_nums)
x = 0
while N % min_my_nums != 0:
    x += 1
    for i in range(1, len(my_nums)):
        if (N - my_nums[i] * x) % min_my_nums == 0:
            N = N - my_nums[i] * x
            new_N = my_nums[i]
            break
max_min = N // min_my_nums
ans = ""
for i in range(N // min_my_nums):
    ans = str(nums[min_my_nums]) + ans
for i in range(x):
    if nums[new_N] > nums[min_my_nums]:
        ans = str(nums[new_N]) + ans
    else:
        ans = ans + str(nums[new_N])
print(ans)

Submission status: Wrong Answer

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

a = -1
cnt = 100

def check(n,r,S):
	if n==0:
		if r==0:
			return(S)
		else:
			return("no")
	for i in range(len(A)):
		if r-num[A[i]]>=0:
			s = check(n-1,r-num[A[i]],S+str(A[i]))
			if s!="no":
				return(s)
	return("no")

for i in range(len(A)):
	if cnt>=num[A[i]]:
		a = A[i]
		cnt = num[A[i]]
ans = ""
while N-cnt>=0:
	ans = ans+str(a)
	N -= cnt
A.sort()
A.reverse()
for i in range(len(A)):
	if N==num[A[i]]:
		if(a<A[i]):
			ans = str(A[i])+ans
		else:
			ans = ans+str(A[i])
		N = 0

if N==0:
	print(ans)
else:
	s = ""
	judge = False
	c = 0
	while judge==False:
		b = ans[-1:]
		ans = ans[:-1]
		c += 1
		N += num[int(b)]
		s = b+s
		res = check(c,N,"")
		if res!="no":
			if s<res:
				ans = res+ans
			else:
				ans = ans+res
			judge = True
			break;
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

ANSLIST=set()
def dfs(i,NOW):
    if NOW==N:
        L=sorted(list(i),reverse=True)
        
        x=int(("".join(L)))
        ANSLIST.add(x)

        if len(ANSLIST)>=15:
            print(max(ANSLIST))
            sys.exit()
    elif NOW>N:
        return
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])

def dfs2(i,NOW):
    ANS=0
    if NOW==N:
        L=sorted(list(i),reverse=True)
        
        x=int(("".join(L)))

        return x
    elif NOW>N:
        return 0
    else:
        for a in A:
            ANS=max(ANS,dfs2(i+str(a),NOW+M[a]))

    return ANS

A.sort(reverse=True)
A.sort(key=lambda x:M[x])

if N<=50:
    print(dfs2("",0))
else:
    dfs("",0)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

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

b = list(map(int,input().split()))
honsuu = [-1,2,5,5,4,5,6,3,7,6]
enabled = [False] * 10
for bb in b:
    enabled[bb] = True
if (enabled[6] & enabled[9]):
     enabled[6] = False;
if (enabled[5] & (enabled[2] | enabled[3])):
     enabled[2] = enabled[3] = False;
if (enabled[2] & enabled[3]):
     enabled[2] = False

a = []
for i in range(10):
    if (enabled[i]):
        a.append(i)

if enabled[1]:
    if n % 2 == 1:
        if enabled[7]:
            res = "7" + ((n - 3) // 2) * "1"
        elif enabled[5]:
            res = "5" + ((n - 5) // 2) * "1"
        elif enabled[3]:
            res = "3" + ((n - 5) // 2) * "1"
        elif enabled[2]:
            res = "2" + ((n - 5) // 2) * "1"
        else:
            res = "8" + ((n - 7) // 2) * "1"
        print(res)
    else:
        print("1" * (n // 2))
    exit()

if enabled[7]:
    if n % 3 == 1:
        if enabled[4]:
            res = "7" * ((n - 4) // 3) + "4"
        elif enabled[8]:
            res = "8" + "7" * ((n - 7) // 3)
        elif enabled[5]:
            res = "7" * ((n - 10) // 3) + "55"
        elif enabled[3]:
            res = "7" * ((n - 10) // 3) + "33"
        elif enabled[2]:
            res = "7" * ((n - 10) // 3) + "22"
        print(res)
    elif n % 3 == 0:
        print("7" * (n // 3))
    else:
        if enabled[5]:
            res = "7" * ((n - 5) // 3) + "5"
        elif enabled[3]:
            res = "7" * ((n - 5) // 3) + "3"
        elif enabled[2]:
            res = "7" * ((n - 5) // 3) + "2"
        elif enabled[4]:
            res = "7" * ((n - 8) // 3) + "44"
        elif enabled[8]:
            res = "88" + "7" * ((n - 14) // 3)
        print(res)
    exit()

if enabled[4]:
    if n % 4 == 0:
        print("4" * (n // 4))
    elif n % 4 == 1:
        if enabled[5]:
            res = "5" + "4" * ((n - 5) // 4)
        elif enabled[3]:
            res = "4" * ((n - 5) // 4) + "3"
        elif enabled[2]:
            res = "4" * ((n - 5) // 4) + "2"
        elif enabled[8]:
            if enabled[9]:
                res = "98" + ((n - 13) // 4) * "4"
            elif enabled[6]:
                res = "86" + ((n - 13) // 4) * "4"
            else:
                res = "888" + ((n - 21) // 4) * "4"
        print(res)
    elif n % 4 == 2:
        if enabled[9]:
            res = "9" + "4" * ((n - 6) // 4)
        elif enabled[6]:
            res = "6" + "4" * ((n - 6) // 4)
        elif enabled[5]:
            res = "55" + "4" * ((n - 10) // 4)
        elif enabled[3]:
            res = "4" * ((n - 10) // 4) + "33"
        elif enabled[2]:
            res = "4" * ((n - 10) // 4) + "22"
        elif enabled[8]:
            res = "88" + ((n - 14) // 4) * "4"
        print(res)
    else:
        if enabled[8]:
            res = "8" + "4" * ((n - 7) // 4)
        elif enabled[9]:
            if enabled[5]:
                res = "95" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "9" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "9" + "4" * ((n - 11) // 4) + "2"
        elif enabled[6]:
            if enabled[5]:
                res = "65" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "6" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "6" + "4" * ((n - 11) // 4) + "2"
        elif enabled[5]:
            res = "555" + "4" * ((n - 15) // 4)
        elif enabled[3]:
            res = "4" * ((n - 15) // 4) + "333"
        else:
            res = "4" * ((n - 15) // 4) + "222"
        print(res)
    exit()

for i in [5, 3, 2]:
    c = str(i)
    if enabled[i]:
        if n % 5 == 0:
            print(c * (n // 5))
        elif n % 5 == 1:
            if enabled[9]:
                res = "9" + c * ((n - 6) // 5)
            elif enabled[6]:
                res = "6" + c * ((n - 6) // 5)
            else:
                res = "888" + c * ((n - 21) // 5)
            print(res)
        elif n % 5 == 2:
            if enabled[9]:
                res = "99" + c * ((n - 12) // 5)
            elif enabled[8]:
                res = "8" + c * ((n - 7) // 5)
            else:
                res = "66" + c * ((n - 12) // 5)
            print(res)
        elif n % 5 == 3:
            if enabled[9]:
                res = "999" + c * ((n - 18) // 5)
            elif enabled[6]:
                if enabled[8]:
                    res = "86" + c * ((n - 13) // 5)
                else:
                    res = "666" + c * ((n - 18) // 5)
            else:
                res = "8888" + c * ((n - 28) // 5)
            print(res)
        else:
            if enabled[9]:
                res = "9999" + c * ((n - 24) // 5)
            elif enabled[8]:
                res = "88" + c * ((n - 14) // 5)
            else:
                res = "6666" + c * ((n - 24) // 5)
            print(res)
        exit()

if enabled[9]:
    c = "9"
    if n % 6 == 0:
        print(c * (n // 6))
    elif n % 6 == 1:
        print(c * ((n - 7) // 6) + "8")
    elif n % 6 == 2:
        print(c * ((n - 14) // 6) + "88")
    elif n % 6 == 3:
        print(c * ((n - 21) // 6) + "888")
    elif n % 6 == 4:
        print(c * ((n - 28) // 6) + "8888")
    else:
        print(c * ((n - 35) // 6) + "88888")
    exit()

if enabled[6]:
    c = "6"
    if n % 6 == 0:
        print(c * (n // 6))
    elif n % 6 == 1:
        print("8" + c * ((n - 7) // 6))
    elif n % 6 == 2:
        print("88" + c * ((n - 14) // 6))
    elif n % 6 == 3:
        print("888" + c * ((n - 21) // 6))
    elif n % 6 == 4:
        print("8888" + c * ((n - 28) // 6))
    else:
        print("88888" + c * ((n - 35) // 6))
    exit()

print("8" * (n // 7))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A = list(map(int,input().split()))
costToValue = {}
costs = [-1,2,5,5,4,5,6,3,7,6]
values = set()
for a in A:
    if a not in values:
        costToValue[costs[a]] = a
        values.add(a)
    else:
        if costToValue[costs[a]] < a:
            costToValue[costs[a]] = a
dp = [[0,0,0,0,0,0,0,0] for _ in range(N+1)] #posssible, digitNum, count2, count3, count4,...
dp[0][0] = 1 #possibility, digitNum
for i in range(1,N+1):
    maxValue = -1
    maxA = -1
    for a in costToValue:
        if a > i:
            continue
        if dp[i-a][0] == 0:
            continue
        dp[i][0] = 1
        if dp[i-a][1] > maxValue:
            maxValue = dp[i-a][1]
            maxA = a
    if maxValue == -1:
        continue
    dp[i][0] = 1
    dp[i][1] = maxValue + 1
    for j in range(2,8):
        dp[i][j] = dp[i-maxA][j]
    dp[i][maxA] += 1
# for i in range(N+1):
    # print(dp[i])

solution = dp[N]
digits=[]
for i in range(2,8):
    for j in range(solution[i]):
        digits.append(costToValue[i])
digits.sort(reverse = True)
print("".join(list(map(str,digits))))

Submission status: Wrong Answer

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

cost_define = [2,5,5,4,5,6,3,7,6]

C = []
A = sorted(A)
for a in A:
  C.append(cost_define[a-1])

#まず最小コストで桁を決定
min_cost = 7
min_cost_index = 0
for i in range(len(C)):
  #あと勝ち
  if (C[i] <= min_cost):
    min_cost_index = i
    min_cost = C[i]
min_cost_number = A[min_cost_index]
keta = N // min_cost
amari = (N - (keta*min_cost))
#print(min_cost, min_cost_number, keta, amari)

#余ったら最大桁を増やしていく
res = 0
while (0 < keta):
  if (0 < amari):
    found = False
    for (c,a) in zip(reversed(C),reversed(A)):
      #print(c,a,amari)
      c -= min_cost
      if (c <= amari):
        amari -= c
        res += a*(10**(keta-1))
        found = True
        break
    if not found:
      res += min_cost_number*(10**(keta-1))
  else:
    res += min_cost_number*(10**(keta-1))
  keta -= 1
  #print(keta, res)
print(res)

Submission status: Wrong Answer

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

A = list(map(int,input().split()))
dp = [False for i in range(N+10)]
memo = [[] for i in range(N+10)]
taiou = [[1,2],[2,5],[3,5],[4,4],[5,5],[6,6],[7,3],[8,7],[9,6]]
matchi = []
for i in range(1,10):
    if i in A:
        matchi.append(taiou[i-1])
matchi = sorted(matchi,key = lambda x:-x[0])
matchi = sorted(matchi,key = lambda x:x[1])
# for i in range(1,len(matchi)):
#     if matchi[i][1] == matchi[i-1][1]:

minma = matchi[0][1]
# print(matchi)
# print(minma)
# dp[0] = F
for i in range(len(matchi)):
    dp[matchi[i][1]] = True
    memo[matchi[i][1]].append(matchi[i][0])
for i in range(N):
    for j in range(len(matchi)):
        if dp[i-matchi[j][1]]:
            dp[i] = True
            memo[i] = memo[i] + memo[i-matchi[j][1]]
            memo[i].append(matchi[j][0])
            break
# print(dp)
# print(memo)
maxi = N
for i in range(N//minma,0,-1):
    if dp[N-i*minma]:
        maxi = i
        # print(maxi)
        break

ans = sorted([matchi[0][0]]*maxi + memo[N-maxi*minma],reverse = True)
for i in range(len(ans)):
    print(ans[i],sep='',end='')
print('')

Submission status: Wrong Answer

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

def solve(N, M, As):
    Ms = {num: c for num, c in Matches.items() if num in As}
    ans = 0
    digits = []
    for (dc, dnum) in [(c, num) for (num, c) in Ms.items()]:
        iN = N
        digit = str(dnum) * (iN // dc)
        iN -= dc * (iN // dc)
        if digit:
            digits.append((digit, dnum, iN))

    for digit, num, iN in digits:
        if iN == 0:
            ans = max(ans, int(digit))
        elif Ms[num] + iN in Ms.values():
            for m, c in [(m, c) for m, c in Ms.items() if c == Ms[num] + iN]:
                if m < num:
                    ans = max(ans, int(digit[:-1] + str(m)))
                else:
                    ans = max(ans, int(str(m) + digit[1:]))
    return ans

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

Submission status: Wrong Answer

Solution code:
cost=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int,input().split())
A=sorted(map(int,input().split()))
lowcost_i=A[0];lowcost=cost[A[0]]
for a in A:
    if cost[a]<lowcost:lowcost_i=a;lowcost=cost[a]
s=str(lowcost_i)*(N//lowcost)
l=N%lowcost
before_l=l
disit=0
#costがl+lowcost以下で最大のものを探索，上位から置換
while l>0:
    lll = {a:cost[a] for a in A if cost[a]<=l+lowcost}
    mmm = max(lll.keys())
    if mmm>lowcost_i:
        #print("p")
        s=s[:disit]+str(mmm)+s[disit+1:]
        l-=lll[mmm]-lowcost
        disit+=1
    else:
        #print("E")
        for k in sorted(lll.keys())[::-1]:
            if lll[k]==l+lowcost:
                s=s[:len(s)]+str(k)
                l=0
                break
    #print(s)
#print(lowcost_i, lowcost)
print(s)

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]
c = list(map(int,input().split()))
cc = [[0,0] for i in range(b)]
ccc = [[0,0] for i in range(b)]
c.sort(reverse = True)
for i in range(b):
	cc[i] = [c[i],k[c[i]-1]]
	ccc[i]= [c[i],k[c[i]-1]]

cc.sort(key = lambda x:x[1])
ccc.sort(reverse = True)
p = a // cc[0][1]
q = a % cc[0][1]
co = [cc[0][0] for i in range(p)]
for i in range(p):
	for j in range(b):
		if ccc[j][0] > cc[0][0] and q >= ccc[j][1] - cc[0][1]:
			co[i] = ccc[j][0]
			q -= ccc[j][1] - cc[0][1]
			break
for h in range(b):
	for i in range(p):
		for j in range(b):
			if q >= cc[j][1] - k[co[-(i+1)]-1] and cc[j][1] > k[co[-(i+1)]-1]:
				q -= cc[j][1] - k[co[-(i+1)]-1]
				co[-(i+1)] = cc[j][0]
				break
		if q == 0:
			break
	if q == 0:
		break


co = map(str,co)
aaa = ''.join(co)
print(aaa)

Submission status: Wrong Answer

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

Alist = [int(x) for x in input().split()]

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

items = {}
for a in Alist:
    items[a] = matchDict[a]

# 必要マッチ数の少ない順にソート
items = sorted(items.items(), key=lambda x: (x[1], -x[0]))

cache = 0
delList = []
for k, v in items:
    if cache == v:
        delList.append((k,v))
    else:
        cache = v
for x in delList:
    items.remove(x)

# 何桁作る？
mininum, mini = items[0]
keta = N // mini
amari = N % mini

result = str(mininum) * keta
modcount = 0
# 余りに応じて数値調整
if amari != 0:
    items = sorted(items, key=lambda x: (-x[1]))

    for k,v in items:
        if mininum == k:
            continue
        if v <= mini+amari:
            if k > mininum:
                while True:
                    moded = result[0:modcount]
                    result = result[modcount:]
                    result = moded + str(k) + result
                    result = result[:-1]
                    modcount += 1
                    amari = amari - (v - mini)
                    if v > mini+amari:
                        break
            elif mininum > k:
                result = result[:-1] + str(k)
                amari = amari - (v - mini)

        if amari == 0:
            break

print(result)

Submission status: Wrong Answer

Solution code:
arr = [10,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())),key = lambda x:arr[x])
dim = 0
num = 0
min_num = 0
for i in src:
    if arr[min_num] > arr[i]:
        if min_num <= i:
            min_num = i
for i in src:
    tmp = 1 + (N-arr[i])//arr[min_num]
    if dim <= tmp and num < i:
        dim = tmp
        num = i
s = str(num)
cnt = N - arr[num]
cnt_dim = 1
while(cnt_dim + 1 < dim):
    s += str(min_num)
    cnt -= arr[min_num]
    cnt_dim += 1
for i in src:
    if cnt == arr[i]:
        if i <= min_num:
            s += str(i)
            break
        else:
            s = s[:1] + str(i) + s[1:]
            break
print(s)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A = list(map(int,input().split()))
costToValue = {}
costs = [-1,2,5,5,4,5,6,3,7,6]
values = set()
for a in A:
    if a not in values:
        costToValue[costs[a]] = a
    else:
        if costToValue[costs[a]] < a:
            costToValue[costs[a]] = a
dp = [[0,0,0,0,0,0,0,0] for _ in range(N+1)] #posssible, digitNum, count2, count3, count4,...
dp[0][0] = 1 #possibility, digitNum
for i in range(1,N+1):
    maxValue = -1
    maxA = -1
    for a in costToValue:
        if a > i:
            continue
        if dp[i-a][0] == 0:
            continue
        dp[i][0] = 1
        if dp[i-a][1] > maxValue:
            maxValue = dp[i-a][1]
            maxA = a
    if maxValue == -1:
        continue
    dp[i][0] = 1
    dp[i][1] = maxValue + 1
    for j in range(2,8):
        dp[i][j] = dp[i-maxA][j]
    dp[i][maxA] += 1
# for i in range(N+1):
    # print(dp[i])

solution = dp[N]
digits=[]
for i in range(2,8):
    for j in range(solution[i]):
        digits.append(costToValue[i])
digits.sort(reverse = True)
print("".join(list(map(str,digits))))

Submission status: Wrong Answer

Solution code:
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

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

b = list(map(int,input().split()))
honsuu = [-1,2,5,5,4,5,6,3,7,6]
enabled = [False] * 10
for bb in b:
    enabled[bb] = True
if (enabled[6] & enabled[9]):
     enabled[6] = False;
if (enabled[5] & (enabled[2] | enabled[3])):
     enabled[2] = enabled[3] = False;
if (enabled[2] & enabled[3]):
     enabled[2] = False

a = []
for i in range(10):
    if (enabled[i]):
        a.append(i)

if enabled[1]:
    if n % 2 == 1:
        if enabled[7]:
            res = "7" + ((n - 3) // 2) * "1"
        elif enabled[5]:
            res = "5" + ((n - 5) // 2) * "1"
        elif enabled[3]:
            res = "3" + ((n - 5) // 2) * "1"
        elif enabled[2]:
            res = "2" + ((n - 5) // 2) * "1"
        else:
            res = "8" + ((n - 7) // 2) * "1"
        print(res)
    else:
        print("1" * (n // 2))
    exit()

if enabled[7]:
    if n % 3 == 1:
        if enabled[4]:
            res = "7" * ((n - 4) // 3) + "4"
        elif enabled[8]:
            res = "8" + "7" * ((n - 7) // 3)
        elif enabled[5]:
            res = "7" * ((n - 10) // 3) + "55"
        elif enabled[3]:
            res = "7" * ((n - 10) // 3) + "33"
        elif enabled[2]:
            res = "7" * ((n - 10) // 3) + "22"
        print(res)
    elif n % 3 == 0:
        print("7" * (n // 3))
    else:
        if enabled[5]:
            res = "7" * ((n - 5) // 3) + "5"
        elif enabled[3]:
            res = "7" * ((n - 5) // 3) + "3"
        elif enabled[2]:
            res = "7" * ((n - 5) // 3) + "2"
        elif enabled[4]:
            res = "7" * ((n - 8) // 3) + "44"
        elif enabled[8]:
            res = "88" + "7" * ((n - 14) // 3)
        print(res)
    exit()

if enabled[4]:
    if n % 4 == 0:
        print("4" * (n // 4))
    elif n % 4 == 1:
        if enabled[5]:
            res = "5" + "4" * ((n - 5) // 4)
        elif enabled[3]:
            res = "4" * ((n - 5) // 4) + "3"
        elif enabled[2]:
            res = "4" * ((n - 5) // 4) + "2"
        elif enabled[8]:
            if enabled[9]:
                res = "98" + ((n - 13) // 4) * "4"
            elif enabled[6]:
                res = "86" + ((n - 13) // 4) * "4"
            else:
                res = "888" + ((n - 21) // 4) * "4"
        print(res)
    elif n % 4 == 2:
        if enabled[9]:
            res = "9" + "4" * ((n - 6) // 4)
        elif enabled[6]:
            res = "6" + "4" * ((n - 6) // 4)
        elif enabled[5]:
            res = "55" + "4" * ((n - 10) // 4)
        elif enabled[3]:
            res = "4" * ((n - 10) // 4) + "33"
        elif enabled[2]:
            res = "4" * ((n - 10) // 4) + "22"
        elif enabled[8]:
            res = "88" + ((n - 14) // 4) * "4"
        print(res)
    else:
        if enabled[8]:
            res = "8" + "4" * ((n - 7) // 4)
        elif enabled[9]:
            if enabled[5]:
                res = "95" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "9" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "9" + "4" * ((n - 11) // 4) + "2"
        elif enabled[6]:
            if enabled[5]:
                res = "65" + "4" * ((n - 11) // 4)
            elif enabled[3]:
                res = "6" + "4" * ((n - 11) // 4) + "3"
            elif enabled[2]:
                res = "6" + "4" * ((n - 11) // 4) + "2"
        elif enabled[5]:
            res = "555" + "4" * ((n - 15) // 4)
        elif enabled[3]:
            res = "4" * ((n - 15) // 4) + "333"
        else:
            res = "4" * ((n - 15) // 4) + "222"
        print(res)
    exit()

for i in [5, 3, 2]:
    c = str(i)
    if enabled[i]:
        if n % 5 == 0:
            print(c * (n // 5))
        elif n % 5 == 1:
            if enabled[9]:
                res = "9" + c * ((n - 6) // 5)
            elif enabled[6]:
                res = "6" + c * ((n - 6) // 5)
            else:
                res = "888" + c * ((n - 21) // 5)
            print(res)
        elif n % 5 == 2:
            if enabled[8]:
                res = "8" + c * ((n - 7) // 5)
            elif enabled[9]:
                res = "99" + c * ((n - 12) // 5)
            else:
                res = "66" + c * ((n - 12) // 5)
            print(res)
        elif n % 5 == 3:
            if enabled[9]:
                res = "999" + c * ((n - 18) // 5)
            elif enabled[6]:
                if enabled[8]:
                    res = "86" + c * ((n - 13) // 5)
                else:
                    res = "666" + c * ((n - 18) // 5)
            else:
                res = "8888" + c * ((n - 28) // 5)
            print(res)
        else:
            if enabled[9]:
                res = "9999" + c * ((n - 24) // 5)
            elif enabled[8]:
                res = "88" + c * ((n - 14) // 5)
            else:
                res = "6666" + c * ((n - 24) // 5)
            print(res)
        exit()

if enabled[9]:
    c = "9"
    if n % 6 == 0:
        print(c * (n // 6))
    elif n % 6 == 1:
        print(c * ((n - 7) // 6) + "8")
    elif n % 6 == 2:
        print(c * ((n - 14) // 6) + "88")
    elif n % 6 == 3:
        print(c * ((n - 21) // 6) + "888")
    elif n % 6 == 4:
        print(c * ((n - 28) // 6) + "8888")
    else:
        print(c * ((n - 35) // 6) + "88888")
    exit()

if enabled[6]:
    c = "6"
    if n % 6 == 0:
        print(c * (n // 6))
    elif n % 6 == 1:
        print("8" + c * ((n - 7) // 6))
    elif n % 6 == 2:
        print("88" + c * ((n - 14) // 6))
    elif n % 6 == 3:
        print("888" + c * ((n - 21) // 6))
    elif n % 6 == 4:
        print("8888" + c * ((n - 28) // 6))
    else:
        print("88888" + c * ((n - 35) // 6))
    exit()

print("8" * (n // 7))

Submission status: Wrong Answer

Solution code:
import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

m = {}
m[1] = 2
m[2] = 5
m[3] = 5
m[4] = 4
m[5] = 5
m[6] = 6
m[7] = 3
m[8] = 7
m[9] = 6

ans = ''

N, M = map(int, input().split())
t = list(map(int, input().split()))
if 3 in t and 2 in t:
    t.remove(2)
if 3 in t and 5 in t:
    t.remove(3)
if 2 in t and 5 in t:
    t.remove(2)
if 6 in t and 9 in t:
    t.remove(6)
A = sorted(t, reverse=True)

matches = [m[v] for v in A]
matches = sorted(list(set(matches)))
mi = 10
mi_num = 0
for a in A:
    if m[a] < mi:
        mi = m[a]
        mi_num = a
matches.remove(mi)
A.remove(mi_num)

nums = N//mi
# print(nums)
# 最小個数のマッチ本数の数字をnums子作れる
r = N - nums*mi
#print("freq->", mi_num)
#print("mi->", mi)
#print("remaind->", r)
# print(matches)
# print(A)
# 余ったマッチと1このmiのマッチでより大き数を作れるならそうする


Q = []
Q.append(['', r])
while Q:
    add, r = Q.pop(0)
    #print("add->", add, r)
    if r < 0:
        continue
    if r == 0:
        cand = []
        for c in add:
            cand.append(int(c))
        cand.append(mi_num)
        cand = sorted(cand, reverse=True)
        l = len(cand)-1
        ans = ''
        for c in cand:
            if c == mi_num:
                ans += str(mi_num)*(nums-l)
            else:
                ans += str(c)
        print(ans)
        exit()
    else:
        r += mi
        for a in A:
            Q.append([add+str(a), r-m[a]])

Submission status: Wrong Answer

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

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

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

M = len(b_list)
for i in range(2, N + 1):
    for j in range(M):
        if i - items[b_list[j]] >= 0:
            if dp[i - items[b_list[j]]] != 0:
                dp[i] = max(dp[i - items[b_list[j]]] * 10 + b_list[j], dp[i])

print(dp[N])

Submission status: Wrong Answer

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

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

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

#dpの初期化
for i in range(m):
    if cost[a[i]] <= n:
        dp[cost[a[i]]]= [a[i]]


for i in range(0,n+1):
    for k in range(m):
        if i > cost[a[k]]:

            tmp = copy.copy(dp[i-cost[a[k]]])
            tmp.append(a[k])
            tmp.sort(reverse = True)
            #print(i,tmp)
            if len(tmp) > len(dp[i]) and len(tmp) != 1:
                dp[i] = tmp
            elif len(tmp) == len(dp[i]) and len(tmp) != 1:
                big = 1
                for s in range(len(tmp)):
                    if tmp[s] < dp[i][s]:
                        big = 0
                if(big):
                    dp[i] = tmp

ans = ""
for cha in dp[n]:
    ans = ans + str(cha)
print(ans)

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
k = [2,5,5,4,5,6,3,7,6]
c = list(map(int,input().split()))
cc = [[0,0] for i in range(b)]
ccc = [[0,0] for i in range(b)]
c.sort(reverse = True)
for i in range(b):
	cc[i] = [c[i],k[c[i]-1]]
	ccc[i]= [c[i],k[c[i]-1]]

cc.sort(key = lambda x:x[1])
ccc.sort(reverse = True)
p = a // cc[0][1]
q = a % cc[0][1]
co = [cc[0][0] for i in range(p)]
for i in range(p):
	for j in range(b):
		if ccc[j][0] > cc[0][0] and q >= ccc[j][1] - cc[0][1]:
			co[i] = ccc[j][0]
			q -= ccc[j][1] - cc[0][1]
			break

for i in range(p):
	for j in range(b):
		if q >= cc[j][1] - k[co[-(i+1)]-1] and cc[j][1] > k[co[-(i+1)]-1]:
			q -= cc[j][1] - k[co[-(i+1)]-1]
			co[-(i+1)] = cc[j][0]

co = map(str,co)
aaa = ''.join(co)
print(aaa)

Submission status: Wrong Answer

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

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

can_use = [False for i in range(9)]
match_num=[2,5,5,4,5,6,3,7,6]
match_num2=[]
for a in A:
    can_use[a-1]=True
    match_num2.append([match_num[a-1],a])
match_num2=sorted(match_num2,key=lambda x:x[1],reverse=True)
match_num2=sorted(match_num2,key=lambda x:x[0])

most=match_num2[0][1]
dig_num=N//match_num2[0][0]
dig_res=N%match_num2[0][0]

if dig_res==0:
    print(str(most)*dig_num)
else:
    match_num3=[]
    for i in range(M):
        if match_num2[i][0]>match_num2[0][0]:
            match_num3.append(match_num2[i])
    match_num3.append([match_num2[0][0],most])
    l=len(match_num3)
    res_pattern=[]
    for i in range(l**dig_res):
        res=""
        r=0
        for j in range(dig_res):
            res+=str(match_num3[(i//(l**j))%l][1])
            r+=match_num3[(i//(l**j))%l][0]
        if r-dig_res*match_num2[0][0]==dig_res:
            res_pattern.append(res)
    max_res=0
    for res in res_pattern:
        max_res=max(int(res),max_res)
    if int(str(max_res)[0])>most:
        print(str(max_res)+str(most)*(dig_num-dig_res))
    else:
        print(str(most)*(dig_num-dig_res)+str(max_res))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

def match(i):
    ANS=0
    for s in str(i):
        ANS+=M[int(s)]

    return ANS
        
ANSLIST=set()
def dfs(i,NOW):
    if NOW==N:
        L=sorted(list(i),reverse=True)
        
        x=int(("".join(L)))
        ANSLIST.add(x)

        if len(ANSLIST)>=500:
            #print(ANSLIST)
            print(max(ANSLIST))
            sys.exit()
    elif NOW>N:
        return
    else:
        for a in A:
            dfs(i+str(a),NOW+M[a])


A.sort(reverse=True)
#print(A)
A.sort(key=lambda x:M[x])
#print(A)

dfs("",0)