--->
4 задач
<---
Вася коллекционирует спичечные этикетки. Для этого у него есть N альбомов вместимостью K1, K2, …, KN этикеток. Вася хочет, чтобы в случае утери одного любого альбома каждая этикетка осталась у него хотя бы в одном экземпляре. Для этого он покупает каждую этикетку в двух экземплярах, и наклеивает их в два разных альбома. Какое максимальное количество различных этикеток при этом может оказаться в его коллекции?<
Входной файл содержит сначала число N — количество альбомов, а затем N чисел K1, K2, …, KN, задающих вместимости альбомов. N — натуральное число из диапазона от 2 до 1000. Вместимость каждого альбома задается натуральным числом, суммарная вместимость всех альбомов не превышает 100000 этикеток.
В выходной файл выведите сначала число E — максимальное количество различных этикеток, которое может собрать Вася с соблюдением выдвинутого условия. Затем выведите E пар чисел — каждая пара чисел задает номера двух альбомов, куда будет вклеена очередная этикетка.
4 1 2 1 1
2 1 2 2 3
Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции.
На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым, оказывается нарушен классический принцип «от перестановки мест слагаемых сумма не меняется» ).
Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в \(1.05), потом результат — с 12 (\)1.65), и затем — с 13 (\(2.3), то всего мы заплатим \)5, если же сначала отдельно сложить 10 и 11 (\(1.05), потом — 12 и 13 (\)1.25) и, наконец, сложить между собой два полученных числа (\(2.3), то в итоге мы заплатим лишь \)4.6.
Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.
Во входном файле записано число N (2N100000). Далее идет N натуральных чисел, которые нужно сложить, каждое из них не превышает 10000.
В выходной файл выведите, сколько денег нам потребуется на нахождение суммы этих N чисел. Результат должен быть выведен с двумя знаками после десятичной точки.
4 10 11 12 13
4.60
2 1 1
0.10
Помимо открыток Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще K–2 своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете P тортиков. Настал черед рассчитываться за них.
В магазине есть N работающих касс, занумерованных числами от 1 до N. Про i-ю кассу известно, что кассиру требуется Ai единиц времени на обработку одного товара и Bi единиц времени для того, чтобы рассчитаться с покупателем. Обойдя все кассы, школьники посчитали, что на обслуживание покупателей, уже стоящих в i-ю кассу, уйдет Ti единиц времени.
Теперь Петя и Вася задались вопросом, в какие кассы надо встать им и их друзьям (в каждую из выбранных касс должен стоять хотя бы один из них, и каждый из них может стоять не более, чем в одну кассу, поэтому суммарно они могут стоять не более чем в K касс) и сколько тортиков каждый должен взять, чтобы последний из них вышел из магазина как можно раньше. Некоторые из ребят могут в кассу не стоять, а, отдав все тортики другим, выйти через специальный выход для тех, кто ничего не купил.
Напишите программу, которая определит это минимальное время.
В первой строке записано одно число N — количество касс в супермаркете (1 ≤ N ≤ 100000). В следующих N строках записано по три числа Ai, Bi, Ti (0 ≤ Ai, Bi, Ti ≤ 100000). В последней строке записаны два числа — K и P — число школьников и покупок у них соответственно (0 ≤ P ≤ 100000, 2 ≤ K ≤ 100000).
Все числа во входном файле целые.
Выведите минимальное время выхода последнего школьника из магазина.
Комментарии к примерам тестов
Здесь лучше всего встать в обе кассы и купить там по одному тортику.
Выгоднее всего одному из школьников встать со всеми тортиками в первую кассу, а остальным выйти без покупок.
Частичные ограничения
Первая группа состоит из тестов, в которых N ≤ 10 и оценивается в 30 баллов.
Вторая группа состоит из тестов, в которых N ≤ K ≤ 100000 и оценивается в 30 баллов.
Третья группа состоит из тестов без дополнительного ограничения и оценивается в 40 баллов.
2 100 10 40 10 100 50 2 2
160
3 1 2 0 5 2 1 2 10 1 3 5
7
Одна Очень Престижная Олимпиада, как и все престижные олимпиады в последнее время, состоит из двух туров - регионального и заключительного. Правила отбора во второй тур (заключительный этап) просты:
Известно, что никакие два участника не набрали одинаковое количество баллов. По информации о результатах первого тура помогите жюри установить минимально возможный проходной балл, при котором все правила отбора будут выполнены.
В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники (\(1 \le M < N\)). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника (\(1 \le id \le N\)), далее номер региона \(region\), в котором данный участник учится (\(1 \le region \le R\)), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.
Гарантируется, что все идентификаторы участников различны, никакие два участника не набрали одинаковое число баллов, и выполнить все правила отбора возможно.
Выведите одно число - минимальный проходной балл, который можно установить.
Тесты состоят из четырёх групп. Во всех тестах \(0 \le score \le 10^9\).
9 6 5 6 1 799 0 2 4 995 0 1 4 989 1 7 2 538 0 5 4 984 0 8 2 1000 0 3 2 998 0 4 2 823 1 9 1 543 0
985