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):
def search(N, idx):
    global a, M, count

    if N == 0:
        return True
    elif N < 0:
        return False
    elif idx == M:
        return False

    loop = N // a[idx][0]
    for i in range(loop, -1, -1):
        flag = search(N-a[idx][0]*i, idx+1)
        if flag:
            if i:
                count.append([a[idx][1], i])
            return True

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

search(N, 0)

nums = [[A[count[i][0]], count[i][1]] for i in range(len(count))]

nums.sort(reverse=True)

for i in range(len(nums)):
    print(str(nums[i][0]) * nums[i][1], end='')

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

dp = [-1] * (N+1)
for b in B:
    dp[b] = 1

for i in range(1, N+1):
    for b in B:
        if i < b:
            break
        else:
            dp[i] = max(dp[i], dp[i-b]+1)
digit = dp[-1]

for n in A:
    x = a[n-1]
    while dp[N-x] == digit-1:
        print(n, end='')
        N -= x
        digit -= 1
    if N == x:
        print(n, end='')
        N -= x

def search(N, idx):
    global a, M, count

    if N == 0:
        return True
    elif N < 0:
        return False
    elif idx == M:
        return False

    loop = N // a[idx][0]
    for i in range(loop, -1, -1):
        flag = search(N-a[idx][0]*i, idx+1)
        if flag:
            if i:
                count.append([a[idx][1], i])
            return True

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

if 6 in A and 9 in A:
    A.remove(6)

if 5 in A or 3 in A:
    if 2 in A:
        A.remove(2)
    if 5 in A and 3 in A:
        A.remove(3)

x = [2,5,5,4,5,6,3,7,6]
a = [[x[A[i]-1],i] for i in range(len(A))]
count = []
a.sort()

search(N, 0)

nums = [[A[count[i][0]], count[i][1]] for i in range(len(count))]

nums.sort(reverse=True)

for i in range(len(nums)):
    print(str(nums[i][0]) * nums[i][1], end='')

a = [2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = sorted(set(list(map(int, input().split()))), reverse=True)
B = sorted([a[i-1] for i in A])

dp = [-1] * (N+1)
for b in B:
    dp[b] = 1

for i in range(1, N+1):
    for b in B:
        if i < b:
            break
        else:
            dp[i] = max(dp[i], dp[i-b]+1)
digit = dp[-1]

for n in A:
    x = a[n-1]
    while dp[N-x] == digit-1:
        print(n, end='')
        N -= x
        digit -= 1
    if N == x:
        print(n, end='')
        N -= x

def search(N, idx):
    global a, M, count

    if N == 0:
        return True
    elif N < 0:
        return False
    elif idx == M:
        return False

    loop = N // a[idx][0]
    for i in range(loop, -1, -1):
        flag = search(N-a[idx][0]*i, idx+1)
        if flag:
            if i:
                count.append([a[idx][1], i])
            return True

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

if 6 in A and 9 in A:
    A.remove(6)

if 5 in A or 3 in A:
    if 2 in A:
        A.remove(2)
    if 5 in A and 3 in A:
        A.remove(3)
M = len(A)
x = [2,5,5,4,5,6,3,7,6]
a = [[x[A[i]-1],i] for i in range(M)]
count = []
a.sort()

search(N, 0)

nums = [[A[count[i][0]], count[i][1]] for i in range(len(count))]

nums.sort(reverse=True)

for i in range(len(nums)):
    print(str(nums[i][0]) * nums[i][1], end='')

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

dp = [0] * (N+1)

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

for i in range(1, N+1):
    for a in A:
        if 0 <= i-t[a]:     
            if dp[i-t[a]] == 0 and i-t[a] > 0: continue
            dp[i] = max(dp[i], dp[i-t[a]]*10+a)
print(dp[N])

Verdicts: Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Accepted