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

N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort()
A.reverse()

sys.setrecursionlimit(100000)

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

A_num = [(num[a], -a) for a in A]
A_num.sort()

min_A = -A_num[0][1]
min_num = A_num[0][0]
keta_max = N//min_num

def solve(d, amari):
    if d <= 0 and amari > 0:
        return None
    if amari < 0:
        return None
    elif amari == 0:
        if d == 0:
            return ""
        else:
            return None
    if amari < d*min_num:
        return None
    elif amari == d*min_num:
        return str(min_A) * d
    elif amari < d*(min_num+1):
        new_d = amari - d*min_num
        temp = solve(new_d, amari-(d-new_d)*min_num)
        if temp == None:
            return None
        else:
            temp1 = str(min_A) * (d-new_d) + temp
            temp2 = temp + str(min_A) * (d-new_d)
            if int(temp1) >= int(temp2):
                return temp1
            else:
                return temp2
    for a in A:
        temp = solve(d-1, amari-num[a])
        if temp != None:
            return str(a) + temp
    return None
    
for keta in range(keta_max, 0, -1):
    ans = solve(keta, N)
    if ans:
        break
print(ans)

Submission status: Wrong Answer

Solution code:

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

# NUM_DICT = {
#     '2': [1],
#     '3': [7],
#     '4': [4],
#     '5': [2, 3, 5],
#     '6': [6, 9],
#     '7': [8]
# }
# NUMs = sorted(map(int, NUM_DICT.keys()))

N, M = map(int, raw_input().split())
As = map(int, raw_input().split())

num_dict = {}
for a in As:
    num = NUMs[a]
    if a not in num_dict.items():
        num_dict[str(num)] = a
    elif num_dict[str(num)] < a:
        num_dict[str(num)] = a
nums = sorted(map(int, num_dict))

#print nums, num_dict

remove = []
for i in nums:
    for j in nums:
        if i + j in nums:
            remove.append(i + j)
        if j > i and j % i == 0:
            remove.append(j)
nums = sorted(list(set(nums) - set(remove)))

#print nums

int_nums = [0] * len(nums)
int_nums[0] = N // nums[0]
#print int_nums

#print zip(nums, int_nums)

rest = N - sum(map(lambda (a,b): a * b, zip(nums, int_nums)))
while rest > 0:
    for i in range(1, len(nums)):
        if rest == nums[i]:
            int_nums[i] += 1
            rest = 0
            break
    if rest != 0:
        if rest > nums[1]:
            int_nums[1] += 1
            rest -= nums[1]
        else:
            int_nums[0] -= 1
            rest += nums[0]


i = ''
for m, n in zip(nums, int_nums):
    i += str(num_dict[str(m)]) * n

print ''.join(sorted(i, reverse=True))

Submission status: Wrong Answer

Solution code:
import math
import copy
import bisect







def nCast(number):
    if type(number)==str:
        return int(number)
    for idx in range(0,len(number)):
        if type(number[idx])==str:

            number[idx]=int(number[idx])
        else:
            nCast(number[idx])
    return number
    
def inputArr(w):
    l=list()
    for idx in range(0,w):
        l.append(input())
    return l
def inputArr1(w):
    l=list()
    for idx in range(0,w):
        l.append(input().split())
    return l

n=nCast(input().split())
m=nCast(input().split())

def cmp(l1,l2):

    if len(l1)!=len(l2):
        return len(l1)-len(l2)
#     for idx in range(0,len(l1)):
#         if l1[idx]!=l2[idx]:
#             return l1[idx]-l2[idx]
    return 0
