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)