2-й этап Республиканской олимпиады по информатике 2022-2023

Задача C. Без переноса

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Маленький Дамир еще не научился делать переносы при сложении чисел. Но он отлично справляется со сложением чисел, где не нужно делать перенос. Например, Дамир не сможет посчитать $27+5$, но легко посчитает $31421 + 6374 + 3$. У вас есть $N$ чисел. Вам нужно среди них выбрать максимальное количество чисел, которых можно сложить без переноса.

Формат входного файла

В первой строке находится одно целое число $N(1 <= N <= 18)$. Во второй строке находятся $N$ целых числа $a_1, a_2, ..., a_N$($1 <= a_i <= 10^8$).

Формат выходного файла

Выведите ответ на задачу.

Система оценки

Данная задача состоит из $10$ тестов. Каждый тест оценивается в $10$ баллов.

• Тест 1. Пример из условия.
• Тесты 2-4: $n = 2$.
• Тесты 5-7: $1 <= a_i <= 9$.
• Тесты 8-10: без дополнительных ограничении.

Пример:

Вход

5
8 45 32 27 111

Ответ

3

Замечание

В первом примере можно выбрать три числа: $45$,$32$,$111$. ( Temirlan Satylkhanov )

Комментарий/решение

s,p= map(int, input().split())

res=0

for a in range(1,s):

for b in range(1,s):

if a+b>=s or a*b>p:

break

for c in range(1,s):

if a+b+c>=s or a*b*c>p:

break

d=min(s-a-b-c, p//(a*b*c))

res+=d

print(res)

from itertools import combinations

input()

a = input().split()

a = list(map(list, a))

a = [list(map(int, m)) for m in a]

result = []

for r in range(1, len(a) + 1):

(tab) result.extend(combinations(a, r))

result = [list(x) for x in result]

def TSum(a):

(tab) c = min([len(m) for m in a])

(tab ) for i in range(-1,-c-1,-1):

(tab)(tab) if sum([m[i] for m in a])>9:

(tab)(tab)(tab) return False

(tab) return True

for i in range(-1,-len(result)-1,-1):

(tab) if TSum(result[i]):

(tab)(tab) print(len(result[i]))

(tab)(tab) break

# Заметил что в комментариях не выводятся пробелы в началах строк, поэтому там где нужно, я заменил их на надпись "(tab)"