def func():
    l=list()
    nn=[1,2,3,4,5,6,7,8,9]
    s=set(m)
    mm=[2,5,5,4,5,6,3,7,6]
    d=dict()
    for idx in nn:
        if idx in s:
            if idx==2 and 5 in s:
                continue
            if idx==3 and 5 in s:
                continue
            if idx==2 and 3 in s:
                continue
            if idx==6 and 9 in s:
                continue
            d[nn[idx-1]]=mm[idx-1]
    for idx in range(0,n[0]+1):
        l.append(list())
    for idx in range(1,n[0]+1):
        for idy in d:
            if idx-d[idy]>0:
                tmp=l[idx-d[idy]][:]
                if len(tmp)==0:
                    continue
                tmp.append(idy)
                #tmp.sort(reverse=True)
                if cmp(tmp,l[idx])>0:
                    l[idx]=tmp
            elif idx-d[idy]==0:
                max=0
                for dd in d:
                    if d[dd]==idx and dd>max:
                        max=dd
                if cmp([max],l[idx])>0:
                    l[idx]=[max]

    result=""
    l[-1].sort(reverse=True)
    for idx in range(0,len(l[-1])):
        result=result+str(l[-1][idx])
    return result



print(func())

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
hon=[2,5,5,4,5,6,3,7,6]
a=list(map(int, input().split()))
s=sorted(set([hon[i-1] for i in a]))
t=[0]*10
for i in range(9):
    if i+1 in a:t[hon[i]]=i+1
