Problem:


Score : 400 points

Problem Statement

Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:

Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9).

The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6, respectively.

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

There exists an integer that can be formed by exactly N matchsticks under the conditions.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

The output may not fit into a 64-bit integer type.

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Wrong Answer

Solution code:
import math
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:
            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:
                max=0
                for dd in d:
                    if d[dd]==idx and dd>max:
                        max=dd
                if cmp([max],l[idx])>0:
                    l[idx]=[max]
            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

    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:
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
if True:
    N = 10000
    M = 9
    A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]



best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj



# print(best)
X = [0] + [-10**9] * N
bpre = -1
ll = 1
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    if b[0] > X[i]:
                        X[i] = b[0]
                        bpre = b
                        ll = 0
                else:
                    if X[i-b[1]]*10 + b[0] < X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])):
                        lll = 1

                    if max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]]))) > X[i]:
                        X[i] = max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
                        ll = lll
                        bpre = b
                

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

print(ans)
# print(len(ans))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest 118：D - Match Matching
import sys
sys.setrecursionlimit(1000000)


def det(cand, i, remain):
    # print 'First:', cand, i, remain, len(cand)
    if i >= len(cand):
        return False, cand
    # print 'Next'
    d = remain / cand[i][1]
    if d == 0:
        return False, cand
    for n in range(d, -1, -1):
        cand[i][2] = n
        if remain - n*cand[i][1] == 0:
            return True, cand
        # print cand, i, cand[i][1], remain - n*cand[i][1]
        found, cand = det(cand, i+1, remain - n*cand[i][1])
        if found:
            return True, cand
    return False, cand


def main():
    N, M = [int(i) for i in raw_input().strip().split(' ')]
    A = [int(i) for i in raw_input().strip().split(' ')]

    cand = [[1, 2, 0], [7, 3, 0], [4, 4, 0], [5, 5, 0], [3, 5, 0], [2, 5, 0], [9, 6, 0], [6, 6, 0], [8, 7, 0]]
    new_cand = []
    for c in cand:
        if c[0] in A:
            new_cand.append(c)
    # print new_cand
    #   [[7, 3, 0], [4, 4, 0], [3, 5, 0], [8, 7, 0]]

    found, new_cand = det(new_cand, 0, N)
    # print found, new_cand

    ds = sorted(new_cand, key=lambda x: x[0], reverse=True)
    s = ''
    for d in ds:
        s += str(d[0])*d[2]
    print s


if __name__ == '__main__':
    main()

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:
					ans = s2
				else:
					ans = s1
#				if s[0:c-i]<res:
#					ans = res+ans
#				else:
#					ans = ans+res
				judge = True
				break;
print(ans)

Submission status: Wrong Answer

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

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

X = [1, 7, 4, 5, 3, 2, 9, 6, 8, 0]
Y = [2, 3, 4, 5, 5, 5, 6, 6, 7, 0]

ANS = []


for i in range(9):
    if(X[i] in A):
        while(n>12):
            n -= Y[i]
            ANS.append(X[i])

A.append(0)
ind  = 0
for i in range(10):
    if(ind != 0):
        break
    for j in range(10):
        if(ind != 0):
            break
        for k in  range(10):
            if(ind != 0):
                break
            for l in range(10):
                if(ind != 0):
                    break
                for m in range(10):
                    if(ind != 0):
                        break
                    if(X[i] in A and X[j] in A and X[k] in A and X[l] in A and X[m] in A):
                        if(n == (Y[i] + Y[j] + Y[k] + Y[l] + Y[m])):
                            if(X[i] != 0):
                                ANS.append(X[i])
                            if(X[j] != 0):
                               ANS.append(X[j])
                            if(X[k] != 0):
                                ANS.append(X[k])
                            if(X[l] != 0):
                                ANS.append(X[l])
                            if(X[m] != 0):
                                ANS.append(X[m])
                            ind  =1

ANS.sort()
ANS.reverse()
for i in ANS:
    print(i, end='')
print()

Submission status: Wrong Answer

Solution code:
N, M = input().split()
N = int(N)
ori_N = 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])

fun = []
for i in my_nums:
    fun.append(nums[i])
list.sort(fun, reverse=True)
if sum(my_nums) == ori_N:
    ans = ""
    for i in fun:
        ans = ans + str(i)
print(ans)

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


