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):
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def main():
  remain, _ = list(map(int, input().split()))

  costs = list(map(int, input().split()))
  costs = [(c, COSTS[c]) for c in costs]
  costs.sort(key=lambda x:x[1])

  num, cost = costs[0]
  nums = [num] * (remain // cost)
  remain -= cost * len(nums)

  if remain != 0:
    new_costs = []
    exists = set([0])

    for n, c in costs:
      nc = c - cost

      if nc <= remain and nc not in exists:
        new_costs.append((n, nc))

    #max_repeat = min(remain // min(v[1] for v in new_costs), len(nums))
    #rep_nums_list = []

    #for repeat in range(1, max_repeat + 1):
    #  for idxs in itertools.product(range(len(new_costs)), repeat=repeat):
    

    
    #      continue

    

    #max_nums = [0] * len(nums)

    #for rep_nums in rep_nums_list:
    
    
    #  new_nums = nums[:]

    #  if len(uns) > 0:
    

    #  if len(lns) > 0:
    #    new_nums = new_nums[:-len(lns)] + lns

    #  if new_nums > max_nums:
    #    max_nums = new_nums

    #nums = max_nums

  print(''.join(str(v) for v in nums), flush=True)


if __name__ == '__main__':
  main()




#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  r = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)
  n, _ = list(map(int, input().split()))
  ps = list(map(int, input().split()))

  cs = [(p, r[p]) for p in ps]
  cs.sort(key=lambda x: x[1])
  a = []
  s, b = cs[0]

  while n - b > 0:
    a.append(s)
    n -= b

  cs.sort(key=lambda x:-x[0])
  cs = [(p, c - b) for p, c in cs if c != b]
  ds = None

  for i in range(1, len(cs) + 1):
    for ps in itertools.product(range(len(cs)), repeat=i):
      if sum(cs[p][1] for p in ps) == n:
        ds = [cs[p][0] for p in ps]
        break

    if ds is not None:
      break

  uds = [d for d in ds if d >= s]
  lds = [d for d in ds if d < s][::-1]

  a = uds + a[len(uds):]
  a = a[-len(lds):] + lds

  print(''.join(str(v) for v in a), flush=True)


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  
  if len(digits) == 0:
    return False

  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

    
    #  uppers = [d for d in replaces if d > base_digit]
    #  lowers = [d for d in replaces if d < base_digit]

      num = number[:]

    #  if len(uppers) > 0:
    

    #  if len(lowers) > 0:
    

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  r = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)
  n, _ = list(map(int, input().split()))
  ps = list(map(int, input().split()))

  cs = [(p, r[p]) for p in ps]
  cs.sort(key=lambda x: x[1])
  a = []
  s, b = cs[0]

  while n - b > 0:
    a.append(s)
    n -= b

  #cs.sort(key=lambda x:-x[0])
  #cs = [(p, c - b) for p, c in cs if c != b]
  #ds = None

  
  #  for ps in itertools.product(range(len(cs)), repeat=i):
  #    if sum(cs[p][1] for p in ps) == n:
  #      ds = [cs[p][0] for p in ps]
  #      break

  #  if ds is not None:
  #    break

  #uds = [d for d in ds if d >= s]
  #lds = [d for d in ds if d < s][::-1]

  #if len(uds) > 0:
  
  #if len(lds) > 0:
  #  a = a[:-len(lds)] + lds

  print(''.join(str(v) for v in a), flush=True)


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def main():
  remain, _ = list(map(int, input().split()))

  costs = list(map(int, input().split()))
  costs = [(c, COSTS[c]) for c in costs]
  costs.sort(key=lambda x:x[1])

  num, cost = costs[0]
  costs.sort(key=lambda x:-x[0])

  nums = [num] * (remain // cost)
  remain -= cost * len(nums)

  if remain != 0:
    new_costs = []
    exists = set([0])

    for n, c in costs:
      nc = c - cost

      if nc <= remain and nc not in exists:
        new_costs.append((n, nc))

    max_repeat = min(remain // min(v[1] for v in new_costs), len(nums))
    rep_nums_list = []

    for repeat in range(1, max_repeat + 1):
      for idxs in itertools.product(range(len(new_costs)), repeat=repeat):
        nc = sum(new_costs[i][1] for i in idxs)

        if nc != remain:
          continue

        rep_nums_list.append([new_costs[i][0] for i in idxs])

    #max_nums = [0] * len(nums)

    #for rep_nums in rep_nums_list:
    
    
    #  new_nums = nums[:]

    #  if len(uns) > 0:
    

    #  if len(lns) > 0:
    #    new_nums = new_nums[:-len(lns)] + lns

    #  if new_nums > max_nums:
    #    max_nums = new_nums

    #nums = max_nums

  print(''.join(str(v) for v in nums), flush=True)


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):

  number = [base_digit] * base_length
  remain -= base_cost * base_length

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

    
    #  uppers = [d for d in replaces if d > base_digit]
    #  lowers = [d for d in replaces if d < base_digit]

      num = number[:]

    #  if len(uppers) > 0:
    

    #  if len(lowers) > 0:
    

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number))

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  r = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)
  n, _ = list(map(int, input().split()))
  ps = list(map(int, input().split()))

  cs = [(p, r[p]) for p in ps]
  cs.sort(key=lambda x: x[1])
  a = []
  s, b = cs[0]

  while n - b > 0:
    a.append(s)
    n -= b

  cs.sort(key=lambda x:-x[0])
  cs = [(p, c - b) for p, c in cs if c != b]
  ds = None

  for i in range(1, len(cs) + 1):
    for ps in itertools.product(range(len(cs)), repeat=i):
      if sum(cs[p][1] for p in ps) == n:
        ds = [cs[p][0] for p in ps]
        break

    if ds is not None:
      break

  
  # lds = [d for d in ds if d < s][::-1]

  # if len(uds) > 0:
  
  # if len(lds) > 0:
  #  a = a[:-len(lds)] + lds

  print(''.join(str(v) for v in a), flush=True)


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  r = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)
  n, _ = list(map(int, input().split()))
  ps = list(map(int, input().split()))

  cs = [(p, r[p]) for p in ps]
  cs.sort(key=lambda x: x[1])
  a = []
  s, b = cs[0]

  while n - b > 0:
    a.append(s)
    n -= b

  cs.sort(key=lambda x:-x[0])
  cs = [(p, c - b) for p, c in cs if c != b]

  for i in range(1, len(cs) + 1):
    for ps in itertools.product(range(len(cs)), repeat=i):
      if sum(cs[p][1] for p in ps) == n:
        ds = [cs[p][0] for p in ps]
        break

  uds = [d for d in ds if d >= s]
  lds = [d for d in ds if d < s][::-1]

  a = uds + a[len(uds):]
  a = a[-len(lds):] + lds

  print(''.join(str(v) for v in a), flush=True)


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  print(''.join(str(d) for d in number), flush=True)
  return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

    
    #  uppers = [d for d in replaces if d > base_digit]
    #  lowers = [d for d in replaces if d < base_digit]

      num = number[:]

    #  if len(uppers) > 0:
    

    #  if len(lowers) > 0:
    

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  r = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)
  n, _ = list(map(int, input().split()))
  ps = list(map(int, input().split()))

  cs = [(p, r[p]) for p in ps]
  cs.sort(key=lambda x: x[1])
  a = []
  s, b = cs[0]

  while n - b > 0:
    a.append(s)
    n -= b

  cs.sort(key=lambda x:-x[0])
  cs = [(p, c - b) for p, c in cs if c != b]
  ds = None

  for i in range(1, len(cs) + 1):
    for ps in itertools.product(range(len(cs)), repeat=i):
      print(ps)
      if sum(cs[p][1] for p in ps) == n:
        ds = [cs[p][0] for p in ps]
        break

    if ds is not None:
      break

  uds = [d for d in ds if d >= s]
  lds = [d for d in ds if d < s][::-1]

  a = uds + a[len(uds):]
  a = a[-len(lds):] + lds

  print(''.join(str(v) for v in a), flush=True)


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  r = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)
  n, _ = list(map(int, input().split()))
  ps = list(map(int, input().split()))

  cs = [(p, r[p]) for p in ps]
  cs.sort(key=lambda x: x[1])
  a = []
  s, b = cs[0]

  while n - b > 0:
    a.append(s)
    n -= b

  cs.sort(key=lambda x:-x[0])
  cs = [(p, c - b) for p, c in cs if c != b]
  ds = None

  
  #  for ps in itertools.product(range(len(cs)), repeat=i):
  #    if sum(cs[p][1] for p in ps) == n:
  #      ds = [cs[p][0] for p in ps]
  #      break

  #  if ds is not None:
  #    break

  #uds = [d for d in ds if d >= s]
  #lds = [d for d in ds if d < s][::-1]

  #if len(uds) > 0:
  
  #if len(lds) > 0:
  #  a = a[:-len(lds)] + lds

  print(''.join(str(v) for v in a), flush=True)


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]
  max_repeat = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for repeat in range(1, max_repeat + 1):
    for idxs in itertools.product(range(len(digits)), repeat=repeat):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

    
    #  uppers = [d for d in replaces if d > base_digit]
    #  lowers = [d for d in replaces if d < base_digit]

      num = number[:]

    #  if len(uppers) > 0:
    

    #  if len(lowers) > 0:
    

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools


def main():
  r = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)
  n, _ = list(map(int, input().split()))
  ps = list(map(int, input().split()))

  cs = [(p, r[p]) for p in ps]
  cs.sort(key=lambda x: x[1])
  a = []
  s, b = cs[0]

  while n - b > 0:
    a.append(s)
    n -= b

  cs.sort(key=lambda x:-x[0])
  cs = [(p, c - b) for p, c in cs if c != b]
  ds = None

  for i in range(1, len(cs) + 1):
    for ps in itertools.product(range(len(cs)), repeat=i):
      if sum(cs[p][1] for p in ps) == n:
        ds = [cs[p][0] for p in ps]
        break

    if ds is not None:
      break

  uds = [d for d in ds if d >= s]
  lds = [d for d in ds if d < s][::-1]

  # if len(uds) > 0:
  
  # if len(lds) > 0:
  #  a = a[:-len(lds)] + lds

  print(''.join(str(v) for v in a), flush=True)


if __name__ == '__main__':
  main()



#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools

COSTS = (99, 2, 5, 5, 4, 5, 6, 3, 7, 6)


def gen(base_digit, base_cost, base_length, digits, remain):
  number = [base_digit] * base_length
  remain -= base_cost * base_length

  if remain == 0:
    print(''.join(str(d) for d in number), flush=True)
    return True

  digits = [(d, c - base_cost) for d, c in digits if d != base_digit and c - base_cost <= remain]

  if len(digits) == 0:
    return False

  max_size = min(remain // min(digits, key=lambda x: x[1])[1], len(number))
  numbers = []

  for size in range(1, max_size + 1):
    for idxs in itertools.combinations_with_replacement(range(len(digits)), size):
      if sum(digits[i][1] for i in idxs) != remain:
        continue

      replaces = [digits[i][0] for i in idxs]
      replaces.sort(reverse=True)
      uppers = [d for d in replaces if d > base_digit]
      lowers = [d for d in replaces if d < base_digit]

      num = number[:]

      if len(uppers) > 0:
        num = uppers + num[len(uppers):]

      if len(lowers) > 0:
        num = num[:-len(lowers)] + lowers

      numbers.append(num)

  if len(numbers) == 0:
    return False

  number = max(numbers)

  print(''.join(str(d) for d in number), flush=True)

  return True


def main():
  remain, _ = list(map(int, input().split()))

  digits = {}

  for d in map(int, input().split()):
    if COSTS[d] not in digits or digits[COSTS[d]] < d:
      digits[COSTS[d]] = d

  digits = [(d, c) for c, d in digits.items()]
  base_digit, base_cost = min(digits, key=lambda x: x[1])

  for length in range(remain // base_cost, -1, -1):
    if gen(base_digit, base_cost, length, digits, remain):
      break


if __name__ == '__main__':
  main()



Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Accepted