Задание 26. Информатика. ЕГЭ. Шастин. 19.09.2024
- Просмотры: 233
- Изменено: 24 ноября 2024
(Л. Шастин) Для построения магического карточного домика используется набор из \(N\) игральных карт разных мастей, имеющих весовые номера. Сам карточный домик состоит из некоторого количества уровней. Первый уровень состоит из наибольшего количества карт и служит опорой для остальных уровней. Каждый следующий уровень может включать в себя любое количество карт, которое меньше количества карт, из которых состоит предыдущий уровень. При этом сумма номеров карт, из которых состоит любой следующий уровень, должна быть строго меньше суммы номеров карт, из которых состоит текущий уровень. Идеальным считается карточный домик, состоящий из максимального количества уровней. Определите количество уровней в идеальном карточном домике, который можно построить из карт, имеющихся в наборе, а также минимально возможную сумму номеров всех карт, из которых может состоять такой карточный домик.
Входные данные
В первой строке входного файла находится число \(N\) — количество карт в наборе (натуральное число, не превышающее \(10000\)). В следующих \(N\) строках находятся номера карт (все числа натуральные, не превышающие \(100~000\)), каждое — в отдельной строке.
Запишите в ответе два целых числа: сначала количество уровней в идеальном карточном домике, затем минимально возможную сумму номеров всех карт, из которых может состоять такой домик.
Типовой пример организации данных во входном файле
\(8\)
\(2\)
\(9\)
\(8\)
\(4\)
\(12\)
\(2\)
\(10\)
\(3\)
Пример входного файла приведён для набора из восьми игральных карт. При таких исходных данных идеальный карточный домик будет состоять из трёх уровней: \(\{4, \, 8, \, 9\}\), \(\{3, \, 2\}\), \(\{2\}\). Сумма номеров карт, из которых состоит этот домик, равна \(28\).
Решение:
Python
#N = 8
#cards = [2, 9, 8, 4, 12, 2, 10, 3]
fd = open('26.txt')
N = int(fd.readline())
cards = [int(x) for x in fd]
cards.sort()
level, total, p = 0, 0, 0
rem = N
while level + 1 <= rem:
level += 1
total += sum(cards[p:p+level])
p += level
rem -= level
print(level, total)
Ответ: \(140 \,\, 491509192\)