def printf(str):
    l = list(str)
    l = sorted(l, reverse=True)
    print("".join(l))

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"
        printf(res)
    else:
        printf("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"
        printf(res)
    elif n % 3 == 0:
        printf("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)
        printf(res)
    exit()

if enabled[4]:
    if n % 4 == 0:
        printf("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"
        printf(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"
        printf(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"
        printf(res)
    exit()

for i in [5, 3, 2]:
    c = str(i)
    if enabled[i]:
        if n % 5 == 0:
            printf(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)
            printf(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)
            printf(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)
            printf(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)
            printf(res)
        exit()

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

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

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

Submission status: Wrong Answer

Solution code:
import math


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

MAX_N = int(1e4)
dp = [[-1 for i in range(10)] for i in range(MAX_N + 20)]
for j in range(1, 9 + 1):
    dp[0][j] = 0

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

for i in range(N + 1):
    for j in A:

        if i < mc[j - 1]:
            continue

        for k in A:
            tmp = dp[i - mc[j - 1]][k]
            if tmp == -1:
                continue
            if tmp == 0:
                dp[i][j] = max(dp[i][j], j)
            else:
                dp[i][j] = max(dp[i][j], tmp * 10 + j, (j * 10 ** (int(math.log10(tmp)) + 1) + tmp))

ans = 0
for j in range(1, 9 + 1):
    ans = max(ans, dp[N][j])
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

if q >= (p-1) * (cc[-1][0] - cc[0][0]) and q != 0:
	for j in range(b):
		if q >= ccc[j][1] - cc[0][1] and 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]
	if q == 0:
		break

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, _ = map(int, input().split())
A = list(map(int, input().split()))
table = defaultdict(int)
for i, cost in zip(range(1, 10), [2,5,5,4,5,6,3,7,6]):
    if i in A:
        table[cost] = max(table[cost], i)
candy = sorted(table)
res = defaultdict(int)
for k in range(len(candy)):
    bits = 1
    for i in candy[k + 1:]:
        bits = bits | (bits << i)
    for i in range(1, len(format(bits, 'b'))):
        if bits & (1 << i):
            if N - i >= 0 and (N - i) % candy[k] == 0:
                res[table[candy[k]]] = ((N - i) // candy[k])
                N = i
                break
    if N == candy[k]:
        res[table[candy[k]]] = 1
        N = 0
#swap
for _ in range(2):
    for candy1 in candy:
        for candy2 in candy:
            sum1 = candy1 + candy2
            for candy3 in candy:
                for candy4 in candy:
                    sum2 = candy3 + candy4
                    if sum1 == sum2:
                        x = sorted([table[candy1], table[candy2]], reverse=True)
                        y = sorted([table[candy3], table[candy4]], reverse=True)
                        if x < y:
                            a, b = x
                            c, d = y
                            t = min(res[a], res[b])
                            res[a] -= t
                            res[b] -= t
                            res[c] += t
                            res[d] += t
tmp = []
for i, d in res.items():
    tmp += [i] * d
print(''.join(map(str, sorted(tmp, reverse=True))))

Submission status: Wrong Answer

Solution code:
def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]



best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 100:
    adj = (N - 100)//best[1]
    N -= best[1] * adj



# print(best)
X = [0] + [-10**9] * N
bpre = -1
ll = 1
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    if b[0] > X[i]:
                        X[i] = b[0]
                        bpre = b
                        ll = 0
                else:
                    if X[i-b[1]]*10 + b[0] < X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])):
                        lll = 1

                    if max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]]))) > X[i]:
                        X[i] = max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
                        ll = lll
                        bpre = b
                

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

print(ans)

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

    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:
                if amari > 2*(v-mini):
                    c = amari // (v-mini)
                    c = c-1
                    for x in range(c):
                        result = result[:-1] + str(k)
                        amari = amari - (v - mini)
                if (amari - v + mini) == 0:
                    result = result[:-1] + str(k)
                    amari = amari - (v - mini)

        if amari == 0:
            break

print(result)

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 amari > max(mapped):
        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:
import numpy as np
import itertools
a,b=map(int, input().split(" "))
A=list(map(int, input().split(" ")))
A.sort()
numcount=[2,5,5,4,5,6,3,7,6]

d={}
for i in range(9):
    d[i+1]=numcount[i]

numcount2=[]
for num,i in enumerate(numcount):
    if num+1 in A:
        numcount2.append(i)

#print(numcount2)

