Алгоритмы сортировки

ID 60947. Шоколадная мудрость

Шоколад помогает развивать ум и укреплять дух! Старец Летовец после своих занятий угощает своих учеников шоколадом. На следующем занятии у него будет M учеников и каждому из них Старец хочет дать по одной плитке шоколада.

Чтобы купить нужное количество шоколада, старец отправил своего праправнука Летовёнка разузнать, какое минимальное количество денег ему понадобится.
Оказывается, каждый магазин продаёт шоколад по разной цене. В i-м магазине можно купить не более Bi​ плиток шоколада по цене Аi​ рублей за плитку. Летовец хочет потратить как можно меньше денег, но при этом купить ровно M плиток шоколада. 

Помогите Летовёнку посчитать какую минимульную сумму на шоколад потратит старец Летовец. 

Примеры

ID 60876. Необычная сортировка

Магане любит брать обычные вещи и выворачивать их смысл наизнанку. В этот раз ей попался совершенно обычный массив целых чисел, и чтобы избавиться от скуки, она хочет сделать его отсортированным по неубыванию.

Для этого Магане может один раз выбрать произвольный набор различных позиций в массиве и заменить элементы на этих позициях на противоположные, то есть умножить их на \(-1\). Например, чтобы сделать массив \([-4, 4, 1, 3, -10]\) отсортированным, она может умножить на \(-1\) числа на позициях \(2\) и \(5\), и получить массив \([-4, -4, 1, 3, 10]\).

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

Помогите ей с этой задачей! Поскольку итоговое количество способов может быть слишком большим, найдите ответ по модулю \(998244353\).

В первой строке ввода записано целое число \(n\) — количество элементов в массиве (\(1 \leqslant n \leqslant 10^6\)).

Формат входных данных
Во второй строке через пробел перечислены \(n\) целых чисел \(a_1\), \(a_2\), …, \(a_n\) — элементы массива (\(-10^9 \leqslant a_i \leqslant 10^9\)).

Формат выходных данных
Выведите одно число — количество способов отсортировать массив указанным образом (по модулю \(998244353\)).

ID 55450. Экономический кризис

Экономический кризис вынуждает центробанки многих стран выделять большие пакеты экономической помощи инвестиционным и сберегательным банкам для поддержания ликвидности и сохранения кредитных рынков.

Центробанк Флатландии планирует выделить N пакетов помощи. Каждый пакет характеризуется его суммой A_i.

Банки предоставили запросы на помощь. На данный момент поступило M запросов. Каждый запрос характеризуется его продолжительностью B_i дней.

Законы Флатландии требуют, чтобы при возвращении пакета помощи банк каждый день возвращал центробанку одинаковую целую сумму флатландских рублей. Таким образом, пакет с суммой A и продолжительностью B можно выделить только в случае если A делится на B.

По известной информации о пакетах помощи и запросах подсчитайте количество возможных пар пакет-запрос.

Входные данные
Первая строка содержит целое число N – количество пакетов помощи (1 ≤ N ≤ 100 000). Вторая строка содержит N целых чисел: a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁶).

Вторая строка содержит целое число N – количество запросов (1 ≤ M ≤ 100 000). Вторая строка содержит N целых чисел: b₁, b₂, . . . , b_n (1 ≤ b_i ≤ 10⁶).

Выходные данные
Выведите количество возможных пар.

Комментарий к примеру

Пары могут быть следующие: (3, 1) дважды как (a₁, b₁) и (a₁, b₂), (3, 3), (4, 1) дважды, (4, 2), (5, 1) дважды, (6, 1) дважды, (6, 2) и (6, 3).

ID 55120. Площадь прямоугольников

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить площадь фигуры, образованной объединением данных прямоугольников.

Входные данные
В первой строке находится число прямоугольников - N. Затем идут N строк, содержащих по 4 числа: x₁, y₁, x₂, y₂ - координаты двух противоположных углов прямоугольника. 1 <= N <= 100, координаты целые и по абсолютному значению не превосходят 10 000.

