Задание 26 ЕГЭ: покупки в пределах суммы

Наибольшее число покупок и самая дорогая из них. Тема номера — обработка данных и моделирование. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

Магазин продаёт наборы деталей по разной цене. Закупщику выделили сумму S. Он хочет купить как можно больше наборов (каждый — не больше одного раза), а если таких вариантов несколько — тот, в котором самый дорогой набор как можно дороже.

По заданному списку цен определите наибольшее количество наборов, которые можно купить, и наибольшую возможную цену самого дорогого набора в такой покупке.

Входные данные. В первой строке входного файла 26.txt записаны два натуральных числа: N — количество наборов и S — выделенная сумма. В каждой из следующих N строк записано натуральное число — цена очередного набора.

Запишите в ответе два числа: сначала наибольшее количество наборов, затем наибольшую возможную цену самого дорогого из них.

Скачать файл к примеру

Решение

Наибольшее количество получается, если брать самые дешёвые наборы. Чтобы самый дорогой набор был как можно дороже, оставляем k − 1 самых дешёвых, а вместо k-го берём самый дорогой набор, на который хватает оставшихся денег.

Ответ: 1057 942.

f = open('26.txt')
n, s = map(int, f.readline().split())
a = sorted(int(f.readline()) for _ in range(n))
total = k = 0
while k < n and total + a[k] <= s:     # сначала самые дешёвые — так покупок больше всего
    total += a[k]
    k += 1
rest = s - (total - a[k - 1])         # k − 1 дешёвых оставляем, последний набор берём подороже
print(k, max(x for x in a[k - 1:] if x <= rest))

Решить такую задачу — новый вариант с проверкой