Problem:


Score : 400 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^4

1 \leq M \leq 9

1 \leq A_i \leq 9

A_i are all different.

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

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M

Output

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

Sample Input 1

20 4
3 7 8 4

Sample Output 1

777773

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

Sample Input 2

101 9
9 8 7 6 5 4 3 2 1

Sample Output 2

71111111111111111111111111111111111111111111111111

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

Sample Input 3

15 3
5 4 6

Sample Output 3

654



Sample input:
20 4
3 7 8 4


Sample output:
777773

Submission status: Wrong Answer

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

number = [0]*9
for i in range(9):
    for j in range(m):
        if a[j] == i+1:
            number[i] += 1

can_use = []
if number[0] > 0:
    can_use.append(2)

if number[6] > 0:
    can_use.append(3)

if number[3] > 0:
    can_use.append(4)

if number[1] + number[2] + number[4] > 0:
    can_use.append(5)

if number[5] + number[8] > 0:
    can_use.append(6)

if number[7] > 0:
    can_use.append(7)

digit = list(list(0 for _ in range(6)) for _ in range(n+1))
digit_num = list(0 for _ in range(n+1))
for i in range(1,n+1):
    for j in can_use:
        if i - j >= 0:
            if digit_num[i-j] == 0 and i != j:
                continue
            elif digit_num[i-j] + 1 > digit_num[i]:
                digit_num[i] = digit_num[i-j] + 1
                for k in range(6):
                    digit[i][k] = digit[i-j][k]
                digit[i][j-2] += 1
        else:
            continue


can_use_digit = [0]*9
can_use_digit[0] = digit[n][0]
can_use_digit[6] = digit[n][1]
can_use_digit[3] = digit[n][2]
if number[1] + number[2] + number[4] > 0:
    can_use_digit[max(number[1]*1,number[2]*2,number[4]*4)] = digit[n][3]

if number[5] + number[8] > 0:
    can_use_digit[max(number[5]*5,number[8]*8)] = digit[n][4]

can_use_digit[7] = digit[n][5]
answer = 0
for i in range(8,-1,-1):
    for j in range(can_use_digit[i]):
        answer *= 10
        answer += i+1

print(answer)

Submission status: Wrong Answer

Solution code:
n , m = map(int, input().split(' '))
s = [0,2,5,5,4,5,6,3,7,6]
a = list(map(int, input().split(' ')))
r = []
for i in range(len(a)):
    r.append([s[a[i]],a[i]])
r.sort()
d = [0]
for i in range(n+10):
    d.append(-1)
for i in range(n+1):
    j = 0
    while j < len(a):
        if i-s[r[j][1]] < 0:
            j += 1
        elif d[i-s[r[j][1]]] >= 0:
            d[i] = d[i-s[r[j][1]]] +1
            break
        else:
            j+= 1
result = []
a.sort(reverse = True)
while n > 0:
    j = 0
    while j < len(a):
        if d[n-s[a[j]]] +1 == d[n]:
            result.append(a[j])
            n -= s[a[j]]
        else:
            j += 1
            
print(''.join(list(map(str, result))))

Submission status: Wrong Answer

Solution code:
A = list(map(int, input().split()))
N = list(map(int, input().split()))
MAP =[-1*(10**2)]*10
numList=[0,2,5,5,4,5,6,3,7,6]
dp=[[-1*(10**2),""] for i in [1] * (A[0]+11)]
    
dp[10][0]=0
for i in range(1,A[0]+1):
    tmp = [0]*10
    maxk=0
    maxNum=-1000
    tmpNum=0
    for k in N:
        tmpNum=dp[10+i-numList[k]][0]+1
        if(tmpNum >= maxNum):
            maxNum=dp[10+i-numList[k]][0]+1
            maxk=k
    dp[i+10][0] = maxNum
    dp[i+10][1] = str(maxk)+str(dp[10+i-numList[maxk]][1])

print(dp[(A[0]+10)][1])

"""
for i in range(dp[A[0]+10]):
    print("A")
"""

Submission status: Wrong Answer

Solution code:
# ABC 118 D

