Полу нужно упаковать четыре прибора, имеющих кубическую форму, с размерами стороны $$$A, B, C, D$$$ соответственно. Для транспортировки Пол использует кубические коробки с размером стороны $$$E$$$. Он может поместить несколько приборов в одну коробку, заполнив оставшееся место гранулами полистирола. Определите минимальное количество коробок, необходимых для упаковки.
Ввод содержит пять целых чисел $$$A, B, C, D, E (1 \le A \le B \le C \le D \le E \le 1000)$$$, по одному числу в строке - размеры приборов в неубывающем порядке и размеры коробки для упаковки.
Вывести одно целое число - вычисленный ответ.
В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
1 2 3 4 7
1
1 1 1 1 1
4
Пояснение к примеру 1: все приборы можно упаковать в одну коробку. Пояснение к примеру 2: для каждого прибора потребуется отдельная коробка.
Чани готовит танцевальный номер к празднику Воды. Для танца "Ручеек" участников номера нужно разделить на пары из мальчика и девочки. Чани хочет разбить детей на пары так, чтобы суммарная разница в росте по всем парам была минимальна. Напишите программу, которая определит, какую минимальную суммарную разницу может получить Чани.
Первая строка ввода содержит одно целое число $$$N (2 \le N \le 100)$$$ – количество пар в танцевальном номере. Вторая строка ввода содержит $$$N$$$ целых чисел в диапазоне от $$$1000$$$ до $$$1800$$$ – рост мальчиков в мм. Третья строка ввода содержит $$$N$$$ целых чисел в диапазоне от $$$1000$$$ до $$$1800$$$ – рост девочек в мм.
Вывести одно целое число – минимальную суммарную разницу в росте по всем парам.
В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
3 1500 1600 1505 1490 1501 1610
24
Пояснение к примеру: минимальная суммарная разница получится, если составить пары так: $$$(1500,1490)$$$, $$$(1505,1501)$$$, $$$(1600,1610)$$$. Сумма будет равна $$$|1500−1490| + |1505−1501| + |1600−1610|=10+4+10=24$$$.
Владимир пригласил гостей на фуршет по поводу своей победы. На праздничном столе расставлен ряд из $$$N$$$ блюд $$$T_1, T_2, ..., T_N$$$, где $$$T_i$$$ обозначает тип $$$i$$$-го блюда.
Перед приходом гостей Владимир решил немного перекусить, для этого он выбрал один тип блюда и стал есть блюда только этого типа. Так как отсутствие нескольких блюд подряд на столе будет слишком заметно, Владимир ест только блюда, между которыми не менее $$$K$$$ других блюд.
Определите, какой тип блюд должен выбрать Владимир, чтобы съесть как можно больше блюд.
Первая строка ввода содержит два целых числа – количество блюд $$$N (1 \le N \le 100000)$$$ и минимальное пропускаемых количество блюд $$$K$$$ $$$(1 \le K \le 100)$$$.
Вторая строка содержит $$$N$$$ целых чисел $$$T_i$$$ – номера типов блюд.
Вывести два целых числа – номер типа блюда и количество съеденных блюд. Если несколько типов блюд обеспечивают максимум количества блюд, то выведите минимальный номер типа из них.
Подзадача 1 (40 баллов) $$$1 \le N \le 100, 1 \le T_i \le 100, K=1$$$ В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 2 (30 баллов) $$$100 \le N \le 100000, 1 \le T_i \le 100000, K=1$$$ Необходимые подзадачи: 1. В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 3 (30 баллов) $$$100 \le N \le 100000, 1 \le T_i \le 10^9, 2 \le K \le 100$$$ Необходимые подзадачи: 1, 2. В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
5 1 1 2 2 1 2
1 2
Пояснение к примеру 1: Владимир может съесть блюда с №1,4 (тип 1) или блюда с №2,5 (тип 2) или блюда с №3,5 (тип 2). Так как количество блюд во всех случаях равно 2, то выводим наименьший номер типа - 1.
Пояснение к примеру 2: Владимир может съесть блюда с №1,3,5 (тип 1).
На планете Арракис вокруг пустыни расположены $$$N$$$ поселений. В $$$i$$$-м поселении может разместиться $$$P_i$$$ колонистов. Челнок, доставляя новых колонистов с орбиты, делает $$$M$$$ рейсов. $$$j$$$-й рейс приземляется возле поселения $$$X_j$$$ и привозит $$$K_j$$$ колонистов.
Часть колонистов остается в поселении $$$X_j$$$. Те, для кого места в этом поселении нет, движутся вокруг пустыни наземным транспортом в следующие поселения, в порядке увеличения номера поселения. После $$$N$$$-го поселения следующим является поселение с номером $$$1$$$. Если в следующем поселении есть места, то часть колонистов остается там. Остальные продолжают движение.
Для каждого рейса нужно подсчитать расходы на перевозку колонистов наземным транспортом, как сумму расстояний, на которое нужно перевезти каждого колониста. Расстояние между соседними поселениями будем считать равным $$$1$$$. Первоначально все поселения пустые и заполняются по мере выполнения рейсов.
Первая строка ввода содержит одно целое число $$$N$$$ $$$(2 \le N \le 100000)$$$ – количество поселений.
Вторая строка ввода содержит $$$N$$$ целых чисел $$$P_i$$$ $$$(1 \le Pi \le 10^9)$$$ – вместимость поселений.
Третья строка ввода содержит одно целое число $$$M$$$ $$$(1 \le M \le 100000)$$$ – количество рейсов.
Следующие $$$M$$$ строк содержат по два целых числа – номер поселения, возле которого приземляется челнок $$$X_j$$$ $$$(1 \le X_j \le N)$$$ и количество колонистов в челноке $$$K_j$$$ $$$(1 \le K_j \le 10^9)$$$. Гарантируется, что сумма всех $$$K_j$$$ не превышает суммы всех $$$P_i$$$.
Для каждого рейса вывести на отдельной строке расходы на перевозку колонистов наземным транспортом.
Подзадача 1 (40 баллов) $$$1 \le N \le 100, 1 \le M \le 100, 1 \le P_i \le 100, 1 \le K_j \le 100$$$ В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (30 баллов) $$$100 \lt N \le 1000, 100 \lt M \le 1000, 1 \le P_i \le 10^9, 1 \le K_j \le 10^9$$$ Необходимые подзадачи: 1. В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (30 баллов) $$$1000 \lt N \le 100000, 1000 \lt M \le 100000, 1 \le P_i \le 10^9, 1 \le K_j \le 10^9$$$ Необходимые подзадачи: 1, 2. В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
5 3 3 4 5 1 2 2 11 3 3
12 6
Пояснение к примеру: Из 11 прибывших 1-м рейсом колонистов 3 остаются в поселении №2, 4 остаются в поселении №3, 4 – в поселении №4. Расходы на перевозку равны 3 $$$0+4 1+4 2=12$$$. После размещения колонистов в поселениях остается следующее количество свободных мест: $$$(3,0,0,1,1)$$$. Из 3 прибывших 1-м рейсом колонистов 1 остается в поселении №4, 1 - в поселении №5, еще 1, проехав поселение №5, доезжает до поселения №1. Расходы на перевозку равны $$$1⋅1+1⋅2+1⋅3=6$$$.
В некоторых точках длинной прямой дороги, идущей через пустыню, расположены посадочные площадки. Известны расстояния от начала дороги до каждой из площадок. Несколько экспедиций хотят добраться до разных точек на дороге. Для этого каждая экспедиция должна сначала высадиться на одной из площадок (не обязательно ближайшей к нужной точке), затратив на это определенное количество топлива для вертолета, а затем проехать от площадки до нужной точки по дороге, затратив дополнительное топливо на каждую единицу пути. Напишите программу, которая рассчитает для каждой экспедиции, какое минимальное количество топлива необходимо для доставки экспедиции в заданную точку.
В первой строке ввода содержатся три целых числа: количество площадок $$$N$$$ $$$(1 \le N \le 10^5)$$$, количество экспедиций $$$M$$$ $$$(1 \le M \le 10^5)$$$ и затраты топлива на проезд одной единицы дороги $$$C$$$ $$$(1 \le C \le 10^9)$$$. Далее следует N строк, содержащих по два целых числа: расстояние от начала дороги до $$$i$$$-й площадки $$$A_i$$$ $$$(0 \le Ai \le 10^9)$$$ и затраты топлива для доставки экспедиции на $$$i$$$-ю площадку $$$B_i$$$ $$$(1 \le Bi \le 10^9)$$$. Все площадки расположены в разных точках дороги. Далее следует $$$M$$$ строк, содержащих одно целое числа: расстояние от начала дороги до цели $$$j$$$-й экспедиции $$$D_j$$$ $$$(0 \le D_j \le 10^9)$$$.
Для каждой экспедиции вывести одно целое число на отдельной строке – минимальное количество топлива для доставки экспедиции в заданную точку.
3 2 1 200 300 300 100 100 250 150 110
250 260
Пояснение к примеру: первая экспедиция высаживается на второй площадке (на расстоянии 300 от начала дороги), затратив 100 единиц топлива, а затем проезжает до точки 150, затратив еще 150 единиц топлива. Вторая экспедиция высаживается на третьей площадке (на расстоянии 100 от начала дороги), затратив 250 единиц топлива, а затем проезжает до точки 110, затратив еще 10 единиц топлива.