Выходные данные
Вывести одно число - площадь фигуры.

ID 54353. Антон решает задачи

Мальчик Антон решает вступительную работу в летний математический лагерь. В ней N заданий, которые можно выполнять в произвольном порядке. Разные задачи требуют разного времени для решения. При этом известно, что если задание с номером i выполнять j-м по счету, Антону потребуется T_i*j
 времени: чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую, то потребуется T₁*1 + T₂*2 времени, а если выполнить сначала вторую задачу, а затем первую – то T₂*1 + T₁*2. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени.

Входные данные
В первой строке вводится число N, во второй строке —N чисел через пробел T₁, T₁, …, T_N, разделенные пробелами. Все числа целые и удовлетворяют следующим ограничениям: 0 < N ≤ 10, 0 < T_i ≤ 100.

Выходные данные
Требуется вывести сначала минимальное время, за которое можно решить все задачи, а затем – номера задач в том порядке, в котором их нужно решать, чтобы уложиться в это время. Все числа разделяются пробелами. Если решений несколько, нужно выдать любое из них.

Примеры

ID 50541. Решение задач

В этой задаче Вася готовится к олимпиаде. Учитель дал ему \(N\) (\(1 \le N \le 100\)) задач для тренировки. Для каждой из этих задач известно, каким умением \(a_i\) нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения \(i\)-й задачи Васино умение увеличивается на число \(b_i\).

Исходное умение Васи равно \(A\). Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

Формат входных данных
Сначала вводятся два целых числа \(N\), \(A\) (\(1 \le N \le 100\), \(0 \le A \le 100\)) — количество задач и исходное умение. Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(1 \le a_i \le 100\), \(1 \le b_i \le 100\)) — соответственно сколько умения нужно для решения \(i\)-й задачи и сколько умения прибавится после её решения.

Формат выходных данных
Выведите одно число — максимальное количество задач, которое Вася может решить.

Примечание
В первом тесте Вася сможет решить все задачи, выбрав, например, порядок 2, 1, 3. Во втором тесте ему необходимо сначала разобраться с 1 и 3 задачами, после чего он осилит 2.

ID 49712. Сортировка строк

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