if len(s)>1:x=s[0]*s[1]+1
else:x=n
dp=[[-100]*(x+1) for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    for j in range(x+1):
        if j%s[i-1]==0:
            dp[i][j]=max(dp[i][j],j//s[i-1])
        for k in range(1,j+1):
            if (j-k)%s[i-1]==0:
                dp[i][j]=max(dp[i][j],(j-k)//s[i-1]+dp[i-1][k])
ans=[]
if n>x:
    ans+=[min(s)]*-(-(n-x)//min(s))
    n=n+(-(n-x)//min(s))*min(s)
from itertools import product
for i in product(s,repeat=dp[-1][n]):
    if sum(i)==n:break
ans+=list(i)
import bisect
ansf=[]
for i in ans:
    bisect.insort_left(ansf,t[i])
print(*ansf[::-1],sep='')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
limits = [int(i) for i in input().split()]
necessary = [2, 5, 5, 4, 5, 6, 3, 7, 6]

mapped = [necessary[i-1] for i in limits]

min_val = min(mapped)
many_num = 0
many_num_needs = 0
for i in range(M):
    if mapped[i] == min_val:
        many_num = limits[i]
        many_num_needs = mapped[i]
        break

many_count = int(N / many_num_needs)
amari = N % many_num_needs

while True:
    if sum(mapped) == N:
        print(''.join(map(str, sorted(mapped)[::-1])))
        exit()
    elif amari not in mapped:
        many_count -= 1
        amari = N - (many_num_needs * many_count)
    else:
        break

low_num = 0
for i in range(M):
    if mapped[i] == amari:
        low_num = limits[i]
        break

if many_num < low_num:
    print(low_num, end='')

[print(many_num, end='') for i in range(many_count)]

if low_num <= many_num:
    print(low_num)
else:
    print('')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(x) - 1 for x in input().split()]
match = [2, 5, 5, 4, 5, 6, 3, 7, 6]
for a in range(9):
  if a not in A:
    match[a] = 0
match.reverse()
L = [[m, 9 - i] for i, m in enumerate(match)]
DP = [[0, []] for i in range(N + 1)]
for i in range(1, N + 1):
  for m, l in L:
    if i >= m:
      a = DP[i - m][1] + [str(l)]
      b = int(''.join(sorted(a, reverse=True)))
      if b > DP[i][0]:
        DP[i] = [b, a]
print(DP[-1][0])

Submission status: Wrong Answer

Solution code:

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

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

match_num=[2,5,5,4,5,6,3,7,6]
match_num2=[]
for a in A:
    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=[]
    min_dig=min(dig_res,dig_num)
    for i in range(l**min_dig):
        res=""
        r=0
        for j in range(min_dig):
            res+=str(match_num3[(i//(l**j))%l][1])
            r+=match_num3[(i//(l**j))%l][0]
        if r-min_dig*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)
    ans=""
    flag=True
    for i in range(len(str(max_res))):
        if int(str(max_res)[i])<=most and flag:
            ans += str(most)*(dig_num-min_dig)
            flag=False
        ans += str(max_res)[i]
    if flag:
        ans += str(most)*(dig_num-min_dig)
    print(ans)

Submission status: Wrong Answer

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

costs = [2,5,5,4,5,6,3,7,6,1000]

def main():
    min_a = 10-1
    for a in A:
        if costs[a-1] < costs[min_a-1]:
            min_a = a
    rep = N//costs[min_a-1]
    res = N%costs[min_a-1]
    if res==0:
        print(str(min_a)*rep)
        return

    # two chars
    cands = []
    i = 1
    while costs[min_a-1]*i+res <= 7:
        for a in A:
            if (costs[min_a-1]*i+res) % costs[a-1] == 0:
                cands.append(a)
        if len(cands)>0:
            break
        i += 1
    if len(cands)>0:
        a = max(cands)
        rep = (N-costs[a-1]) // costs[min_a-1]
        if a>min_a:
            print(str(a) + str(min_a)*rep)
            return
        else:
            print(str(min_a)*rep + str(a))
            return
    
    # three chars
    while costs[min_a-1]*i+res <= 14:
        for a0 in A:
            for a1 in A:
                if (costs[min_a-1]*i+res) % (costs[a0-1]+costs[a1-1]) == 0:
                    cands.append(a0*10+a1)
        if len(cands)>0:
            break
        i += 1
    if len(cands)>0:
        a = max(cands)
        a0 = a//10
        a1 = a%10
        rep = (N-costs[a0-1]-costs[a1-1]) // costs[min_a-1]
        if min_a < a1:
            print(str(a0) + str(a1) + str(min_a)*rep)
        elif min_a < a0:
            print(str(a0) + str(min_a)*rep + str(a1))
        else:
            print(str(min_a)*rep + str(a0) + str(a1))
        return

    # four chars
    cands = []
    i = 1
    while costs[min_a-1]*i+res <= 21:
        for a0 in A:
            for a1 in A:
                for a2 in A:
                    if (costs[min_a-1]*i+res) % (costs[a0-1]+costs[a1-1]+costs[a2-1]) == 0:
                        cands.append(a0*100+a1*10+a2)
        if len(cands)>0:
            break
        i += 1
    if len(cands)>0:
        a = max(cands)
        a0 = a//100
        a1 = (a%100)//10
        a2 = a%10
        rep = (N-costs[a0-1]-costs[a1-1]-costs[a2-1]) // costs[min_a-1]
        if min_a < a2:
            print(str(a0) + str(a1) + str(a2) + str(min_a)*rep)
        elif min_a < a1:
            print(str(a0) + str(a1) + str(min_a)*rep + str(a2))
        elif min_a < a0:
            print(str(a0) + str(min_a)*rep + str(a1) + str(a2))
        else:
            print(str(min_a)*rep + str(a0) + str(a1) + str(a2))
        return


main()

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())  #複数数値入力
a=list(map(int, input().split()))  #リスト入力（数値)
needNum = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

a.sort()
need = list()
for i in range(m):
    need.append(needNum[a[i]])

minNum = a[need.index(min(need))]  #必要マッチ棒が一番少ない数
minNeed = min(need) #必要マッチ棒が一番少ない数の必要数

digit = n//minNeed
remain = n % minNeed


out = 0
for i in range(digit):
    if i == digit-1:
        if remain != 0:
            for j in range(m):
                if minNeed +remain == needNum[a[-1-j]]:
                    out = a[-1-j]
                    break
        else:
            out = minNum

    elif remain != 0:
        for j in range(m):
            if minNeed+remain >= needNum[a[-1-j]]:
                out = a[-1-j]
                remain -= needNum[a[-1-j]]-minNeed
                break
    else:
        out = minNum

    print( out, end="")

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
cost = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
can_cost = sorted([cost[a] for a in A])
D = {}
for a in A:
    c = cost[a]
    D[c] = max(a, D.setdefault(c, -1))

min_cost = can_cost[0]
min_cost_num = D[min_cost]
K = N // min_cost
r = N - K * min_cost
temp = int("".join([str(min_cost_num)] * K))

dp = [[-1 for _ in range(min(r, K) + 1)] for __ in range(r + 1)]
dp[0][0] = temp


def f(v, l):
    L = list(str(v))
    set_L = set(L)
    cost_list = [cost[int(a)] for a in set_L]
    min_cost = min(cost_list)
    num = D.setdefault(min_cost + l, -1)
    if num == -1:
        return -1

    min_cost_num = D[min_cost]
    L[L.index(str(min_cost_num))] = str(num)
    L.sort(reverse=True)
    return int("".join(L))


for k in range(min(r, K)):
    for n in range(r):
        v = dp[n][k]
        if v == -1:
            continue
        for l in range(1, r - n + 1):
            dp[n + l][k + 1] = max(dp[n + l][k + 1], f(v, l))

print(max(dp[r]))

Submission status: Wrong Answer

Solution code:
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


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(matches)
mi = 100
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
r = N - nums*mi

Q = []
Q.append(['', r])
while Q:
    add, r = Q.pop(0)
    #print("add->", add, r)
    if r < 0:
        Q.append([add, r+mi])
    elif 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]])
print(1/0)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
li = list(map(int, input().split()))
di = {}
for i, d in enumerate([2,5,5,4,5,6,3,7,6], 1):
    di[i] = d

# honsuu list
ns = set()
# honsuu-> disit list
n2d = {}
for a in li:
    hon = di[a]
    ns.add(hon)
    if (hon not in n2d) or (n2d[hon] < a):
        n2d[hon] = a
ns = list(ns)
ns.sort(reverse=True)

from collections import Counter, deque
cnt = Counter()
Q = deque()
for hon in ns:
    if n - hon >= 0:
        Q.append(((hon,), n - hon))
while len(Q) > 0:
    lis, remain = Q.pop()
    if remain == 0:
        break
    for hon in ns:
        if remain - hon >= 0:
            Q.append((lis + (hon,), remain - hon))

digits = [n2d[n] for n in lis]
digits.sort(reverse=True)

print(*digits, sep='')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
l=list(map(int,input().split()))
count=[0,2,5,5,4,5,6,3,7,6]
maxlen=0
ldic = [[ll,count[ll]] for ll in l]
ldic=sorted(ldic,key=lambda x:x[1])
minc=ldic[0][1]
maxlen=N//ldic[0][1]
n=N%ldic[0][1]
ans=list(str(ldic[0][0]) * maxlen)

p=0
ldic=sorted(ldic,key=lambda x:x[0])

while n!= 0 and p != maxlen-1:
	for i in range(M)[::-1]:
		if n >= ldic[i][1]-minc and ldic[0][0] < ldic[i][0]:
			n -= ldic[i][1]-minc
			ans[p]=str(ldic[i][0])
			p += 1
			break

while n!= 0:
	for j in range(M)[::-1]:
		if n == ldic[j][1]-minc:
			n -= ldic[j][1]-minc
			ans[p]=str(ldic[j][0])

for i in range(len(ans)):
	print(ans[i],end="")
print()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
match=[9999,2,5,5,4,5,6,3,7,6]
uses=[ [i,9999] for i in range(10)]

for i in A:
    uses[i][1]=match[i]

uses.sort(key= lambda x:x[1])
maxyou=[uses[i][1] for i in range(M)]
ans=''
while True:
    if N==0:
        alice=[int(i) for i in ans]
        alice.sort(reverse=True)
        ans=''
        for i in alice:
            ans+=str(i)
        print(ans)
        exit(0)


    pittari_chance=False
    pittari_key=0
    for s in maxyou:
        if N-s==0:
            pittari_chance=True
            pittari_key=s
            N-=s
            break
    if pittari_chance:
        # triple
        for a in maxyou:
            for b in maxyou:
                for c in maxyou:
                    if a+b+c==pittari_key:
                        anss = []
                        for i in range(len(uses)):
                            if a == uses[i][1]:
                                anss.append(uses[i][0])
                        ans += str(max(anss))
                        anss = []
                        for i in range(len(uses)):
                            if b == uses[i][1]:
                                anss.append(uses[i][0])
                        ans += str(max(anss))
                        anss = []
                        for i in range(len(uses)):
                            if c == uses[i][1]:
                                anss.append(uses[i][0])
                        ans += str(max(anss))
                        alice = [int(i) for i in ans]
                        alice.sort(reverse=True)
                        ans = ''
                        for i in alice:
                            ans += str(i)
                        print(ans)
                        exit(0)

        #double up
        for a in maxyou:
            for b in maxyou:
                if a+b==pittari_key:
                    anss = []
                    for i in range(len(uses)):
                        if a == uses[i][1]:
                            anss.append(uses[i][0])
                    ans += str(max(anss))
                    anss = []
                    for i in range(len(uses)):
                        if b == uses[i][1]:
                            anss.append(uses[i][0])
                    ans += str(max(anss))
                    alice = [int(i) for i in ans]
                    alice.sort(reverse=True)
                    ans = ''
                    for i in alice:
                        ans += str(i)
                    print(ans)
                    exit(0)

        anss=[]
        for i in range(len(uses)):
            if pittari_key==uses[i][1]:
                anss.append(uses[i][0])
        ans+=str(max(anss))

    if N-(min(maxyou)*3)<min(maxyou):
        for a in maxyou:
            for b in maxyou:
                for c in maxyou:
                    if a+b+c==pittari_key:
                        anss = []
                        for i in range(len(uses)):
                            if a == uses[i][1]:
                                anss.append(uses[i][0])
                        ans += str(max(anss))
                        anss = []
                        for i in range(len(uses)):
                            if b == uses[i][1]:
                                anss.append(uses[i][0])
                        ans += str(max(anss))
                        anss = []
                        for i in range(len(uses)):
                            if c == uses[i][1]:
                                anss.append(uses[i][0])
                        ans += str(max(anss))
                        alice = [int(i) for i in ans]
                        alice.sort(reverse=True)
                        ans = ''
                        for i in alice:
                            ans += str(i)
                        print(ans)
                        exit(0)

    # double up
    if N-min(maxyou)*2<min(maxyou):
        for a in maxyou:
            for b in maxyou:
                if a + b == N:
                    anss = []
                    for i in range(len(uses)):
                        if a == uses[i][1]:
                            anss.append(uses[i][0])
                    ans += str(max(anss))
                    anss = []
                    for i in range(len(uses)):
                        if b == uses[i][1]:
                            anss.append(uses[i][0])
                    ans += str(max(anss))
                    alice = [int(i) for i in ans]
                    alice.sort(reverse=True)
                    ans = ''
                    for i in alice:
                        ans += str(i)
                    print(ans)
                    exit(0)

    if N==0:
        alice=[int(i) for i in ans]
        alice.sort(reverse=True)
        ans=''
        for i in alice:
            ans+=str(i)
        print(ans)
        exit(0)

    N-=uses[0][1]
    ans+=str(uses[0][0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = input().split()
n = int(n)
m = int(m)
a = input().split()  
for i in range(m):
    a[i] = int(a[i])
a.sort()
ansstr = ""
if 1 in a:
    num1 = n // 2
    n = n % 2
    if n == 1:
        if 7 in a and ansstr == "":
            ansstr = "7" + "1" * (num1 - 1)
        if 5 in a and ansstr == "":
            ansstr = "5" + "1" * (num1 - 2)
        if 3 in a and ansstr == "":
            ansstr = "3" + "1" * (num1 - 2)
        if 2 in a and ansstr == "":
            ansstr = "2" + "1" * (num1 - 2)
        if 8 in a and ansstr == "":
            ansstr = "8" + "1" * (num1 - 3)
    else:
        ansstr = "1" * num1  
if 7 in a and ansstr == "":
    num7 = n // 3
    n = n % 3
    if n == 2:
        if 5 in a and ansstr == "":
            ansstr = "7" * (num7 - 1) + "5"
        if 3 in a and ansstr == "":
            ansstr = "7" * (num7 - 1) + "3"
        if 2 in a and ansstr == "":
            ansstr = "7" * (num7 - 1) + "2"
    elif n == 1:
        if 4 in a and ansstr == "":
            ansstr = "7" * (num7 - 1) + "4"
        if 8 in a and ansstr == "":
            ansstr = "8" + "7" * (num7 - 2)
    else:
        ansstr = "7" * num7  
if 4 in a and ansstr == "":
    num4 = n // 4
    n = n % 4
    if n == 3:
        if 8 in a and ansstr == "":
            ansstr = "8" + "4" * (num4 - 1)
    elif n == 2:
        if 9 in a and ansstr == "":
            ansstr = "9" + "4" * (num4 - 1)
        if 6 in a and ansstr == "":
            ansstr = "6" + "4" * (num4 - 1)
    elif n == 1:
        if 5 in a and ansstr == "":
            ansstr = "5" + "4" * (num4 - 1)
        if 3 in a and ansstr == "":
            ansstr = "4" * (num4 - 1) + "3"
        if 2 in a and ansstr == "":
            ansstr = "4" * (num4 - 1) + "2"
    else:
        ansstr = "4" * num4  
def check5(j,n,ansstr):
    num5 = n // 5
    n = n % 5
    if n == 2:
        if 8 in a and ansstr == "":
            ansstr = "8" + str(j) * (num5 - 1)
    elif n == 1:
        if 9 in a and ansstr == "":
            ansstr = "9" + str(j) * (num5 - 1)
        if 6 in a and ansstr == "":
            ansstr = "6" + str(j) * (num5 - 1)
    elif n == 0:
        ansstr = str(j) * num5
    else:
        ansstr = ""
    return(ansstr)
if 5 in a and ansstr == "":
    ansstr = check5(5,n,ansstr)
if 3 in a and ansstr == "":
    ansstr = check5(3,n,ansstr)
if 2 in a and ansstr == "":
    ansstr = check5(2,n,ansstr)
if 9 in a and ansstr == "":
    num9 = n // 6
    n = n % 6
    if n == 1:
        if 8 in a and ansstr == "":
            ansstr = "9" * (num9 - 1) + "8"
    elif n == 0:
        ansstr = "9" * num9
if 6 in a and ansstr == "":
    num6 = n // 6
    n = n % 6
    if n == 1:
        if 8 in a and ansstr == "":
            ansstr = "8" + "6" * (num6 - 1)
    elif n == 0:
        ansstr = "6" * num6
if 8 in a and ansstr == "":
    num8 = n // 7
    ansstr = "8" * num8


print(ansstr)

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
	if q == 0:
		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]
	if q == 0:
		break
kan = 0

co.sort(reverse = True)

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

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
cost = [0,2,5,5,4,5,6,3,7,6]
from collections import defaultdict
costdict = defaultdict(lambda : 10)

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

for a in A:
    costdict[a] = cost[a]

A = list(costdict.keys())
costA = sorted(A, key=lambda x: cost[x])
# A = list(costdict.keys())

p = []
for a in A:
    # print("a: ", a, "cost[a] = ", cost[a])
    p.append( (cost[a], a) )
    # costdict[a] = cost[a]

costp = sorted(p)
# print("costp: ", costp)

costA = [ z[0] for z in costp]
A = [ z[1] for z in costp]

# print("A: {}, costA: {}".format(A, costA))

div  = N // costA[0]
rest = N % costA[0]

# print("div: ", div, rest)
# while not (rest in costA and not any(rest % z == 0 for z in costp[1:])) :
while not rest in costA :
    # print("rest: ", rest)
    # print("div: ", div)
    rest += costp[0][0]# costA[0]
    div -= 1


idx = costA.index(rest)
last = costp[idx][1]

if costp[0][1] < costp[idx][1]:
    print("".join(  map(str, [costp[idx][1]] + [str(costp[0][1])]*rest)))
else:
    print(str(costp[0][1])*rest + "".join(  map(str, [costp[idx][1]] )))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n,m = li()
a = list(li())

use = {}
for ai in a:
    if dic[ai] not in use.keys():
        use.update({dic[ai]: ai})
    else:
        dic[ai] = max(dic[ai], ai)
        
# 最大順
desc = {}
edge = {}
for idx, num in enumerate(sorted(use.values(), reverse=True)):
    desc.update({idx: num})
    edge.update({idx: dic[num]})
    
        
# 遷移
INF = float('inf')
dp = [[-INF]*len(use) for _ in range(n+1)]
dp[0] = [0]*len(use)
for i in range(1, n+1):
    for idx in range(len(use)):
        if i - edge[idx] < 0:
            continue
        
        if sum(dp[i]) < sum(dp[i-edge[idx]])+1:
            dp[i] = dp[i-edge[idx]].copy()
            dp[i][idx] += 1
            

        elif sum(dp[i]) == sum(dp[i-edge[idx]])+1:
            tmp = dp[i-edge[idx]].copy()
            tmp[idx] += 1
            
            for orgi, tmpi in zip(dp[i], tmp):
                if orgi == tmpi:
                    continue
                
                elif orgi > tmpi:
                    break
                
                else:
                    dp[i] = tmp.copy()
                    break
                

ans = ""
for num, cnt in zip(desc.values(), dp[-1]):
    ans = ans + str(num)*cnt
    
print(ans)

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)
b_list.sort()
for i in range(N + 1):
    for b in b_list:
        if i - items[b] >= 0:
            if dp[i - items[b]] != 0:
                dp[i] = max(dp[i - items[b]] * 10 + b, dp[i])
print(dp[N])

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
		for i in range(c):
			res = check(c-i,N,"")
			if res!="no":
				s1 = ans+res
				s2 = res+ans
				if s1<s2 and ans<s2:
					ans = s2
				elif s1>=s2 and ans<s1:
					ans = s1
#				if s[0:c-i]<res:
#					ans = res+ans
#				else:
#					ans = ans+res
				judge = True
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
	if q == 0:
		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]
	if q == 0:
		break
kan = 0
for i in range(p-1):
	if co[0] < co[-(i+1)]:
		kan = co[0]
		co[0] = co[-(i+1)]
		co[-(i+1)] = kan

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

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
li = list(map(int, input().split()))
di = {}
for i, d in enumerate([2,5,5,4,5,6,3,7,6], 1):
    di[i] = d

# honsuu list
ns = set()
# honsuu-> disit list
n2d = {}
for a in li:
    hon = di[a]
    ns.add(hon)
    if (hon not in n2d) or (n2d[hon] < a):
        n2d[hon] = a
ns = list(ns)
ns.sort(reverse=True)

from collections import Counter, deque
cnt = Counter()
Q = deque()
Q.append((tuple(), n))
while len(Q) > 0:
    lis, remain = Q.pop()
    if remain == 0:
        break
    for hon in ns:
        if remain - hon >= 0:
            Q.append((lis + (hon,), remain - hon))

digits = [n2d[n] for n in lis]
digits.sort(reverse=True)

print(*digits, sep='')