Решайте задания по одному, проверяйте себя сразу и открывайте подсказки там, где нужно.
Верный ответ: 191 31
Сначала сохраняются обязательные файлы.
В наборе имеется 7 файлов размера 99. Они занимают 7 · 99 = 693 единицы, поэтому после их сохранения остаётся 2587 − 693 = 1894 единицы. Исключать эти файлы ради большего количества маленьких нельзя: условие прямо требует сохранить их в первую очередь.
На оставшемся месте максимизируем количество.
Остальные файлы сортируем по возрастанию. Сумма 184 наименьших файлов равна 1883. Следующий файл имеет размер 20, и 1883 + 20 = 1903, что больше оставшегося объёма. Значит, дополнительно можно сохранить максимум 184 файла.
Ищем максимальный размер одного дополнительного файла.
183 наименьших файла занимают 1863 единицы, поэтому для последнего остаётся 31. В данных есть неприоритетный файл размера 31; файл большего размера уже не помещается. Общее количество равно 7 + 184 = 191.
Структура решения:
mandatory = [x for x in files if x == 99] other = sorted(x for x in files if x != 99) free = S - sum(mandatory)Второе число относится именно к дополнительно выбранным файлам. Если учитывать обязательные файлы, оно всегда было бы равно 99 и не отражало бы второй этап оптимизации.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19219.
Верный ответ: 19829
Каждый выбранный файл расходует на две единицы больше своего исходного размера. Поэтому при проверке вместимости используется величина x + 2, а не x.
Максимальное количество.
Сортируем файлы по возрастанию исходного размера: прибавление одинаковых двух единиц ко всем файлам не меняет их порядок. Сумма занимаемых размеров 198 самых маленьких файлов равна 2581. Следующий файл вместе со служебной записью занимает 25 единиц, и 2581 + 25 = 2606, что больше S = 2587. Следовательно, 199 файлов не помещаются.
Максимальный исходный размер при количестве 198.
197 файлов с наименьшими занимаемыми размерами требуют 2556 единиц. Для последнего файла остаётся 31 единица с учётом служебной записи, поэтому его исходный размер должен быть не больше 29. Файл размера 29 в данных есть и помещается.
Фрагмент решения:
a.sort()
s = 0
k = 0
while k < N and s + a[k] + 2 <= S:
s += a[k] + 2
k += 1
base = sum(x + 2 for x in a[:k - 1])
last = max(x for x in a[k - 1:] if base + x + 2 <= S)После вычислений числа 198 и 29 соединяются без пробела только из-за формата ответа, указанного в условии.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19192.
Верный ответ: 4729
В один ящик можно высыпать содержимое не более двух корзин, а сумма должна быть ровно 100. Поэтому корзина с x монетами может образовать пару только с корзиной, в которой 100 − x монет.
Почему используется минимум двух количеств.
Если корзин с x монетами имеется A, а корзин с 100 − x монетами — B, то можно собрать не более min(A, B) ящиков: каждая пара расходует по одной корзине каждого вида, повторно использовать корзину нельзя.
Пары достаточно рассматривать для x от 1 до 49. Если после пары 30 и 70 отдельно рассмотреть 70 и 30, те же корзины будут посчитаны второй раз. Особый случай — корзины по 50 монет: для одного ящика нужны две такие корзины, поэтому их вклад равен count[50] // 2.
Программа:
from collections import Counter
cnt = Counter(baskets)
boxes = 0
for x in range(1, 50):
boxes += min(cnt[x], cnt[100 - x])
boxes += cnt[50] // 2В файле 99 корзин по 50 монет, они дают 49 ящиков. Все остальные взаимодополняющие пары дают ещё 4680 ящиков. Остаточная непарная корзина каждого вида использоваться не может, потому что делить её содержимое запрещено.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19165.
Верный ответ: 1125 49
Приоритетные файлы нельзя смешивать с обычным жадным выбором.
Сначала отбираем все файлы размеров от 50 до 60 включительно. Таких файлов 41, их суммарный размер равен 2222. Они помещаются, поэтому для остальных файлов остаётся 13 820 − 2222 = 11 598 единиц.
Максимизируем число неприоритетных файлов.
Из дальнейшего рассмотрения исключаем размеры 50–60, затем сортируем остальные файлы по возрастанию. Сумма 1084 наименьших неприоритетных файлов равна 11 581. Следующий файл имеет размер 41, и 11 581 + 41 = 11 622, поэтому 1085 дополнительных файлов уже не помещаются.
Максимизируем размер одного дополнительного файла.
Оставим 1083 наименьших неприоритетных файла: они занимают 11 540 единиц. На последний остаётся 58. Но размеры 50–60 являются приоритетными и уже исключены из дополнительного набора, поэтому самый большой допустимый неприоритетный размер — 49. Всего сохраняется 41 + 1084 = 1125 файлов.
Ключевая структура решения:
priority = [x for x in files if 50 <= x <= 60] other = [x for x in files if not (50 <= x <= 60)] free = S - sum(priority) other.sort()Если сначала выбрать самые маленькие файлы из общего списка, часть обязательных файлов может не поместиться — это нарушит условие, даже если количество окажется больше.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19138.
Верный ответ: 21525
Размеры сортируем по возрастанию, потому что именно самые маленькие файлы дают наибольшее возможное количество пользователей. Сумма 215 наименьших файлов равна ровно 2587 — всему свободному объёму диска. Следовательно, 215 файлов сохранить можно, а добавить 216-й уже невозможно.
Для второго числа оставляем 214 наименьших файлов. Их сумма равна 2562, поэтому на последний файл остаётся 2587 − 2562 = 25 единиц. В данных есть файл размера 25, а любой файл большего размера превысил бы вместимость.
Почему ответ записывается слитно.
По условию два числа нужно записать без пробела: сначала количество 215, затем размер 25. Это требование относится только к форме записи; в вычислениях числа остаются самостоятельными.
Алгоритм:
a.sort()
s = 0
k = 0
while k < N and s + a[k] <= S:
s += a[k]
k += 1
base = sum(a[:k - 1])
last = max(x for x in a[k - 1:] if base + x <= S)Точное заполнение диска суммой 215 минимальных файлов дополнительно подтверждает найденное максимальное количество.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19111.
100 4 80 30 50 40Для примера ответ: 2 50.
Верный ответ: 561 50
Сначала ищем максимальное количество.
Чтобы взять как можно больше подарков, коробки сортируют по возрастанию объёма. Если набор из самых маленьких коробок уже не помещается, никакой другой набор того же, большего количества поместиться не сможет: замена маленькой коробки на большую только увеличивает сумму.
Сумма 561 наименьшей коробки равна 7973. Следующая коробка имеет объём 29, и 7973 + 29 = 8002, что больше объёма мешка 8000. Поэтому 562 подарка взять невозможно.
Затем увеличиваем одну коробку, сохраняя количество.
Оставим 560 самых маленьких коробок. Они занимают 7944 единицы, поэтому на последнюю коробку остаётся 56. Среди коробок, которые ещё можно выбрать, максимальный объём, не превышающий 56, равен 50. Именно поэтому нельзя просто вывести объём 561-й коробки после сортировки: требуется найти наибольшую допустимую замену.
Схема программы:
boxes.sort()
s = 0
k = 0
while k < N and s + boxes[k] <= S:
s += boxes[k]
k += 1
base = sum(boxes[:k - 1])
large = max(x for x in boxes[k - 1:] if base + x <= S)Первый цикл отвечает за число подарков, а поиск по оставшимся коробкам — за максимально возможный объём одной из них.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19084.
Верный ответ: 1148 96
Сравнивать нужно размеры после сжатия.
Файл x ≤ 50 занимает x единиц, а для x > 50 его размер равен ⌈0,6x⌉. Поэтому сортировка только по исходным размерам неверна: например, исходный файл 60 после сжатия занимает 36 единиц и может оказаться выгоднее несжатого файла 40.
Удобно для каждого файла хранить пару «занимаемый размер, исходный размер» и сортировать по первому компоненту. Сумма 1148 наименьших занимаемых размеров равна 13 782. Следующий размер равен 39, и 13 782 + 39 = 13 821, что больше S = 13 820. Следовательно, 1149 файлов не помещаются.
Для второго критерия оставляем 1147 файлов с минимальными занимаемыми размерами. Они занимают 13 743 единицы, поэтому для ещё одного файла остаётся 77 единиц. Самый большой исходный файл в наборе имеет размер 96; после сжатия он занимает ⌈96 · 0,6⌉ = 58 единиц и помещается. Более крупного файла во входных данных нет.
Вычисление сжатого размера без вещественных чисел:
def packed(x):
if x <= 50:
return x
return (3 * x + 4) // 5 # округление 3*x/5 вверх
items = sorted((packed(x), x) for x in files)При поиске максимального количества складывается первый элемент пары, а при выборе последнего файла сравнивается второй — исходный размер.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19057.
20 3 10 17 15 13 12 11 7 6 4 3 2После выполнения алгоритма на дисках остаётся 0, 1 и 0 единиц, поэтому для примера ответ: 1 2.
Верный ответ: 230 2
Для решения требуется полностью воспроизвести работу скрипта. Простое деление общего объёма архивов на суммарную ёмкость дисков не подходит: часть файлов откладывается из-за распределения свободных промежутков по разным дискам.
Храним массив свободных остатков и индекс диска, с которого начинается проверка очередного архива. После успешной записи индекс переносится на диск, следующий за использованным.
Моделирование:
files.sort(reverse=True)
free = [V] * K
start = 0
for x in files:
for shift in range(K):
d = (start + shift) % K
if x <= free[d]:
free[d] -= x
start = (d + 1) % K
break
free_sum = sum(free)
max_free = max(free)
disk = free.index(max_free) + 1Метод index возвращает первое вхождение максимума, поэтому при равенстве остатков автоматически выбирается диск с наименьшим номером.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19030.
6 720 100 315 120 160 140 300В данном случае сначала нужно взять груз массой 315 кг. Остается 405 кг. После этого можно вывезти ещё максимум 3 груза. Это можно сделать тремя способами: 100 + 120 + 140, 100 + 140 + 160, 100 + 120 + 160. Выбираем способ, при котором вывозится груз наибольшей возможной массы. Таких способов два: 100 + 120 + 160, 100 + 140 + 160. Из этих способов выбираем тот, при котором больше масса второго по величине груза, то есть 100 + 140 + 160. Всего получается 4 груза общей массой 715 кг. Ответ: 4 715.
Верный ответ: 543 130311
Сначала выполняется обязательный приоритет.
Нельзя сразу сортировать все грузы по возрастанию: грузы массой от 310 до 320 кг должны быть загружены раньше остальных. В файле таких грузов 351, их общая масса равна 110 566 кг. Все они помещаются, поэтому после приоритетной погрузки остаётся 130 311 − 110 566 = 19 745 кг.
Затем максимизируется количество остальных грузов.
Оставшиеся массы сортируем по возрастанию. Сумма 192 самых лёгких грузов равна 19 646 кг, а добавление следующего груза массой 105 кг дало бы 19 751 кг, что уже больше остатка. Следовательно, дополнительно можно взять не более 192 грузов.
Учитываем правило выбора при одинаковом количестве.
Чтобы сделать набор из 192 грузов лексикографически самым тяжёлым, оставляем 191 самый лёгкий груз. Их сумма равна 19 541 кг, поэтому для последнего груза остаётся 204 кг. В данных есть груз массой 204 кг; более тяжёлый уже не помещается. Получается 351 + 192 = 543 груза, а суммарная масса равна полной грузоподъёмности 130 311 кг.
Фрагмент алгоритма для второй части:
other.sort()
s = 0
k = 0
while k < len(other) and s + other[k] <= free:
s += other[k]
k += 1
base = sum(other[:k - 1])
last = max(x for x in other[k - 1:] if base + x <= free)Первый этап нельзя смешивать со вторым: иначе лёгкие грузы вытеснят обязательные грузы диапазона 310–320 кг, и будет нарушено условие задачи.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19003.
100 4 70 10 25 3При таких исходных данных можно сохранить три файла – 70, 25, 3. Поэтому ответ должен содержать два числа – 3 и 3.
Верный ответ: 837 61
Администратор не стремится получить наибольшее количество файлов любой ценой. По условию он сначала пытается сохранить самые большие файлы, поэтому размеры сортируются по убыванию.
Для каждого файла выполняется проверка: если размер не превосходит свободный остаток, файл сохраняется; иначе файл пропускается. После пропуска цикл продолжается, так как следующий, меньший файл может поместиться.
Программа:
files.sort(reverse=True)
free = S
count = 0
smallest = None
for x in files:
if x <= free:
free -= x
count += 1
smallest = xТак как файлы просматриваются от больших к маленьким, переменная smallest после каждого успешного сохранения содержит размер наименьшего из уже выбранных файлов. В данном файле после сохранения 836 файлов остаётся 61 единица; файл размера 61 помещается и полностью заполняет диск. В итоге выбрано 837 файлов, а меньшие файлы уже не могут быть добавлены из-за нулевого остатка.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18976.