В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M ( 1 <= N , M <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. В последней строке вводится номер столбца K .
 

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

Примеры

4 5
21 22 23 24 25
26 12 18 29 33
11 37 31 14 39
16 17 18 5 20
1

26 12 18 29 33 
21 22 23 24 25 
16 17 18 5 20 
11 37 31 14 39 

ID 49711. Сортировка по сумме элементов в столбце - 1

Напишите программу, которая переставляет столбцы матрицы так, чтобы при их просмотре слева направо суммы всех значений в каждом столбце образовали невозрастающую последовательность. В случае равенства суммы всех значений в двух столбцах, столбцы должны следовать в том же порядке, что и в исходной матрице.
 
Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. 
 
Формат выходных данных
Программа должна вывести получившуюся матрицу.
 

ID 49709. Сортировка по сумме строк

Напишите программу, которая переставляет строки матрицы так, чтобы при их просмотре сверху вниз суммы всех значений в каждой строке образовали неубывающую последовательность. В случае равенства суммы всех значений в двух строках, строки должны следовать в том же порядке, что и в исходной матрице.
 
Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. 
 
Формат выходных данных
Программа должна вывести получившуюся матрицу.
 

ID 48944. Результаты олимпиады

В олимпиаде участвовало N человек. Каждый получил определенное количество баллов, при этом оказалось,что у всех участников — разное число баллов.

Упорядочите список участников олимпиады в порядке убывания набранных баллов.

ID 47509. Максимус спасает Элстейд

Одарённый невероятной магией и всезнанием Максимус заметил группу из n монстров, приближающихся к городку Элдстейд. Своими волшебными способностями он мгновенно определил расстояние в километрах от города до каждого монстра. Он также заметил, что все монстры двигаются с постоянной скоростью. У Максимуса есть оружие, способное уничтожить одного монстра после полной зарядки. Зарядка занимает ровно одну минуту. Чтобы победить монстра, оружие должно быть полностью заряжено к моменту приближения монстра к городу. Другими словами, невозможно убить монстра достигшего города, даже если в этот момент оружие закончило полную зарядку.
Максимус задается вопросом, сможет ли он сам спасти город от всех монстров или ему нужна помощь.
Напишите программу, которая поможет Максимусу мгновенно определить максимальное количество монстров, которое он сможет уничтожить до того момента, как хотя бы один монстр достигнет города.

Входные данные
Первая строка содержит число n - количество монстров. Во второй строке записано n чисел dist[i] - начальное расстояние в километрах от города для i-го монстра. Третья строка содержит n чисел speed[i] - скорость i-го монстра в километрах в минуту.

Ограничения

• n == длина массива dist == длина массива speed
• 1 <= n <= 105
• 1 <= dist[i], speed[i] <= 105

Примеры

3
1 3 4 
1 1 1

3

4
1 1 2 3
1 1 1 1

1

ID 46032. Сортировка строк матрицы по половинам

Напишите программу, которая сортирует строки двумерного массива целых чисел (nums) по возрастанию суммы элементов первой половины строки. В случае равенства суммы элементов первой половины строки должны идти в порядке возрастания суммы элементов второй половины. При нечетном количестве элементов в строке, средний элемент включается как в первую половину, так и во вторую.

Входные данные
В первой строке записаны два целых числа N и M - количество строк и столбцов матрицы соответственно.  Далее идет N строк, каждая из которых содержит по M чисел, разделенных одним пробелом - элементы массива (nums). 

Ограничения
1 <= N, M <= 10³
-10⁹ <= numsi,j <= 10⁹

Выходные данные
Выведите отсортированный массив.
 
 

Примеры

ID 46031. Сортировка матрицы по сумме строк

Напишите программу, которая сортирует строки двумерного массива целых чисел (nums) по возрастанию суммы элементов строк. В случае равенства суммы двух строк эти строки должны идти в порядке возрастания суммы первого и последнего элементов строки.

Входные данные
В первой строке записаны два целых числа N и M - количество строк и столбцов матрицы соответственно.  Далее идет N строк, каждая из которых содержит по M чисел, разделенных одним пробелом - элементы массива (nums). 

Ограничения
1 <= N, M <= 10³
-10⁹ <= numsi,j <= 10⁹

Выходные данные
Выведите отсортированный массив.
 
 

Примеры

ID 45716. Сортировка главной диагонали

Напишите программу, которая переставляет элементы квадратной матрицы, расположенные на главной диагонали, в порядке возрастания. Остальные элементы матрицы должны остаться на своих местах.
 

В первой строке записано одно число N размер квадратной матрицы ( 1 <= N <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по N натуральных чисел, разделённых пробелами. 
 

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

Примеры

5
1 11 11 5 10 
2 9 2 10 2 
12 9 10 9 15 
6 15 14 1 11 
11 12 4 9 3 

1 11 11 5 10 
2 1 2 10 2 
12 9 3 9 15 
6 15 14 9 11 
11 12 4 9 10

ID 44617. Сортировка строк

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

В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M ( 1 <= N , M <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. В последней строке вводится номер столбца K .
 

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

Примеры

4 5
21 22 23 24 25
26 12 18 29 33
11 37 31 14 39
16 17 18 5 20
1

26 12 18 29 33 
21 22 23 24 25 
16 17 18 5 20 
11 37 31 14 39 

ID 39815. ДВ-2022

В лесополосе осуществляется посадка деревьев. Причем саженцы высаживают рядами на одинаковом расстоянии.
Через какое-то время осуществляется аэросъемка, в результате которой определяется, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд не менее 11 неприжившихся саженцев, при условии, что справа и слева от них саженцы прижились.
В ответе запишите сначала наибольший номер ряда, затем наименьший номер из неприжившихся мест.

Входные данные
В первой строке входного файла находится число N - количество прижившихся саженцев (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места, на котором прижились саженцы.

Выходные данные
Два целых неотрицательных числа: наибольший номер ряда, затем наименьший номер из неприжившихся мест.

Пример входного файла

7
40 30
40 34
50 125
50 129
50 64
50 68
50 70

Ответ для примера (при поиске 3 подряд идущих неприжившихся саженца):
50 65

Файл к заданию

ID 39513. Треугольники - 2

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 10⁵) как различных (X₁,Y₁)…(X_N,Y_N) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

Какова сумма площадей всех возможных пастбищ, которые может сформировать ФД?

Входные данные
Первая строка содержит N.
Каждая из последующих N строк содержит два целых числа Xi и Yi, каждое в интервале −10⁴…10⁴ включительно, описывающих положение столба.

Выходные данные
Поскольку сумма площадей может быть числом не целым и очень большим, выведите остаток от деления удвоенной суммы площадей на 10⁹+7.

Примеры

4
0 0
0 1
1 0
1 2

ID 39498. Концертная площадка

Концертная площадка хранит данные о проданных билетах и свободных местах. Известна информация о том, какие места свободны. Необходимо приобрести 5 билетов на мероприятие, причем так, чтобы все места были в одном ряду и шли подряд. Найдите ряд с наименьшим номером, в котором есть пять соседних свободных мест. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа, в одной строке через пробел: минимальный номер ряда и наибольший номер места из найденных в этом ряду подходящих свободных мест.
 

Входные данные

В первой строке входного файла 26.txt находится число N – количество свободных мест (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер свободного места.

Выходные данные
Два целых неотрицательных числа: Минимальный номер ряда, где нашлись обозначенные в задаче места и максимальный номер подходящего свободного места в этом ряду.
 

Пример входного файла

6
1 1
1 2
1 3
1 4
1 5
1 6

Файл к заданию

ID 39384. Скупщик шоколада

Услышав, что шоколад полезен для мозга и нервной системы, ученик Василий решает купить M плиток шоколада. В городе есть N магазинов, которые продают различный шоколад. В i-м магазине Василий может купить не более Bi плиток шоколада по Ai рублей каждая. Помогите Василию определить, какую минимальную сумму денег ему необходимо накопить, чтобы купить M плиток шоколада?
Гарантируется, что располагая нужной суммой, Василий всегда сможет купить M плиток шоколада.

Входные данные
В первой строке заданы два числа: N и M (1 <= N, M <= 10⁵). Следующие N строк содержат по 2 числа: Ai (1 <= A_i <= 10⁹) и Bi (1 <= В_i <= 10⁵). \(B_1 + B_2 +... + B_N >= M\).

Выходные данные
Выведите минимальную сумму денег, необходимую Василию для покупки M плиток шоколада.
 

Примеры

ID 39245. Шоколад полезный

Услышав, что шоколад полезен для мозга и нервной системы, ученик Василий решает закупить шоколад на весь учебный год. Василий решил закупить шоколада на R рублей. Он обошел в городе все N магазинов, которые продают различный шоколад. Василий сохранил в файл информацию о том, что в i-м магазине он может купить не более Bi плиток шоколада по Ai рублей каждая.
Запасливый ученик хочет потратить как можно больше своих денег (лучше даже сразу все) и купить на них как можно больше шоколада. Помогите Василию понять, сколько плиток шоколада он сможет купить на свои деньги и сколько будет стоить самая дорогая плитка, которую он сможет купить.

Входные данные
Первая строка в файле содержит два числа: N и R. В следующих N строках записана пара чисел: Ai и Вi.

Укажите в ответе два числа через пробел в одной строке: сначала количество плиток шоколада, которые сможет купить Василий на свои деньги, затем стоимость самой дорогой плитки шоколада, которая будет у Василия после покупки.

Файл к заданию