Problem: 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.

Submission attempts (in order):
pair = [[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()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp



def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                print(j)
                if index == j[1]:
                    return str(j[0])
            return ""
        elif index - given_pair[x][1] < 0:
            return "-1"
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

pair = [[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()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x-1] for x in given],key = lambda x :x[1])
def rec(n,t_list,pair_list):
  if n==0:
    return t_list
  elif n< pair_list[0][1]:
    return t_list[:-1]
  else:
    a = rec(n-pair_list[0][1],t_list+[pair_list[0][0]],pair_list)
    if pair_list[1:]!=[]:
        b = rec(n,t_list,pair_list[1:])
        if len(a)>len(b):
                return a
        elif len(a)==len(b):
                if(a[-1]>b[-1]):
                        return a
                else:
                        return b
        else:
                return b
    else:
        return a

kotae = map(str,sorted(rec(n,[],given_pair),reverse=True))
print("".join(kotae))

pair = [[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()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp

print(given_pair)

print(dp)


def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                print(j)
                if index == j[1]:
                    return str(j[0])
            return ""
        elif index - given_pair[x][1] < 0:
            return "-1"
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

pair = [[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()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x-1] for x in given],key = lambda x :x[1])
def rec(n,t_list,pair_list):
  if n==0:
    return t_list
  elif n< pair_list[0][1]:
    return t_list[:-1]
  else:
    a = rec(n-pair_list[0][1],t_list+[pair_list[0][0]],pair_list)
    if pair_list[1:]!=[]:
        b = rec(n,t_list,pair_list[1:])
        if len(a)>len(b):
                return a
        elif len(a)==len(b):
                if(a[-1]>=b[-1]):
                        return a
                else:
                        return b
        else:
                return b
    else:
        return a

kotae = map(str,sorted(rec(n,[],given_pair),reverse=True))
print("".join(kotae))


n,m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(n)]

s=[]
for t in e:
  b_list=0
  for x in t[1:]:
    b_list = b_list | pow(2,x-1)
  s.append(b_list)
result=pow(2,30)-1
for i in s:
   result = result & i
cnt=0
for i in range(30):
  if result & pow(2,i):
    cnt+=1
print(cnt)

n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

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

for i in range(n+1):
    max_tmp = -float("inf")
    for j in am:
        if i-c[j-1]>=0:
            max_tmp = max(dp[i-c[j-1]]+1, max_tmp)
    dp[i] = max(dp[i],max_tmp)

tmp_n = n
ans =[]
for i in range(dp[n]):
    for j in range(m):
        if i==dp[n]-1 and tmp_n- c[am[j]-1] != 0:
            continue
        if tmp_n - c[am[j]-1] >= 0 and dp[tmp_n - c[am[j]-1]] == dp[tmp_n] -1:
            ans.append(am[j])
            tmp_n -= c[am[j]-1]
            break


print(ans)

pair = [[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()]
given = sorted([int(i) for i in input().split()])
given_pair = sorted([pair[x - 1] for x in given], reverse=True)

dp = (1 + n) * [0]
max_dp = 0
for i in range(n + 1):
    if i == 0:
        dp[i] = 0
    for j in range(m):
        if i - given_pair[j][1] >= 0:
            if dp[i - given_pair[j][1]] + 1 >= max_dp:
                max_dp = dp[i - given_pair[j][1]] + 1
    dp[i] = max_dp

print(given_pair)

print(dp)


def choice_list(x, index):
#    print("now_index", index)
#    print(given_pair[x][1])
#    print("now_dp_atai", dp[index - given_pair[x][1]])
    if dp[index - given_pair[x][1]] == dp[index] - 1:
        if dp[index - given_pair[x][1]] == 0:
            for j in given_pair:
                if index == j[1]:
                    return str(j[0])
            return ""
        elif index - given_pair[x][1] < 0:
            return "-1"
        else:
            return str(given_pair[x][0]) + choice_list(x, index - given_pair[x][1])

    else:
        return choice_list(x + 1, index)


print(choice_list(0, n))

n, m = [int(i) for i in input().split()]
am = sorted([int(i) for i in input().split()],reverse=True)
c = [2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-1 for i in range(n+1)]
dp[0]=0
for i in range(n+1):
    #max_tmp = -float("inf")
    for j in am:
        if i+c[j-1]<=n:
            dp[i+c[j-1]] = max(dp[i+c[j-1]], dp[i]+1)
#print(dp)
tmp_n = n
ans =""
for i in range(dp[n]):
    for j in range(m):
        if i==dp[n]-1 and tmp_n- c[am[j]-1] != 0:
            continue
        if tmp_n - c[am[j]-1] >= 0 and dp[tmp_n - c[am[j]-1]] == dp[tmp_n] -1:
            ans+=(str(am[j]))
            tmp_n -= c[am[j]-1]
            break


print(ans)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Accepted