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

Есеп C. Тасымалсыз

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

1 second

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

256 megabytes

Кішкентай Дамир сандарды қосқанда тасымал жасауды білмейді. Бірақ қосқанда тасымал жасау керек болмаса, ол дұрыс санайды. Мысалға, Дамир $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)"