Задание 26
Системный
администратор раз в неделю создает архив пользовательских файлов. Файлы
сохраняются на два диска по следующему алгоритму:
1.
на один из дисков записывается файл самого
большого размера,
2.
на второй диск записывается следующий по
убыванию размера файл,
3.
на второй диск записываются файлы наименьшего
объема до тех пор, пока суммарный объем файлов на втором диске не станет больше
суммарного объема файлов на первом диске,
4.
алгоритм повторяется для другого диска, начиная
с (п.2).
Алгоритм
повторяется до тех пор, пока не будут распределены все файлы.
В файле находится
следующая информация:
В первой строке
записано одно число – количество файлов N
< 100000, в последующих N строках
записаны размеры всех файлов пользователей (0
< x < 10000).
В качестве ответа
приведите два числа – суммарные объемы файлов на первом и втором дисках.
Пример входных данных
6
25
15
10
20
50
40
Для такого случая
программа должна вывести два числа 75 (50+25) и 85 (40+10+15+20).
В магазине по продаже
смартфонов считается, что премиум смартфоны – это самые дорогие смартфоны,
которые имеют суммарную стоимость не более 30% от общей стоимости всех
смартфонов.
В конце продажного
периода магазин решил провести одну из двух акций:
-
скидка 50% на обычный смартфон при покупке
премиум смартфона,
-
при покупке обычного и премиум смартфонов скидка
20% на оба устройства.
В акции участвуют
только чеки, в которых ровно два устройства – обычный и премиум смартфоны.
Определите наиболее
выгодную акцию для магазина, если известно, что покупатели при покупке премиум
смартфона всегда выбирают обычный смартфон с максимальной стоимостью, который
еще не продан.
В качестве ответа
укажите количество премиум смартфонов и суммарную стоимость проданных по
наиболее выгодной акции устройств, если известно, что все смартфоны были
проданы. Для нецелых чисел укажите только целую часть.
В файле в первой
строке записано число N < 100000 –
количество смартфонов в магазине. В каждой из последующий N строк – стоимость одного смартфона в условных единицах (0 < x < 10000).
Пример входных данных
10
500
200
900
1000
200
300
400
700
300
150
Для такого входного
файла суммарная стоимость премиум смартфонов не должна превышать 1350. Значит
премиум смартфон только один.
Поэтому выбираем
одну из акций для одного чека: (1000 + 900*0.5) или (1000+900)*0.8. Для такого
случая вторая акция выгоднее.
Ответом в таком
случае будет пара чисел – 1 и 1520
Планируется
проведение онлайн-конференции, в которой от каждого участника требовалось
заранее записать один видеоролик со своим выступлением. Далее эти видеоролики предполагалось
монтировать в один общий видеоролик. Однако потребовалось ограничить длину
общего ролика некоторым заданным временем.
По заданному
максимальному ограничению длины общего ролика (в секундах) и информации о
длинах роликов участников определите максимальное число выступлений, которые
могут быть смонтированы в общий ролик. Также определите число участников, чьи
выступления заведомо не попадут в общий ролик (при условии попадания в общий
ролик максимального числа выступлений).
В первой строке
входного файла находятся два числа: D - максимальная длительность общего ролика
(натуральное число, не превышающее 100000) и N – количество участников
(натуральное число, не превышающее 1000). В следующих N строках находятся
значения длин выступлений каждого участника (все числа натуральные, не
превышающие 100), каждое в отдельной строке.
Запишите в ответе
два числа: сначала наибольшее число выступлений, которые могут быть
смонтированы в общий ролик, затем число участников, чьи выступления заведомо не
попадут в общий ролик (при условии попадания в общий ролик максимального числа
выступлений).
Пример входного
файла:
300 4
200 110
150 120
При таких исходных
данных можно смонтировать в общий ролик максимум два выступления. Возможные
длины этих двух выступлений 110 и 120, 110 и 150 или 120 и 150. Заведомо не
попадёт в общий ролик одно выступление (длиной 200), поэтому ответ для
приведённого примера: 2 1
Логистическая компания перевозит грузы, упакованные в коробки
одинакового размера. При транспортировке коробки помещаются в контейнеры. В
распоряжении компании имеется Nконтейнеров (1 ≤ N ≤ 105). Каждый контейнер
заполнен некоторым (возможно нулевым) количеством коробок. Компания получила
партию грузов, упакованных в M коробок (0 ≤ M ≤ 104). Требуется распределить новую
партию грузов по контейнерам так, чтобы количество коробок в самом заполненном
контейнере было наименьшим из возможных. Под самым заполненным понимается
контейнер с таким количеством коробок, больше которого нет ни в каком другом
контейнере. Предполагается, что в каждом контейнере имеется достаточно
свободного места, чтобы вместить все коробки из новой партии. Напишите
эффективную по времени и по памяти программу, определяющую наименьшее возможное
количество коробок в наиболее заполненном контейнере.
В первой строке записаны числа N
и M, контейнеры и коробки. В следующих N строках приведено по одному целому
числу — количество коробок в каждом из Nконтейнеров до распределения новых
грузов. В качестве ответа выведите одно число – минимально возможное количество
коробок в наиболее заполненном контейнере.
Пример входных данных:
5
20
1
2
3
4
5
Ответ для примера: 7
Завод “Винтаж” производит оптовую закупку изделий A и Z, на которую
выделена определённая сумма денег. В оптовом магазине есть в наличии партии этих
изделий различных модификаций по различной цене. На выделенные деньги
необходимо приобрести как можно больше изделий A (независимо от модификации).
Закупать можно любую часть каждой партии. Если у магазина закончатся изделия A,
то на оставшиеся деньги необходимо приобрести как можно больше изделий Z.
Известна выделенная для закупки сумма, а также количество и цена различных
модификаций данных изделий в магазине. Необходимо определить, сколько будет
закуплено изделий Z и какая сумма останется неиспользованной.
Входные данные представлены следующим образом. Первая строка входного
файла содержит два целых числа: N – общее количество партий изделий у
поставщика и S – сумма выделенных на закупку денег (в рублях). Каждая из
следующих N строк описывает одну партию изделия: сначала записана буква A или Z
(тип изделия), а затем – два целых числа: цена одного изделия в рублях и
количество изделий в партии. Все данные в строках входного файла разделены
одним пробелом. В ответе запишите два целых числа без пробела: сначала
количество закупленных изделий типа Z, затем оставшуюся неиспользованной сумму
денег.
Пример входного файла
4 1000
A 14 12
Z 30 7
A 40 20
Z 50 15
В данном случае сначала нужно купить изделия A: 12 изделий по 14 рублей
и 24 изделия по 40 рублей. На это будет потрачено 968 рублей. На оставшиеся 32
рубля можно купить 1 изделие Z по 30 рублей. Таким образом, всего будет куплено
1 изделие Z и останется 2 рубля. В ответе надо записать числа 1 и 2.
Комментариев нет:
Отправить комментарий