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 = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

dp = ["0"] * (n+1)
ma = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

for i in range(n):
    if dp[i] == "":
        continue
    elif dp[i] == "0":
        for j in a:
            k = i + ma[j]
            if k <= n:
                dp[k] = max(dp[k], str(j), key=int)
    else:
        for j in a:
            k = i + ma[j]
            if k <= n:
                dp[k] = max(dp[k], dp[i] + str(j), key=int)
                dp[k] = max(dp[k], str(j)+dp[i], key=int)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

DEPMAX = 4

def foo(n,dep):
    if dep>DEPMAX or n<0:
        ret = "-1"
    elif n==0:
        ret = ""
    elif n%mn==0:
        ret = str(mni)*(n//mn)
    else:
        mxs = "-1"
        for x in a:
            v = foo(n-cs[x],dep+1)
            if v=="-1":
                continue
            vv = v+str(x)
            if int(vv)>int(mxs):
                mxs = vv
            vv = str(x)+v
            if int(vv)>int(mxs):
                mxs = vv
        ret = mxs
    #ddprint(f"foo n {n} k {k} ret {ret}")
    return ret

n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
mn = min([cs[x] for x in a])
for i in range(m-1,-1,-1):
    if cs[a[i]]==mn:
        mni = a[i]
        break
#k = (n+mn-1)//mn
#k = (n)//mn
#ddprint(f"mn {mn} mni {mni}")
#ddprint(a)
print(foo(n,0))

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

DEPMAX = 4

def foo(n,dep):
    k = n//mn
    if dep>DEPMAX or k<=0:
        ret = ""
    elif n%mn==0:
        ret = str(mni)*k
    else:
        mxs = "0"
        if n<=7:
          for i in range(m-1,-1,-1):
            if cs[a[i]]==n:
                mxs = str(a[i])
                break
        for x in a:
            v = foo(n-cs[x],dep+1)
            if v=="":
                continue
            if x<mni:
                vv = v+str(x)
            else:
                vv = str(x)+v
            if int(vv)>int(mxs):
                mxs = vv
        ret = mxs if mxs != "0" else ""
    #ddprint(f"foo n {n} k {k} ret {ret}")
    return ret

n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
mn = min([cs[x] for x in a])
for i in range(m-1,-1,-1):
    if cs[a[i]]==mn:
        mni = a[i]
        break
#k = (n+mn-1)//mn
#k = (n)//mn
#ddprint(f"mn {mn} mni {mni}")
#ddprint(a)
print(foo(n,0))

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

DEPMAX = 4

def foo(n,dep):
    k = n//mn
    if dep>DEPMAX or k<=0:
        ret = ""
    elif n%mn==0:
        ret = str(mni)*k
    elif k==1:
        ret = ""
        for i in range(m-1,-1,-1):
            if cs[a[i]]==n:
                ret = str(a[i])
                break
    else:
        mxs = "0"
        for x in a:
            v = foo(n-cs[x],dep+1)
            if v=="":
                continue
            if x<mni:
                vv = v+str(x)
            else:
                vv = str(x)+v
            if int(vv)>int(mxs):
                mxs = vv
        ret = mxs if mxs != "0" else ""
    #ddprint(f"foo n {n} k {k} ret {ret}")
    return ret

n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
mn = min([cs[x] for x in a])
for i in range(m-1,-1,-1):
    if cs[a[i]]==mn:
        mni = a[i]
        break
#k = (n+mn-1)//mn
#k = (n)//mn
#ddprint(f"mn {mn} mni {mni}")
#ddprint(a)
print(foo(n,0))

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

DEPMAX = 4

def foo(n,dep):
    k = n//mn
    if dep>DEPMAX or k<=0:
        ret = ""
    elif n%mn==0:
        ret = str(mni)*k
    elif k==1:
        ret = ""
        for i in range(m-1,-1,-1):
            if cs[a[i]]==n:
                ret = str(a[i])
                break
    else:
        mxs = "0"
        for x in a:
            v = foo(n-cs[x],dep+1)
            if v=="":
                continue
            if x<mni:
                vv = v+str(x)
            else:
                vv = str(x)+v
            if int(vv)>int(mxs):
                mxs = vv
        ret = mxs
    #ddprint(f"foo n {n} k {k} ret {ret}")
    return ret

n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
mn = min([cs[x] for x in a])
for i in range(m-1,-1,-1):
    if cs[a[i]]==mn:
        mni = a[i]
        break
#k = (n+mn-1)//mn
#k = (n)//mn
#ddprint(f"mn {mn} mni {mni}")
#ddprint(a)
print(foo(n,0))

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

DEPMAX = 4

def foo(n,k,dep):
    if n<mn*k or dep>DEPMAX:
        ret = ""
    elif n==mn*k:
        ret = str(mni)*k
    elif k==1:
        ret = ""
        for i in range(m-1,-1,-1):
            if cs[a[i]]==n:
                ret = str(a[i])
                break
    else:
        mxs = ""
        for x in a:
            v = foo(n-cs[x],k-1,dep+1)
            if v=="":
                continue
            if x<mni:
                vv = v+str(x)
            else:
                vv = str(x)+v
            mxs = max(mxs,vv)
        ret = mxs
    #ddprint(f"foo n {n} k {k} ret {ret}")
    return ret

n,m = inm()
a = inl()
a.sort()
cs = [0,2,5,5,4,5,6,3,7,6]
mn = min([cs[x] for x in a])
for i in range(m-1,-1,-1):
    if cs[a[i]]==mn:
        mni = a[i]
        break
#k = (n+mn-1)//mn
k = (n)//mn
#ddprint(f"mn {mn} mni {mni} k {k}")
#ddprint(a)
print(foo(n,k,0))

Submission status: Wrong Answer

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline

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

data=[]
for i,a in enumerate([2,5,5,4,5,6,3,7,6]):
    if i+1 in A:
        data.append([a,i+1])

dic={}
for a,i in reversed(data):
    dic[i]=0
dp=[copy.copy(dic) for i in range(N+1)]

def main(dic1,dic2):
    dic1=sorted([[str(i),dic1[i]] for i in dic],key=lambda x:x[0],reverse=True)
    dic2=sorted([[str(i),dic2[i]] for i in dic],key=lambda x:x[0],reverse=True)
    for a,b in zip(dic1,dic2):
        if a[1]>b[1]:
            return(0)
        if a[1]<b[1]:
            return(1)
    return(0)

def _sum(dic):
    count=0
    for i in dic:
        count+=dic[i]
    return(count)


for a,n in data:
    tempdic=copy.copy(dic)
    tempdic[n]+=1
    if i>=a:
        flag=main(dp[a],tempdic)
        if flag:
            dp[a]=tempdic
    for i in range(len(dp)):
        if i>=a and _sum(dp[i-a]):
            if _sum(dp[i])<_sum(dp[i-a])+1:

                tempdic=copy.copy(dp[i-a])
                tempdic[n]+=1
                dp[i]=tempdic
            elif _sum(dp[i])==_sum(dp[i-a])+1:
                dp[i-a][n]+=1
                flag=main(dp[i],dp[i-a])
                dp[i-a][n]-=1
                if flag:
                    tempdic=copy.copy(dp[i-a])
                    tempdic[n]+=1
                    dp[i]=tempdic
dic=dp[N]
a=""
dic=sorted([[str(i),dic[i]] for i in dic],key=lambda x:x[0],reverse=True)
for i,z in dic:
    for m in range(z):
        a+=i
print(a)

Submission status: Wrong Answer

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline

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

data=[]
for i,a in enumerate([2,5,5,4,5,6,3,7,6]):
    if i+1 in A:
        data.append([a,i+1])

Motodic={}
for a,i in reversed(data):
    Motodic[i]=0
dp=[copy.copy(Motodic) for i in range(N+1)]

def main(dic3,dic4):
    dic1=sorted([[str(i),dic3[i]] for i in dic3],key=lambda x:x[0],reverse=True)
    dic2=sorted([[str(i),dic4[i]] for i in dic4],key=lambda x:x[0],reverse=True)
    for a,b in zip(dic1,dic2):
        if a[1]>b[1]:
            return(0)
        if a[1]<b[1]:
            return(1)
    return(0)

def _sum(dic):
        count=0
        for i in dic:
            count+=dic[i]

        return(count)

for a,n in data:
    tempdic=copy.copy(Motodic)
    tempdic[n]+=1
    """flag=main(dp[a],tempdic)
    if flag:
        dp[a]=tempdic"""
    try:
        for i in range(len(dp)):
            if i-a>=0 and _sum(dp[i-a]):

                if _sum(dp[i])<_sum(dp[i-a])+1:
                    try:
                        tempdic=copy.copy(dp[i-a])
                        tempdic[n]+=1
                        dp[i]=tempdic
                    except:
                        pass
                elif _sum(dp[i])==_sum(dp[i-a])+1:
                    try:
                        dp[i-a][n]+=1
                        flag=main(dp[i],dp[i-a])
                        dp[i-a][n]-=1
                        if flag:
                            tempdic=copy.copy(dp[i-a])
                            tempdic[n]+=1
                            dp[i]=tempdic
                    except:
                        pass
    except:
        pass

dic=dp[N]
a=""
dic=sorted([[str(i),dic[i]] for i in dic],key=lambda x:x[0],reverse=True)
for i,z in dic:
    for m in range(z):
        a+=i
print(a)

Submission status: Wrong Answer

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline

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

data=[]
for i,a in enumerate([2,5,5,4,5,6,3,7,6]):
    if i+1 in A:
        data.append([a,i+1])

Motodic={}
for a,i in reversed(data):
    Motodic[i]=0
dp=[copy.copy(Motodic) for i in range(N+1)]

def main(dic3,dic4):
    dic1=sorted([[str(i),dic3[i]] for i in dic3],key=lambda x:x[0],reverse=True)
    dic2=sorted([[str(i),dic4[i]] for i in dic4],key=lambda x:x[0],reverse=True)
    for a,b in zip(dic1,dic2):
        if a[1]>b[1]:
            return(0)
        if a[1]<b[1]:
            return(1)
    return(0)

def _sum(dic):
    count=0
    for i in dic:
        count+=dic[i]
    return(count)


for a,n in data:
    tempdic=copy.copy(Motodic)
    tempdic[n]+=1
    flag=main(dp[a],tempdic)
    if flag:
        dp[a]=tempdic
    exit()
    for i in range(len(dp)):
        if i>=a and _sum(dp[i-a]):
            if _sum(dp[i])<_sum(dp[i-a])+1:

                tempdic=copy.copy(dp[i-a])
                tempdic[n]+=1
                dp[i]=tempdic
            elif _sum(dp[i])==_sum(dp[i-a])+1:
                dp[i-a][n]+=1
                flag=main(dp[i],dp[i-a])
                dp[i-a][n]-=1
                if flag:
                    tempdic=copy.copy(dp[i-a])
                    tempdic[n]+=1
                    dp[i]=tempdic
dic=dp[N]
a=""
dic=sorted([[str(i),dic[i]] for i in dic],key=lambda x:x[0],reverse=True)
for i,z in dic:
    for m in range(z):
        a+=i
print(a)

Submission status: Wrong Answer

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline

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

data=[]
for i,a in enumerate([2,5,5,4,5,6,3,7,6]):
    if i+1 in A:
        data.append([a,i+1])

dic={}
for a,i in reversed(data):
    dic[i]=0
dp=[copy.copy(dic) for i in range(N+1)]

def main(dic3,dic4):
    dic1=sorted([[str(i),dic3[i]] for i in dic],key=lambda x:x[0],reverse=True)
    dic2=sorted([[str(i),dic4[i]] for i in dic],key=lambda x:x[0],reverse=True)
    for a,b in zip(dic1,dic2):
        if a[1]>b[1]:
            return(0)
        if a[1]<b[1]:
            return(1)
    return(0)

def _sum(dic):
    count=0
    for i in dic:
        count+=dic[i]
    return(count)

exit()
for a,n in data:
    tempdic=copy.copy(dic)
    tempdic[n]+=1
    flag=main(dp[a],tempdic)
    if flag:
        dp[a]=tempdic
    for i in range(len(dp)):
        if i>=a and _sum(dp[i-a]):
            if _sum(dp[i])<_sum(dp[i-a])+1:

                tempdic=copy.copy(dp[i-a])
                tempdic[n]+=1
                dp[i]=tempdic
            elif _sum(dp[i])==_sum(dp[i-a])+1:
                dp[i-a][n]+=1
                flag=main(dp[i],dp[i-a])
                dp[i-a][n]-=1
                if flag:
                    tempdic=copy.copy(dp[i-a])
                    tempdic[n]+=1
                    dp[i]=tempdic
dic=dp[N]
a=""
dic=sorted([[str(i),dic[i]] for i in dic],key=lambda x:x[0],reverse=True)
for i,z in dic:
    for m in range(z):
        a+=i
print(a)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
lis = [2,5,5,4,5,6,3,7,6]
mat=[]
for num in a:
    mat.append([num,lis[num-1]])

def my_max(lis1,lis2):
    if len(lis1) > len(lis2):
        return lis1
    if len(lis2) > len(lis1):
        return lis2

    for i in range(len(lis)):
        if lis1[i] > lis2[i]:
            return lis1
        if lis2[i] > lis1[i]:
            return lis2
    return lis1

import copy
def new_val(lis,num):
    newl = copy.deepcopy(lis)
    newl.append(num)
    return newl

dp = [[[-(10**10)] for i in range(1+n)] for j in range(1+m)]
for i in range(m):
    dp[i][0]=[0]

for i in range(m):
    num=mat[i][0]
    honsu=mat[i][1]
    for j in range(1+n):
        if j<honsu:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = my_max(new_val(dp[i+1][j-honsu] , num),dp[i][j])
ans = dp[-1][-1]
ans.sort(reverse=True)
print(*ans[:-1],sep="")

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a.reverse()
lis = [2,5,5,4,5,6,3,7,6]
mat=[]
for num in a:
    mat.append([num,lis[num-1]])

def new_val(num1,num2): # 123 , 4 -> 4123
    if num1<0:
        return -(10**10)
    if num1==0:
        return num2
    #return int(str(num1)+str(num2))
    return num1+num2

dp = [[-(10**10) for i in range(1+n)] for j in range(1+m)]
for i in range(m):
    dp[i][0]=0

for i in range(m):
    num=mat[i][0]
    honsu=mat[i][1]
    for j in range(1+n):
        if j<honsu:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(new_val(dp[i+1][j-honsu] , num),dp[i][j])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    dp = [""]*(N+1)
    match = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
    for i in range(2, N+1):
        cur = dp[i] if dp[i] else "0"
        for a in A:
            if match[a] == i or (i - match[a] >= 0 and dp[i - match[a]]):
                ne = dp[i - match[a]] + str(a)
                if len(cur) < len(ne) or cur < ne:
                    dp[i] = ne
                    cur = ne
    # print(dp)
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from collections import defaultdict
from copy import deepcopy

def main():
  n, m = map(int, input().split())
  As = list(map(int, input().split()))
  xs = [10**5, 2, 5, 5, 4, 5, 6, 3, 7, 6]
  d = defaultdict(int)
  for A in As:
    if d[xs[A]] < A:
      d[xs[A]] = A
  d = sorted(d.items(), key=lambda x:x[1], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d]
  
  xmin = min(xs)
  vmin = [As[i] for i, x in enumerate(xs) if x==xmin][0]
  digit  = n // xmin
  remain = n % xmin

  cands = [([], remain)]
  vs_list = []
  while len(cands) != 0:
    vs, remain = cands.pop(0)
    if remain == 0:
      vs_list.append(vs)
      continue
    elif remain < 0:
      continue
    for x, A in zip(xs, As):
      if x == xmin:
        continue
      cands.append((vs + [A], remain - (x - xmin)))    
      
  max = 0
  vs_list
  for vs in vs_list:
    vs.sort()
    num = list([vmin]*digit)
    hvs = [v for v in vs if v > vmin][::-1]
    lvs = [v for v in vs if v < vmin]
    for i, hv in enumerate(hvs):
      num[i] = hv
    for i, lv in enumerate(lvs):
      num[-(i+1)] = lv
    cand = int(''.join(map(str, num)))
    if max < cand:
      max = cand
  print(max)
      
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

from collections import defaultdict
from copy import deepcopy

def main():
  n, m = map(int, input().split())
  As = list(map(lambda x:int(x)-1, input().split()))
  xs = [2,5,5,4,5,6,3,7,6]
  d = defaultdict(int)
  for A in As:
    if d[xs[A]] < A:
      d[xs[A]] = A
  d = sorted(d.items(), key=lambda x:x[1], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d]
  
  xmin = min(xs)
  vmin = [As[i] for i, x in enumerate(xs) if x==xmin][0]
  digit  = n // xmin
  remain = n % xmin

  cands = [([], remain)]
  vs_list = []
  while len(cands) != 0:
    vs, remain = cands.pop(0)
    if remain == 0:
      vs_list.append(vs)
      continue
    elif remain < 0:
      continue
    for x, A in zip(xs, As):
      if x == xmin:
        continue
      cands.append((vs + [A+1], remain - (x - xmin)))    
      
  max = 0
  vs_list
  for vs in vs_list:
    vs.sort()
    num = list([vmin+1]*digit)
    hvs = [v for v in vs if v > vmin][::-1]
    lvs = [v for v in vs if v < vmin]
    for i, hv in enumerate(hvs):
      num[i] = hv
    for i, lv in enumerate(lvs):
      num[-(i+1)] = lv    
    cand = int(''.join(map(str, num)))
    if max < cand:
      max = cand
  print(max)
      
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

from collections import defaultdict

def main():
  n, m = map(int, input().split())
  As = list(map(lambda x:int(x)-1, input().split()))
  xs = [2,5,5,4,5,6,3,7,6]
  d = defaultdict(int)
  for A in As:
    if d[xs[A]] < A:
      d[xs[A]] = A
  d = sorted(d.items(), key=lambda x:x[1], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d]
  
  xmin = min(xs)
  vmin = [As[i] for i, x in enumerate(xs) if x==xmin][0]
  digit  = n // xmin
  remain = n % xmin
  num = list([vmin+1]*digit)

  def f(As, xs, remain, state=False):
    li = []
    while remain > 0:
      flag = False
      for i, x in enumerate(xs):
        if x == xmin:
          continue
        if (state or As[i] > vmin) and remain - (x - xmin) >= 0:
          li.append(str(As[i]+1))
          remain -= (x - xmin)
          flag = True
      if not flag:
        break  
    return li, remain
  hvs, remain = (f(As, xs, remain))   
  
  from copy import deepcopy
  cands = [([], remain)]
  lvs_list = []
  while len(cands) != 0:
    lvs, remain = cands.pop(0)
    if remain == 0:
      lvs_list.append(lvs)
      continue
    elif remain < 0:
      continue
    for x, A in zip(xs, As):
      if x == xmin:
        continue
      cands.append((lvs + [A+1], remain - (x - xmin)))    
      
  max = 0
  for lvs in lvs_list:
    for i, hv in enumerate(sorted(hvs, reverse=True)):
      num[i] = hv
    for i, lv in enumerate(sorted(lvs)):
      num[-(i+1)] = lv    
    cand = int(''.join(map(str, num)))
    if max < cand:
      max = cand
  print(max)
      
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

from collections import defaultdict

def main():
  n, m = map(int, input().split())
  As = list(map(lambda x:int(x)-1, input().split()))
  xs = [2,5,5,4,5,6,3,7,6]
  d = defaultdict(int)
  for A in As:
    if d[xs[A]] < A:
      d[xs[A]] = A
  d = sorted(d.items(), key=lambda x:x[1], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d]
  
  xmin = min(xs)
  vmin = [As[i] for i, x in enumerate(xs) if x==xmin][0]
  digit  = n // xmin
  remain = n % xmin
  num = list([vmin+1]*digit)

  def f(As, xs, remain, state=False):
    li = []
    while remain > 0:
      flag = False
      for i, x in enumerate(xs):
        if x == xmin:
          continue
        if (state or As[i] > vmin) and remain - (x - xmin) >= 0:
          li.append(str(As[i]+1))
          remain -= (x - xmin)
          flag = True
      if not flag:
        break  
    return li, remain
  
  hvs, remain = (f(As, xs, remain))   
  d = sorted(d, key=lambda x:x[0], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d] 
  lvs, remain = (f(As, xs, remain, state=True)) 
  
  for i, hv in enumerate(sorted(hvs, reverse=True)):
    num[i] = hv
  for i, lv in enumerate(sorted(lvs)):
    num[-(i+1)] = lv
  print(''.join(map(str, num)))
      
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

from collections import defaultdict

def main():
  n, m = map(int, input().split())
  As = list(map(lambda x:int(x)-1, input().split()))
  xs = [2,5,5,4,5,6,3,7,6]
  d = defaultdict(int)
  for A in As:
    if d[xs[A]] < A:
      d[xs[A]] = A
  d = sorted(d.items(), key=lambda x:x[1], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d]
  
  xmin = min(xs)
  vmin = [As[i] for i, x in enumerate(xs) if x==xmin][0]
  digit  = n // xmin
  remain = n % xmin
  num = list([vmin+1]*digit)

  def f(As, xs, remain, state=False):
    li = []
    while remain > 0:
      flag = False
      for i, x in enumerate(xs):
        if x == xmin:
          continue
        if (state or As[i] > vmin) and remain - (x - xmin) >= 0:
          li.append(str(As[i]+1))
          remain -= (x - xmin)
          flag = True
      if not flag:
        break  
    return li, remain
  
  hvs, remain = (f(As, xs, remain))   
  d = sorted(d, key=lambda x:x[0], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d] 
  lvs, remain = (f(As, xs, remain, state=True)) 
  
  for i, hv in enumerate(sorted(hvs, reverse=True)):
    num[i] = hv
  for i, lv in enumerate(sorted(lvs, reverse=True)):
    num[-(i+1)] = lv
  print(''.join(map(str, num)))
      
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

from collections import defaultdict

def main():
  n, m = map(int, input().split())
  As = list(map(lambda x:int(x)-1, input().split()))
  xs = [2,5,5,4,5,6,3,7,6]
  d = defaultdict(int)
  for A in As:
    if d[xs[A]] < A:
      d[xs[A]] = A
  d = sorted(d.items(), key=lambda x:x[1], reverse=True)
  d = sorted(d, key=lambda x:x[0], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d]
  
  xmin = min(xs)
  vmin = max([As[i] for i, x in enumerate(xs) if x == xmin])
  digit  = n // xmin
  remain = n % xmin
  num = list([vmin+1]*digit)

  def f(As, xs, remain, state=False):    
    li = []
    while remain > 0:
      flag = False
      for i, x in enumerate(xs):
        if x == xmin:
          continue
        if (state or As[i] > vmin) and remain - (x - xmin) >= 0:
          li.append(str(As[i]+1))
          remain -= (x - xmin)
          flag = True
      if not flag:
        break  
    return li, remain
  
  hvs, remain = (f(As, xs, remain)) 
  lvs, remain = (f(As, xs, remain, state=True)) 
  for i, hv in enumerate(sorted(hvs, reverse=True)):
    num[i] = hv
  for i, lv in enumerate(sorted(lvs, reverse=True)):
    num[-(i+1)] = lv
  print(''.join(map(str, num)))
      
if __name__=='__main__':
  main()

Submission status: Wrong Answer

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

from collections import defaultdict

def main():
  n, m = map(int, input().split())
  As = list(map(lambda x:int(x)-1, input().split()))
  xs = [2,5,5,4,5,6,3,7,6]
  d = defaultdict(int)
  for A in As:
    if d[xs[A]] < A:
      d[xs[A]] = A
  d = sorted(d.items(), key=lambda x:x[1], reverse=True)
  d = sorted(d, key=lambda x:x[0], reverse=True)
  As  = [v for k, v in d]
  xs  = [k for k, v in d]
  
  xmin = min(xs)
  vmin = max([As[i] for i, x in enumerate(xs) if x == xmin])
  digit  = n // xmin
  remain = n % xmin
  num = list([vmin+1]*digit)

  def f(As, xs, remain, state=False):    
    li = []
    while remain > 0:
      flag = False
      for i, x in enumerate(xs):
        if x == xmin:
          continue
        if (state or As[i] > vmin) and remain - (x - xmin) >= 0:
          li.append(str(As[i]+1))
          remain -= (x - xmin)
          flag = True
      if not flag:
        break  
    return li, remain
  
  hvs, remain = (f(As, xs, remain)) 
  lvs, remain = (f(As, xs, remain, state=True)) 
  for i, hv in enumerate(hvs):
    num[i] = hv
  for i, lv in enumerate(lvs):
    num[-(i+1)] = lv
  print(''.join(map(str, num)))
    
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
#118_D
ch={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

def max_num(x,y):#yは一桁
    if x==-1:
        return -1
    if x==0:
        return y
    l=list(str(x))+[str(y)]
    l.sort(reverse=True)
    return int(''.join(l))

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

dp=[-1 for _ in range(n+1)]
dp[0]=0
for i in range(1,n+1):
    res=-1
    for x in a:
        if i-ch[x]>=0:
            res=max(res,max_num(dp[i-ch[x]],x))
    dp[i]=res
    
print(dp)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [0]*(N+1)  
for i in range(N+1):
    for j in A:
        if i + B[j] <= N:
            dp[i+B[j]]= max(dp[i]*10+j, dp[i+B[j]])
print(dp[N])

Submission status: Wrong Answer

Solution code:
Q = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}
 
N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
 
# 桁数の最大
dp = [-1] * (N + 1)
dp[0] = 0
 
for a in A:
    for i in range(Q[a], N + 1):
        if dp[i - Q[a]] >= 0:
            dp[i] = max(dp[i], dp[i - Q[a]] + 1)
            print(dp)
 
# 整数の復元
ans = ''
 
# 大きな数から試す
A.sort(reverse=True)
 
i = N
while i:
    for a in A:
        if i - Q[a] >= 0 and dp[i - Q[a]] == dp[i] - 1:
            ans += str(a)
            i -= Q[a]
            break
 
print(ans)

Submission status: Wrong Answer

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

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

c = [(i, d[i]) for i in A]
c.sort(key=lambda x:(-x[1], -x[0]))
dp[0] = ""
dp[1] = ""

for i in range(2, N+1):
    for n, cost in c:
        if i-cost<0: continue
        a = int(dp[i]) if dp[i] else 0
        b = int(str(n) + dp[i-cost])
        if a<b:
            dp[i] = str(n) + dp[i-cost]

a = 0
for s in dp[N]:
    a+= d[int(s)]

if a==N:
    print(dp[N])

Submission status: Wrong Answer

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

def main():
    nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    As = {}
    for a in A:
        As[nums[a]] = max(a, As.get(nums[a], 0))
    A = sorted(list(As.values()), key=lambda x: nums[x])

    def helper(n, A):
        if n == 0:
            return []
        if n < 0:
            return None
        for k, i in enumerate(A):
            s = helper(n - nums[i], A[k:])
            if s is None:
                continue
            return s + [i]
        return None
            
    print(''.join(str(i) for i in sorted(helper(N, A), reverse=True)))

main()