#max=0
tmparr=[]
for i in numcount2:
    tmparr.append(a//i)
    #print(a//i)

ma=max(tmparr)
basenum=[]
for num,i in enumerate(numcount2):
    if a//i == ma:
        basenum.append(num)

#print(basenum)

ite=[]
for num,i in enumerate(A):
    if num in basenum:
        ite.append(i)

#重複組合せ
comb=list(itertools.combinations_with_replacement(ite, ma-1))
#print(comb)

results=[]
for i in comb:
    count=0
    result=[]
    for k in i:
        #count+=k
        count+=d[k]
        result.append(k)
    
    remain=a-count
    if remain not in numcount2:
        continue
    else:
        for a1,a2 in zip(A[::-1],numcount2[::-1]):
            if a2 == remain:
                result.append(a1)
                break
    results.append(result)
#print(results)

max=0
for i in results:
    i.sort()
    tmp=""
    for k in i[::-1]:
        tmp+=str(k)
    if max < int(tmp):
        max=int(tmp)

print(max)

Submission status: Wrong Answer

Solution code:
def can_make(remain, enable_digits):
    
    candidates = [(remain, [])]
    
    while candidates:
        
        current_remain, digits = candidates.pop(0)
        if current_remain == 0:
            return digits
        for (cost, neg, digit) in enable_digits:
            if cost <= current_remain:
                candidates.append( (current_remain - cost, digits + [digit]))
        #print(candidates)
    return []

def main():
    n, m = [int(x) for x in input().rstrip("\n").split(" ")]
    
    costs = (0,2,5,5,4,5,6,3,7,6)
    enable_digits = [(costs[int(x)],int(x) * -1 , int(x))  for x in input().rstrip("\n").split(" ")]
    
    enable_digits.sort()
    
    #最大桁数を決める
    min_cost, min_cost_max_digit_neg, min_cost_max_digit =enable_digits.pop(0)
    
    num_of_digits, remain = divmod(n , min_cost)
    
    if remain == 0:
        anwer = [str(min_cost_max_digit)] * num_of_digits
        print("".join(anwer))
    else:
        answer = can_make(remain, enable_digits)
        while not answer:
            remain += min_cost
            num_of_digits -= 1
            answer = can_make(remain, enable_digits)
        answer.sort()
        answer.reverse()
        greater = [str(digit) for digit in answer if digit > min_cost_max_digit]
        lesser = [str(digit) for digit in answer if digit < min_cost_max_digit]
        
        print("".join(greater) + (str(min_cost_max_digit) * num_of_digits) + "".join(lesser) )

if __name__ == '__main__':
	main()

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

    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
    
    cands = []
    i = 1
    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


main()

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":
				if s[0:c-i]<res:
					ans = res+ans
				else:
					ans = ans+res
				judge = True
				break;
print(ans)

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]
A.sort(reverse=True)
cost = [cost[Ai] for Ai in A]
tmp = list(zip(cost, A))
tmp.sort(key=lambda x:(x[0]))
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:
import math


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

MAX_N = int(1e4)
dp = [[-1 for i in range(10)] for i in range(MAX_N + 10)]
for j in range(1, 9 + 1):
    dp[0][j] = 0

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

for i in range(N + 1):
    for j in range(1, 9 + 1):
        if j not in A:
            continue

        if i < mc[j - 1]:
            continue

        for k in range(1, j + 1):
            tmp = dp[i - mc[j - 1]][k]
            if tmp == -1:
                continue
            if tmp == 0:
                dp[i][j] = max(dp[i][j], j)
            else:
                dp[i][j] = max(dp[i][j], tmp * 10 + j, (j * 10 ** (int(math.log10(tmp)) + 1) + tmp))

ans = 0
for j in range(1, 9 + 1):
    ans = max(ans, dp[N][j])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

match_table = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
search_table = [1, 7, 4, 5, 3, 2, 9, 6, 8]

def main():
    sys.setrecursionlimit(100) # recursion limit hack
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    buf = input()
    buflist = buf.split()
    A = list(sorted(list(map(int, buflist))))
    # remove unnecessary number
    if 2 in A and (3 in A or 5 in A):
        A.remove(2)
    if 3 in A and 5 in A:
        A.remove(3)
    if 6 in A and 9 in A:
        A.remove(6)
    # main part
    for i in search_table:
        if i in A:
            extra_number, penalty = generate_extra_number(A, i, N % match_table[i])
            num_to_print = ""
            for j in range(N // match_table[i] - penalty):
                num_to_print += str(i)
            if int(extra_number[0]) >= i:
                num_to_print = extra_number + num_to_print
            else:
                num_to_print = num_to_print + extra_number
            print(num_to_print)
            return

def generate_extra_number(A, main_num, remainder):
    if remainder == 0:
        return str(main_num), 1
    d = match_table[main_num]
    best = 0
    penalty = 99999
    digit = 0
    while not best:
        digit += 1
        for i in num_generator(A, digit, ""):
            extra_sum = sum([match_table[int(x)] for x in i])
            if (remainder - extra_sum) % d == 0:
                cand_best = int(i)
                cand_penalty = -(remainder - extra_sum) // d
                if cand_penalty < penalty:
                    best = int(i)
                    penalty = cand_penalty
    return str(best), penalty

def num_generator(A, digit, num):
    if digit == 0:
        yield num
    else:
        for i in reversed(A):
            yield from num_generator(A, digit-1, num + str(i))

if __name__ == '__main__':
    main()