def resolve():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))
    results = [0] * 10

    def printResults():
        for i in range(9, 0, -1):
            for j in range(results[i]):
                print(i, end='')
        print("")

    costs = {}
    if 1 in a:
        costs[2] = 1
    if 7 in a:
        costs[3] = 7
    if 4 in a:
        if 2 not in costs.keys():
            costs[4] = 4
    if 2 not in costs.keys() or 3 not in costs.keys():
        if 5 in a:
            costs[5] = 5
        elif 3 in a:
            costs[5] = 3
        elif 2 in a:
            costs[5] = 2
    if 2 not in costs.keys() or 3 not in costs.keys():
        if 9 in a:
            costs[6] = 9
        elif 6 in a:
            costs[6] = 6
    if 3 not in costs.keys() or (2 not in costs.keys() and 4 not in costs.keys()):
        if 8 in a:
            costs[7] = 8

    keys = list(costs.keys())

    for i in range(N // keys[0], -1, -1):
        results = [0] * 10
        results[costs[keys[0]]] = i
        tmp1 = N - keys[0] * i
        if tmp1 == 0:
            printResults()
            return

        if len(keys) == 1:
            continue

        for j in range(tmp1 // keys[1], -1, -1):
            results[costs[keys[1]]] = j
            tmp2 = tmp1 - keys[1] * j
            if tmp2 == 0:
                printResults()
                return

            if len(keys) == 2:
                continue

            for k in range(tmp2 // keys[2], -1, -1):
                results[costs[keys[2]]] = k
                tmp3 = tmp2 - keys[2] * k
                if tmp3 == 0:
                    printResults()
                    return

                if len(keys) == 3:
                    continue

                for l in range(tmp3 // keys[3], -1, -1):
                    results[costs[keys[3]]] = l
                    tmp4 = tmp3 - keys[3] * l
                    if tmp4 == 0:
                        printResults()
                        return



if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

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

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
def search(ind, remain, ret):
    #print(ind, remain)
    if ind >= len(I):
        return False, ret
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret
    if r == 0:
        ret.append((a, p))
        return True, ret
    for q in range(p-1, -1, -1):
        r += a
        ok, newr = search(ind+1, r, ret)
        if ok:
            newr.append((a, q))
            return True, newr
    return False, ret

ok, L = search(0, N, [])
Q = []
for k, v in L:
    Q.extend([B[k]]*v)
Q.sort(reverse=True)

print(''.join([str(q) for q in Q]))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
magic = [2,5,5,4,5,6,3,7,6]
b = list(map(lambda x: [x,magic[x-1]], a))
two = max(b, key=(lambda x: (x[0] - x[1] * 10)))
use = two[0]
match = two[1]
digit = n // match
rest = n % match
ans = ( 10 ** digit - 1 ) * use // 9
now = digit - 1
while True:
  first = use
  for mi in range(m):
    if rest + match >= b[mi][1] and first < b[mi][0]:
      first = b[mi][0]
  ans += ( first - use ) * ( 10 ** now )
  now -= 1
  rest -= ( magic[first-1] - magic[use-1] )
  #print(ans,now,rest,magic[first-1],magic[use-1])
  if rest == 0:
    break
  if now == -1:
    first = 0
    for mi in range(m):
      if rest + match == b[mi][1] and first < b[mi][0]:
        first = b[mi][0]
    ans += ( first - use )
    break
print(ans)

Submission status: Wrong Answer

Solution code:
costs = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

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

# 第1：桁数 / 第2：合計値 / [要素]
dp = [[0, 0, []] for _ in range(N + 1)]
for a in A:
	cost = costs[a]
	for n in range(N):
		if n != 0 and dp[n][0] == 0:
			continue
		ni = n + cost
		if N < ni:
			break
		np = [dp[n][0] + 1, dp[n][1] + a, sorted(dp[n][2] + [a], reverse=True)]
		if dp[ni] < np:
			dp[ni] = np

print(*reversed(sorted(dp[N][2])), sep="")

Submission status: Wrong Answer

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

def kumi(m,kz=[]):
    if m==0:
        return kz
    mx=0
    re=[]
    for kk in koho[1:]:
        if m-kk<0:break
        tmp=kumi(m-kk,kz+[suji[kk]])
        if not tmp:continue
        if len(tmp)>len(re):
            re=tmp
        elif len(tmp)==len(re) and max(tmp)>mx:
            re=tmp
    return re


hon=[0,2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
a=list(map(int,input().split()))
suji={}
for ak in a:
    ah=hon[ak]
    suji.setdefault(ah,0)
    suji[ah]=max(suji[ah],ak)
koho=[x for x in suji.keys()]
koho.sort()
k,m=divmod(n,koho[0])
if m:
    for i in range(1,k):
        t=kumi(m+koho[0]*i)
        if t:break
else:
    t=[]
    i=0
ans=[suji[koho[0]]]*(k-i)+t
ans.sort(reverse=True)
print(*ans,sep="")

Submission status: Wrong Answer

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

def kumi(m,kz=[]):
    if m==0:
        return kz
    mx=0
    re=[]
    for kk in koho[1:]:
        if m-kk<0:break
        tmp=kumi(m-kk,kz+[suji[kk]])
        if not tmp:continue
        if len(tmp)>len(re):
            re=tmp
        elif len(tmp)==len(re) and max(tmp)>mx:
            re=tmp
    return re


hon=[0,2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
a=list(map(int,input().split()))
suji={}
for ak in a:
    ah=hon[ak]
    suji.setdefault(ah,0)
    suji[ah]=max(suji[ah],ak)
koho=[x for x in suji.keys()]
koho.sort()
k,m=divmod(n,koho[0])
for i in range(k):
    t=kumi(m+koho[0]*i)
    if t:break
ans=[suji[koho[0]]]*(k-i)+t
ans.sort(reverse=True)
print(*ans,sep="")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
a = list(map(int, input().split()))
cost = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [None] * (n + 1)
def dfs(at):
    if dp[at] is not None:
        return dp[at]
    r = max([0] + [dfs(at - cost[v]) * 10 + v for v in a if at - cost[v] >= 0])
    dp[at] = r
    return r


print(dfs(n))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
cand=[[''] for _ in range(6)]
for val in arr:
  cand[dic[val]-2].append(str(val))
pos=6
for i in range(5,-1,-1):
  cand[i]=sorted(cand[i],reverse=True)
  if len(cand[i])>1:
    pos=i
ans=[]
for c1 in range(n//(pos+2),max(-1,n//(pos+2)-11),-1):
  tmp=[[cand[pos][0],c1]]
  if pos==5 and (pos+2)*c1==n:
    t=''
    tmp=sorted(tmp,reverse=True,key=lambda x:x[0])
    for char,val in tmp:
      t+=char*val
    ans.append(t)
  for c2 in range(11):
    if pos>=5:
      continue
    tmp2=tmp+[[cand[pos+1][0],c2]]
    if pos==4 and (pos+2)*c1+(pos+2+1)*c2==n:
      t=''
      tmp2=sorted(tmp2,reverse=True,key=lambda x:x[0])
      for char,val in tmp2:
        t+=char*val
      ans.append(t)
    for c3 in range(11):
      if pos>=4:
        continue
      tmp3=tmp2+[[cand[pos+2][0],c3]]
      if pos==3 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3==n:
        t=''
        tmp3=sorted(tmp3,reverse=True,key=lambda x:x[0])
        for char,val in tmp3:
          t+=char*val
        ans.append(t)
      for c4 in range(11):
        if pos>=3:
          continue
        tmp4=tmp3+[[cand[pos+3][0],c4]]
        if pos==2 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4==n:
          t=''
          tmp4=sorted(tmp4,reverse=True,key=lambda x:x[0])
          for char,val in tmp4:
            t+=char*val
          ans.append(t)
        for c5 in range(11):
          if pos>=2:
            continue
          tmp5=tmp4+[[cand[pos+4][0],c5]]
          if pos==1 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4+(pos+2+4)*c5==n:
            t=''
            tmp5=sorted(tmp5,reverse=True,key=lambda x:x[0])
            for char,val in tmp5:
              t+=char*val
            ans.append(t)
          for c6 in range(11):
            if pos>=1:
              continue
            tmp6=tmp5+[[cand[pos+5][0],c6]]
            if pos==0 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4+(pos+2+4)*c5+(pos+2+5)*c6==n:
              t=''
              tmp6=sorted(tmp6,reverse=True,key=lambda x:x[0])
              for char,val in tmp6:
                t+=char*val
              ans.append(t)
              
for c1 in range(n//(pos+2+1),max(-1,n//(pos+2+1)-11),-1):
  if pos>=5:
    continue
  tmp=[[cand[pos+1][0],c1]]
  if pos==4 and (pos+2+1)*c1==n:
    t=''
    tmp=sorted(tmp,reverse=True,key=lambda x:x[0])
    for char,val in tmp:
      t+=char*val
    ans.append(t)
  for c2 in range(11):
    if pos>=4:
      continue
    tmp2=tmp+[[cand[pos+2][0],c2]]
    if pos==3 and (pos+2+1)*c1+(pos+2+2)*c2==n:
      t=''
      tmp2=sorted(tmp2,reverse=True,key=lambda x:x[0])
      for char,val in tmp2:
        t+=char*val
      ans.append(t)
    for c3 in range(11):
      if pos>=3:
        continue
      tmp3=tmp2+[[cand[pos+3][0],c3]]
      if pos==2 and (pos+2+1)*c1+(pos+2+2)*c2+(pos+2+3)*c3==n:
        t=''
        tmp3=sorted(tmp3,reverse=True,key=lambda x:x[0])
        for char,val in tmp3:
          t+=char*val
        ans.append(t)
      for c4 in range(11):
        if pos>=2:
          continue
        tmp4=tmp3+[[cand[pos+4][0],c4]]
        if pos==1 and (pos+2+1)*c1+(pos+2+2)*c2+(pos+2+3)*c3+(pos+2+4)*c4==n:
          t=''
          tmp4=sorted(tmp4,reverse=True,key=lambda x:x[0])
          for char,val in tmp4:
            t+=char*val
          ans.append(t)
        for c5 in range(11):
          if pos>=1:
            continue
          tmp5=tmp4+[[cand[pos+5][0],c5]]
          if pos==0 and (pos+2+1)*c1+(pos+2+2)*c2+(pos+2+3)*c3+(pos+2+4)*c4+(pos+2+5)*c5==n:
            t=''
            tmp5=sorted(tmp5,reverse=True,key=lambda x:x[0])
            for char,val in tmp5:
              t+=char*val
            ans.append(t)
              
ans=sorted(ans,reverse=True,key=lambda x:len(x))
print(ans[0])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
cand=[[''] for _ in range(6)]
for val in arr:
  cand[dic[val]-2].append(str(val))
pos=6
for i in range(5,-1,-1):
  cand[i]=sorted(cand[i],reverse=True)
  if len(cand[i])>1:
    pos=i
ans=[]
for c1 in range(n//(pos+2),max(-1,n//(pos+2)-15),-1):
  tmp=[[cand[pos][0],c1]]
  if pos==5 and (pos+2)*c1==n:
    t=''
    tmp=sorted(tmp,reverse=True,key=lambda x:x[0])
    for char,val in tmp:
      t+=char*val
    ans.append(t)
  for c2 in range(13):
    if pos>=5:
      continue
    tmp2=tmp+[[cand[pos+1][0],c2]]
    if pos==4 and (pos+2)*c1+(pos+2+1)*c2==n:
      t=''
      tmp2=sorted(tmp2,reverse=True,key=lambda x:x[0])
      for char,val in tmp2:
        t+=char*val
      ans.append(t)
    for c3 in range(13):
      if pos>=4:
        continue
      tmp3=tmp2+[[cand[pos+2][0],c3]]
      if pos==3 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3==n:
        t=''
        tmp3=sorted(tmp3,reverse=True,key=lambda x:x[0])
        for char,val in tmp3:
          t+=char*val
        ans.append(t)
      for c4 in range(13):
        if pos>=3:
          continue
        tmp4=tmp3+[[cand[pos+3][0],c4]]
        if pos==2 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4==n:
          t=''
          tmp4=sorted(tmp4,reverse=True,key=lambda x:x[0])
          for char,val in tmp4:
            t+=char*val
          ans.append(t)
        for c5 in range(13):
          if pos>=2:
            continue
          tmp5=tmp4+[[cand[pos+4][0],c5]]
          if pos==1 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4+(pos+2+4)*c5==n:
            t=''
            tmp5=sorted(tmp5,reverse=True,key=lambda x:x[0])
            for char,val in tmp5:
              t+=char*val
            ans.append(t)
          for c6 in range(13):
            if pos>=1:
              continue
            tmp6=tmp5+[[cand[pos+5][0],c6]]
            if pos==0 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4+(pos+2+4)*c5+(pos+2+5)*c6==n:
              t=''
              tmp6=sorted(tmp6,reverse=True,key=lambda x:x[0])
              for char,val in tmp6:
                t+=char*val
              ans.append(t)
ans=sorted(ans,reverse=True,key=lambda x:len(x))
print(ans[0])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
cand=[[''] for _ in range(6)]
for val in arr:
  cand[dic[val]-2].append(str(val))
pos=6
for i in range(5,-1,-1):
  cand[i]=sorted(cand[i],reverse=True)
  if len(cand[i])>1:
    pos=i
ans=[]
for c1 in range(n//(pos+2),max(-1,n//(pos+2)-15),-1):
  tmp=[[cand[pos][0],c1]]
  if pos==5 and (pos+2)*c1==n:
    t=''
    tmp=sorted(tmp,reverse=True,key=lambda x:x[0])
    for char,val in tmp:
      t+=char*val
    ans.append(t)
  for c2 in range(11):
    if pos>=5:
      continue
    tmp2=tmp+[[cand[pos+1][0],c2]]
    if pos==4 and (pos+2)*c1+(pos+2+1)*c2==n:
      t=''
      tmp2=sorted(tmp2,reverse=True,key=lambda x:x[0])
      for char,val in tmp2:
        t+=char*val
      ans.append(t)
    for c3 in range(11):
      if pos>=4:
        continue
      tmp3=tmp2+[[cand[pos+2][0],c3]]
      if pos==3 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3==n:
        t=''
        tmp3=sorted(tmp3,reverse=True,key=lambda x:x[0])
        for char,val in tmp3:
          t+=char*val
        ans.append(t)
      for c4 in range(11):
        if pos>=3:
          continue
        tmp4=tmp3+[[cand[pos+3][0],c4]]
        if pos==2 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4==n:
          t=''
          tmp4=sorted(tmp4,reverse=True,key=lambda x:x[0])
          for char,val in tmp4:
            t+=char*val
          ans.append(t)
        for c5 in range(11):
          if pos>=2:
            continue
          tmp5=tmp4+[[cand[pos+4][0],c5]]
          if pos==1 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4+(pos+2+4)*c5==n:
            t=''
            tmp5=sorted(tmp5,reverse=True,key=lambda x:x[0])
            for char,val in tmp5:
              t+=char*val
            ans.append(t)
          for c6 in range(11):
            if pos>=1:
              continue
            tmp6=tmp5+[[cand[pos+5][0],c6]]
            if pos==0 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4+(pos+2+4)*c5+(pos+2+5)*c6==n:
              t=''
              tmp6=sorted(tmp6,reverse=True,key=lambda x:x[0])
              for char,val in tmp6:
                t+=char*val
              ans.append(t)
ans=sorted(ans,reverse=True,key=lambda x:len(x))
print(ans[0])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
dic={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
cand=[[''] for _ in range(6)]
for val in arr:
  cand[dic[val]-2].append(str(val))
pos=6
for i in range(5,-1,-1):
  cand[i]=sorted(cand[i],reverse=True)
  if len(cand[i])>1:
    pos=i
ans=[]
for c1 in range(n//(pos+2),max(-1,n//(pos+2)-11),-1):
  tmp=[[cand[pos][0],c1]]
  if pos==5 and (pos+2)*c1==n:
    t=''
    tmp=sorted(tmp,reverse=True,key=lambda x:x[0])
    for char,val in tmp:
      t+=char*val
    ans.append(t)
  for c2 in range(11):
    if pos>=5:
      continue
    tmp2=tmp+[[cand[pos+1][0],c2]]
    if pos==4 and (pos+2)*c1+(pos+2+1)*c2==n:
      t=''
      tmp2=sorted(tmp2,reverse=True,key=lambda x:x[0])
      for char,val in tmp2:
        t+=char*val
      ans.append(t)
    for c3 in range(11):
      if pos>=4:
        continue
      tmp3=tmp2+[[cand[pos+2][0],c3]]
      if pos==3 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3==n:
        t=''
        tmp3=sorted(tmp3,reverse=True,key=lambda x:x[0])
        for char,val in tmp3:
          t+=char*val
        ans.append(t)
      for c4 in range(11):
        if pos>=3:
          continue
        tmp4=tmp3+[[cand[pos+3][0],c4]]
        if pos==2 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4==n:
          t=''
          tmp4=sorted(tmp4,reverse=True,key=lambda x:x[0])
          for char,val in tmp4:
            t+=char*val
          ans.append(t)
        for c5 in range(11):
          if pos>=2:
            continue
          tmp5=tmp4+[[cand[pos+4][0],c5]]
          if pos==1 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4+(pos+2+4)*c5==n:
            t=''
            tmp5=sorted(tmp5,reverse=True,key=lambda x:x[0])
            for char,val in tmp5:
              t+=char*val
            ans.append(t)
          for c6 in range(11):
            if pos>=1:
              continue
            tmp6=tmp5+[[cand[pos+5][0],c6]]
            if pos==0 and (pos+2)*c1+(pos+2+1)*c2+(pos+2+2)*c3+(pos+2+3)*c4+(pos+2+4)*c5+(pos+2+5)*c6==n:
              t=''
              tmp6=sorted(tmp6,reverse=True,key=lambda x:x[0])
              for char,val in tmp6:
                t+=char*val
              ans.append(t)
ans=sorted(ans,reverse=True,key=lambda x:len(x))
print(ans[0])

Submission status: Wrong Answer

Solution code:
def dv_p(t, cos, d_l, s):
    if t == cos:
        return int(s)
    elif t < cos:
        return 0
    else:
        temp = []
        for i_i in range(len(d_l)):
            temp.append(dv_p(t, cos + d_l[i_i][1], d_l, s + str(d[i_i][0])))
        return max(temp)


d = [[1, 2, False], [2, 5, False], [3, 5, False]
    , [4, 4, False], [5, 5, False], [6, 6, False]
    , [7, 3, False], [8, 7, False], [9, 6, False]]
a, b = map(int, input().split())
c = list(map(int, input().split()))
for i in range(b):
    for j in range(len(d)):
        if c[i] == d[j][0]:
            d[j][2] = not d[j][2]
d = sorted(d, key=lambda x: x[0], reverse=True)
d = sorted(d, key=lambda x: x[1])
d = sorted(d, key=lambda x: x[2], reverse=True)
ans = ""
t_cost = a
while True:
    if t_cost >= d[0][1]:
        ans += str(d[0][0])
        t_cost -= d[0][1]
    else:
        if t_cost == 0:
            ans = list(ans)
            ans = sorted(ans, reverse=True)
            print("".join(ans))
            exit()
        else:
            x = 5
            ans_int = 10 ** 9
            while True:
                t_list = []
                tt_cost = t_cost
                for j in range(x):
                    if d[j][2]:
                        t_list.append(d[j])
                        tt_cost += d[0][1]
                    else:
                        break
                ans_int = dv_p(tt_cost, 0, t_list, "")
                if ans_int != 0:
                    break
                x += 1
            ttt = list(str(ans_int) + ans[len(str(ans_int)):])
            ttt = sorted(ttt, reverse=True)
            print("".join(ttt))
            exit()

Submission status: Wrong Answer

Solution code:
def dv_p(t, cos, d_l, s):
    if t == cos:
        return int(s)
    elif t < cos:
        return 0
    else:
        temp = []
        for i_i in range(len(d_l)):
            temp.append(dv_p(t, cos + d_l[i_i][1], d_l, s + str(d[i_i][0])))
        return max(temp)


d = [[1, 2, False], [2, 5, False], [3, 5, False]
    , [4, 4, False], [5, 5, False], [6, 6, False]
    , [7, 3, False], [8, 7, False], [9, 6, False]]
a, b = map(int, input().split())
c = list(map(int, input().split()))
for i in range(b):
    for j in range(len(d)):
        if c[i] == d[j][0]:
            d[j][2] = not d[j][2]
d = sorted(d, key=lambda x: x[0], reverse=True)
d = sorted(d, key=lambda x: x[1])
d = sorted(d, key=lambda x: x[2], reverse=True)
ans = ""
t_cost = a
while True:
    if t_cost >= d[0][1]:
        ans += str(d[0][0])
        t_cost -= d[0][1]
    else:
        if t_cost == 0:
            ans = list(ans)
            ans = sorted(ans, reverse=True)
            print("".join(ans))
            exit()
        else:
            x = 6
            ans_int = 10 ** 9
            while True:
                t_list = []
                tt_cost = t_cost
                for j in range(x):
                    if d[j][2]:
                        t_list.append(d[j])
                        tt_cost += d[0][1]
                    else:
                        break
                ans_int = dv_p(tt_cost, 0, t_list, "")
                if ans_int != 0:
                    break
                x += 1
            ttt = list(str(ans_int) + ans[len(str(ans_int)):])
            ttt = sorted(ttt, reverse=True)
            print("".join(ttt))
            exit()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def solve():
  N, M = LI()
  num_list = LI()
  mapping = [-1,2,5,5,4,5,6,3,7,6]

  a_list = [mapping[num] for num in num_list]
  
  rmap = {}
  for a, num in zip(a_list, num_list):
    if a not in rmap:
      rmap[a] = num
    else:
      if rmap[a] < num:
        rmap[a] = num

  # もっとも効率のいい数字を探す
  eff_num = -1
  eff_a = 10**9
  for a, num in zip(a_list, num_list):
    if a < eff_a or (a == eff_a and num >= eff_num):
      eff_a = a
      eff_num = num

  def search(r, cur, res):
    for a in list(set(a_list)):
      next_cur = [c for c in cur]
      next_cur.append(a)
      if a == r:
        res.append(next_cur)
        return res
      elif a > r:
        return res
      else:
        search(r-a, next_cur, res)
    return res

  k = N // eff_a # 効率のいい数字が作れる数の最大値
  rest =  N - k*eff_a
  if rest == 0:
    print(''.join([str(eff_num)]*k))
    return

  # 答えが出る+10ぐらいまで探索
  first_ans_i = None
  ans_str_cand = []
  for i in range(1, k):
    rest_a = rest + i* eff_a # あまりの数字
    candidates = search(rest_a, [], [])
    if len(candidates) == 0:
      continue
    ans_cand = None
    ans_cand_len = -1
    ans_cand_mx = -1
    for cand in candidates:
      cand_num = [rmap[c] for c in cand]
      cand_mx = max(cand_num)
      if (ans_cand_len < len(cand)) or (ans_cand_len == len(cand) and ans_cand_mx <= cand_mx):
          ans_cand = cand
          ans_cand_len = len(cand)
          ans_cand_mx = cand_mx
    eff = [eff_num]*(k-i)
    num_cand = [rmap[c] for c in ans_cand]
    num_cand.extend(eff)
    num_cand = sorted(num_cand, reverse=True)
    ans_str_cand.append(''.join([str(n) for n in num_cand]))
    if first_ans_i is None:
      first_ans_i = i
    if i >= first_ans_i + 11:
      break
  print(max(ans_str_cand))
solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
import copy

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
cnt = [[0] * 10 for i in range(N+1)]
for i in range(2, N+1):
    for a in A:
        if i >= x[a] and dp[i-x[a]] + 1 > dp[i]:
            dp[i] = dp[i-x[a]] + 1
            cnt[i] = copy.copy(cnt[i-x[a]])
            cnt[i][a] += 1
ans = ''
for i in range(9):
    ans += str(9-i) * cnt[N][9-i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]
import copy

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse = True)
x = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0 for i in range(N+1)]
cnt = [[0] * 10 for i in range(N+1)]
for i in range(2, N+1):
    for a in A:
        if i >= x[a] and dp[i-x[a]] + 1 > dp[i]:
            dp[i] = dp[i-x[a]] + 1
            cnt[i] = copy.copy(cnt[i-x[a]])
            cnt[i][a] += 1
print(cnt)
ans = ''
for i in range(9):
    ans += str(9-i) * cnt[N][9-i]
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
li = list(map(int,input().split()))
li2 = []
for i in li:
    if i == 1:
        li2.append(2)
    elif i == 7:
        li2.append(3)
    elif i == 4:
        li2.append(4)
    elif i == 2 or i == 3 or i == 5:
        li2.append(5)
    elif i == 6 or i == 9:
        li2.append(6)
    elif i == 8:
        li2.append(7)

dp = [0] * (n+1)

for i in range(n):
    for j in li2:
        if i + 1 >= j:
            dp[i+1] = max(dp[i+1],dp[i-j+1]+1)

s = ''

for i in range(dp[n]-1):
    a = 0
    k = 0
    for j in range(len(li2)):
        if dp[n] - dp[n-li2[j]] == 1:
            a = max(a,li[j])
            if a == li[j]:
                k = j
    s += str(li[k])
    n -= li2[k]

a = 0
k = 0
for i in range(len(li2)):
    if n == li2[i]:
        a = max(a,li[i])
s += str(a)

print(s)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
li = list(map(int,input().split()))
li2 = []
for i in li:
    if i == 1:
        li2.append(2)
    elif i == 7:
        li2.append(3)
    elif i == 4:
        li2.append(4)
    elif i == 2 or i == 3 or i == 5:
        li2.append(5)
    elif i == 6 or i == 9:
        li2.append(6)
    elif i == 8:
        li2.append(7)

dp = [0] * (n+1)

for i in range(n):
    for j in li2:
        if i + 1 >= j:
            dp[i+1] = max(dp[i+1],dp[i-j+1]+1)


s = ''

for i in range(dp[n]-1):
    a = 0
    k = 0
    for j in range(len(li2)):
        if dp[n] - dp[n-li2[j]] == 1:
            print(dp[n],dp[n-li2[j]],li2[j])
            a = max(a,li[j])
            if a == li[j]:
                k = j
    s += str(li[k])
    n -= li2[k]

a = 0
k = 0
for i in range(len(li2)):
    if n == li2[i]:
        print(i)
        a = max(a,li[i])
        print(a)
s += str(a)

print(s)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(20000)
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
A = list(map(int, input().split()))

recipe = [2, 5, 5, 4, 5, 6, 3, 7, 6]
strategy = []

for i in A:
	strategy.append((recipe[i - 1], -i))
	
strategy.sort()
l = []

def dfs(cost):
	if cost > N:
		return False
	elif cost == N:
		return True
		
	for j in range(M):
		res = dfs(cost + strategy[j][0])
		if res:
			l.append(-strategy[j][1])
			return True

	return False
	
dfs(0)
l.sort(reverse=True)
c = map(str, l)
print(''.join(c))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
if 2 in A and 3 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 2 in A and 5 in A:
  A.remove(2)
if 6 in A and 9 in A:
  A.remove(6)
m=len(A)
D={}
D[1]=2
D[2]=5
D[3]=5
D[4]=4
D[5]=5
D[6]=6
D[7]=3
D[8]=7
D[9]=6
DP1,DP2=[-float("inf")]*(n+1),[[]]*(n+1)
DP1[0]=0
for i in range(n):
  for j in range(m):
    if D[A[j]]<=i+1 and DP1[i+1-D[A[j]]]!=-float("inf") and DP1[i+1-D[A[j]]]+1>=DP1[i+1]:
      DP1[i+1]=DP1[i+1-D[A[j]]]+1
      x,y=0,0
      X,Y=DP2[i+1],DP2[i+1-D[A[j]]]+[A[j]]
      Y.sort(reverse=True)
      for xx in X:
        x=x*10+xx
      for yy in Y:
        y=y*10+yy
      if y>x:
        DP2[i+1]=DP2[i+1-D[A[j]]]+[A[j]]
print(y)