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: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

n,mmm = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


bar = list(set([table[i] for i in a]))
bar.sort()
minbar=min(bar)

maxnum = ['0']*10
for i in bar:
    mbmax = max([j for j in a if table[j] == i])
    maxnum[i]=str(mbmax)
#print(maxnum,bar)
ans = ['0']*(100)
for i in range(8):
    if i in bar:
        ans[i]=maxnum[i]
#print(ans)
for i in range(90):
    if ans[i] == '0':
        continue
    for j in bar:
        if maxnum[j] > ans[i][0]:
            tmp = maxnum[j]+ans[i]
        else:
            tmp = ans[i]+maxnum[j]
            ans[i+j] = str(max(int(ans[i+j]),int(tmp)))
#print(ans)
if n < 90:
    print(ans[n])
else:
    mn = maxnum[minbar]
    ans2=0
    for i in range(90):
        if n>=i and (n-i)%minbar == 0:
            q=(n-i)//minbar
            if ans[i]=='0' : continue
            X = ''.join([j for j in ans[i] if j > mn])
            Y = ''.join([j for j in ans[i] if j <= mn])
            tmp = int(X+str(mn)*q+Y)
#            print(tmp,X,Y,ans[i],i)
            ans2 = str(max(int(ans2),tmp))
    print(ans2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[0]+[-(2**30) for i in range(n)]
a,b=sorted(list(map(int,input().split())),reverse=True),[0,2,5,5,4,5,6,3,7,6]
for i in range(n):
	for j in range(m):
		if(i+b[a[j]]>n):
			continue
		dp[i+b[a[j]]] = max(dp[i+b[a[j]]],dp[i]+1)
ans = ""
while n:
	for j in range(m):
		if n-b[a[j]]<0:
			continue
		if dp[n-b[a[j]]] == dp[n]-1:
			ans += str(a[j])
			n -= b[a[j]]
			break
print(ans)

Submission status: Accepted

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(len(l1)-1,0,-1):
        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: Accepted

Solution code:
num = [0,2,5,5,4,5,6,3,7,6]
n, m = map(int, input().split())
dp = [-1] * (n+10)
a = list(map(int, input().split()))
a.sort()
a.reverse()
b = list()
for x in a:
    b.append(num[x])
dp[0] = 0
for i in range(n):
    for x in b:
        dp[i+x] = max(dp[i+x], dp[i] + 1)
ans = str()
while n > 0:
    for i in range(m):
        if n-b[i] >= 0 and dp[n] == dp[n-b[i]] + 1:
            n -= b[i]
            ans += str(a[i])
            break
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
enabled = [(i in a) for i in range(10)]

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"
    else:
        res = "1" * (n // 2)
elif 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"
    elif n % 3 == 0:
        res = "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)
elif enabled[4]:
    if n % 4 == 0:
        res = "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"
    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"
    else:
        if 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[8]:
            res = "8" + "4" * ((n - 7) // 4)
        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"
else:
    for i in [5, 3, 2]:
        c = str(i)
        if enabled[i]:
            if n % 5 == 0:
                res = 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)
            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)
            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)
            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]:
        if n % 6 == 0:
            res = "9" * (n // 6)
        elif n % 6 == 1:
            res = "9" * ((n - 7) // 6) + "8"
        elif n % 6 == 2:
            res = "9" * ((n - 14) // 6) + "88"
        elif n % 6 == 3:
            res = "9" * ((n - 21) // 6) + "888"
        elif n % 6 == 4:
            res = "9" * ((n - 28) // 6) + "8888"
        else:
            res = "9" * ((n - 35) // 6) + "88888"
    elif enabled[6]:
        if n % 6 == 0:
            res = "6" * (n // 6)
        elif n % 6 == 1:
            res = "8" + "6" * ((n - 7) // 6)
        elif n % 6 == 2:
            res = "88" + "6" * ((n - 14) // 6)
        elif n % 6 == 3:
            res = "888" + "6" * ((n - 21) // 6)
        elif n % 6 == 4:
            res = "8888" + "6" * ((n - 28) // 6)
        else:
            res = "88888" + "6" * ((n - 35) // 6)
    else:
        res = "8" * (n // 7)
print(res)

Submission status: Accepted

Solution code:
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 = max((N - 200),0)//best[1]
N -= best[1] * adj

X = [0] + [-10**9] * N
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:
                X[i] = max(X[i], X[i-b[1]]*10 + b[0])

ans = str(X[N])
ans = ans[:10] + str(best[0]) * adj + ans[10:]

print(ans)

Submission status: Accepted

Solution code:
tmp = [0] * 10
def rec(i):
  for j in range(len(w)):
    if(i >= w[j] and dp[0][ i - w[j] ] != -1):
      if(dp[0][ i - w[j] ] + 1 > dp[0][i]):
        dp[0][i] = dp[0][ i - w[j] ] + 1
        for k in range(10):
          dp[1][i][k] = dp[1][ i - w[j] ][k]
        dp[1][i][v[j]] += 1

      elif(dp[0][ i - w[j] ] + 1 == dp[0][i]):
        for k in range(10):
          tmp[k] = dp[1][ i - w[j] ][k]
        tmp[v[j]] += 1
        for k in range(9,0,-1):
          if(tmp[k] > dp[1][i][k]):
            dp[0][i] = dp[0][ i - w[j] ] + 1
            for k in range(10):
              dp[1][i][k] = dp[1][ i - w[j] ][k]
            dp[1][i][v[j]] += 1
            break
          elif(tmp[k] < dp[1][i][k]):
            break

n, k = [int(i) for i in input().split(" ")]
a = [int(i) for i in input().split(" ")]
ww = [2,5,5,4,5,6,3,7,6]
z =  [1,7,4,5,3,2,9,6,8]

dp = [0]*2
dp[0] = [-1] * (n+1)
dp[0][0] = 0
dp[1] = [ [0 for i in range(10)] for j in range(n+1)]
w = []
v = []
for i in z:
  if(i in a):
    if(not ww[i-1] in w):
      v.append(i)
      w.append(ww[i-1])

for i in range(min(w), n+1):
  rec(i)

for i in range(9,0,-1):
  print("{}".format(i)*dp[1][n][i], end='')

Submission status: Accepted

Solution code:
nums = list(map(int, input().split()))
N, M = nums[0], nums[1]
A = list(map(int, input().split()))

nums = [2,5,5,4,5,6,3,7,6];

from copy import deepcopy as copy
dp = [[0 for _ in range(10)] for _ in range(N+1)]

def compare_dp(a1, a2):
    for i in range(10):
        if a1[i] > a2[i]:
            return True
        elif a1[i] < a2[i]:
            return False

    return True

def allzero(a):
    flag = True
    for e in a:
        flag = flag and (e==0)
    return flag

for i in range(N+1):
    for j in range(M):
        if i >= nums[A[j]-1]:
            if (not allzero(dp[i-nums[A[j]-1]])) or i-nums[A[j]-1]==0:
                val = copy(dp[i-nums[A[j]-1]])
                val[0] += 1
                val[10-A[j]] += 1
                if compare_dp(val, dp[i]):
                    dp[i] = copy(val)

for i in range(9):
    for j in range(dp[N][i+1]):
        print(9-i, end="")
print("\n", end="")

Submission status: Accepted

Solution code:
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 = max((N - 200),0)//best[1]
N -= best[1] * adj

X = [0] + [-10**9] * N
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:
                    X[i] = max(X[i], b[0])
                else:
                    X[i] = max(X[i], X[i-b[1]]*10 + b[0])

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

print(ans)

Submission status: Accepted

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

setnum = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6} 
rset = {}
for i in a:
    if i in rset:
        if rset[setnum[i]] > i:
            rset[i] = setnum[i]
    else:
        rset[i] = setnum[i]

rset = sorted(rset.items(), reverse=True)
dp = [0] * (n + 1)
for i in rset:
    if n < i[1]:
        continue
    dp[i[1]] = max(dp[i[1]] , i[0])
    for j in range(i[1], n + 1 - i[1]):
        if dp[j] != 0:
            dp[j + i[1]] = max(dp[j + i[1]], dp[j] * 10 + i[0])
print(dp[-1])

Submission status: Accepted

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

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

min_w = 10
for i in a:
    min_w = min(min_w,w[i-1])

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


for i in range(0,n):
    if 1 <= i < min_w:
            dp[i] = -1
    for j in a:
        if i + 1 - w[j-1] >= 0 and dp[i + 1 - w[j-1]] != -1:
            dp[i+1] = max(dp[i+1],dp[i+1-w[j-1]]*10+j)
print(dp[n])

Submission status: Accepted

Solution code:
#coding:utf-8
N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]

def check2(A,B):
    p = 0
    t = 0
    # print(A)
    # print(B)
    if len(A) > len(B):
        return A
    elif len(A) < len(B):
        return B
    for a,b in zip(A,B):
        if  a- b > 0:
            return A
        elif a-b < 0:
            return B
    return A
    # for a in A:
    #     p = p*10+a
    # for b in B:
    #     t = t*10+b
    # if t > p:
    #     return B

    # else:
    #     return A

while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check2(bagS[b+c[a]],sorted((bagS[b]+[a]),reverse=True))

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
print("".join(list(map(str,bagS[N]))))

Submission status: Accepted

Solution code:
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 > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
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:
                    X[i] = max(X[i], b[0])
                else:
                    X[i] = max(X[i], X[i-b[1]]*10 + b[0])

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

print(ans)

Submission status: Accepted

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[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[8]:
            res = "8" + "4" * ((n - 7) // 4)
        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: Accepted

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 > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
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:
                    X[i] = max(X[i], b[0])
                else:
                    X[i] = max(X[i], X[i-b[1]]*10 + b[0])

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

print(ans)

Submission status: Accepted

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 > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
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:
                    X[i] = max(X[i], b[0])
                else:
                    X[i] = max(X[i], X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))

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

print(ans)

Submission status: Accepted

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

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

dp = [[0 for i in xrange(10)] for j in xrange(n + 1)]

for i in xrange(2, n + 1):
    nl = [0 for k in xrange(10)]
    for dig in a:
        if i - sticks[dig] < 0: continue
        if i - sticks[dig] > 0 and dp[i - sticks[dig]][0] == 0: continue
        cur = [dp[i - sticks[dig]][j] for j in xrange(10)]
        
        cur[10 - dig] += 1
        cur[0] += 1
        
        nl = max(nl, cur)
    
    dp[i] = nl
    #print i, dp[i]

#print dp[n]

out = []
for i in xrange(1, 10):
    if dp[n][i] == 0: continue
    for j in xrange(dp[n][i]): out.append(str(10 - i))

print ''.join(out)

Submission status: Accepted

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[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[8]:
            res = "8" + "4" * ((n - 7) // 4)
        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))