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


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38128. Acowdemia
Темы: Бинарный поиск по ответу    Алгоритмы сортировки   

Беси опубликовала N статей (1 <= N <= 105). i-ая статья процитирована ci раз (0 <= ci <= 105).
h-индекс это наибольшее число h такое, что имеется не менее h статей, каждая из которых цитируется не менее чем h раз. Например, есть 4 статьи с количествами цитат (1,100,2,3), тогда h-индекс равен 2, а при количествах цитат (1,100,3,3) h-индекс равен 3.

Чтобы повысить свой h-индекс, Беси планирует написать K обзорных статей (0 <= K <= 105), каждая из которых цитирует несколько ее прошлых статей. Беси имеет право цитировать не более L статей в каждом обзоре (0 <= L <= 105). Конечно, никакая статья не может цитироваться более одного раза в одном обзоре (однако статья может цитироваться в нескольких обзорах).

Помогите Беси определить максимальный h-индекс, который она может достичь после написания этих обзорных статей. Беси не может цитировать обзор в любом из её обзоров.

Входные данные
Первая строка содержит N, K, L. Вторая строка содержит N разделённых пробелом целых чисел c1,...,cN.

Выходные данные
Максимальный h-индекс.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 4 4 1
1 100 1 1		 3 В этом примере Беси может написать 4 обзорные статьи, в каждой из которых можно процитировать не более 1 статьи. Если процитировать первую и третью статьи по 2 раза, её h-индекс станет 3.
2 4 1 4
1 100 1 1		 2 В этом втором примере Беси может написать не более одной статьи. Если Беси процитирует любую из её 1,2 или 4 статью хоть раз, её h-индекс станет 2.

ID 38335. Рассадка участников
Темы: Алгоритмы сортировки    Задачи на моделирование   

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

Входные данные
Программа получает на вход целое положительное число участников олимпиады N1000. Далее в N строках записаны номера школ, в которых учатся участники олимпиады. Номера школ — целые числа от 1 до 3000.

Выходные данные
Программа должна вывести N чисел — номера школ участников олимпиады в том порядке, в котором их необходимо рассадить в компьютерном классе. Выведенная последовательность номеров школ должна быть перестановкой данных номеров школ. В выведенном ответе не должно быть двух одинаковых номеров школ, идущих подряд.

Если задача не имеет решения, необходимо вывести одно число 0.

Числа можно выводить как в отдельных строках, так и в одной строке через пробел. Если есть несколько вариантов рассадки, то необходимо вывести любой из них (но только один).

Примеры
№ Входные данные Выходные данные
1 4
1005
1005
5
2005		 1005 5 1005 2005 
2 4
1005
1005
2005
1005		 0

ID 38473. Взвешивание камней
Темы: Алгоритмы сортировки    Дерево отрезков, RSQ, RMQ    Жадный алгоритм   

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

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

Входные данные
Первая строка содержит целое число N (1  N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк -  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры
№ Входные данные Выходные данные
1 5
1 2
3 1
2 1
4 2
5 1		 
<
>
>
?
>

ID 38481. Ироха любит строки
Темы: Строки    Алгоритмы сортировки   

У Ирохи есть последовательность из N строк s1, s2, .., sN. Каждая строка длиной L. Ироха хочет объединить все строки, чтобы получить очень длинную строку. Среди всех строк, которые она может получить таким образом, найдите лексикографически наименьшую. 

Будем считать, что строка s = s1s2...sn лексикографически меньше строки t = t1t2...tm, если выполняется одно из следующих условий:
- существует индекс i (\(1<=i<=min(n,m)\)), такой что \(s_j =t_j \), для всех индексов j (\(1<=j<=i\)), и \(s_i <t_i \);
-  \(s_i=t_j\) для всех i (\(1<=i<=min(n,m)\)), и \(n<m\).


Входные данные
В первой строке задаются числа N и L. Далее идут строки s1, s2, .., sN, каждая в отдельной строке.

Выходные данные
Выведите лексикографически наименьшую строку, которую может создать Ироха.
 

 

Примеры
№ Входные данные Выходные данные
1 3 3
dxx
axx
cxx		 axxcxxdxx

 
ID 38715. Печаль Громозеки
Темы: Одномерные массивы    Использование сортировки    Алгоритмы сортировки   

Громозека имеет последовательность целых чисел A длины N. Он свободно выбирает целое число b. Здесь ему станет грустно, если Ai и b+i находятся далеко друг от друга. Точнее, печаль Громозеки рассчитывается следующим образом:
\(abs(A_1-(b+1))+abs(A_2-(b+2))+...+abs(A_N-(b+N))\).
Здесь \(abs(x) \)- это функция, которая возвращает абсолютное значение x. Найдите минимально возможную печаль Громозеки.

Входные данные
В первой строке записано целое число N  (\(1<=N<=2 \cdot 10^5\)). Во второй строке записано N целых чисел Ai (\(1<=A_i<=10^9\)).

Выходные данные
Выведите на экран минимально возможную печаль Громозеки.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 5
2 2 3 5 5		 2 Если мы выберем b = 0, печаль Громозеки будет \(\) 
abs (2- (0 + 1)) + abs (2-(0 + 2))+ abs (3-(0 + 3)) + abs (5- (0 + 4)) + abs(5-(0 + 5)) = 2.
Любой другой выбор b не делает печаль Громозеки меньше 2, поэтому ответ - 2.
2 9
1 2 3 4 5 6 7 8 9		 0  
3 6
6 5 4 3 2 1		 18  
4 7
1 1 1 1 2 3 4		 6  

ID 38923. До Нового года - 2!
Темы: Алгоритмы сортировки   

В каком-то другом мире сегодня 30 декабря. В саду деда Коковани посажено N деревьев. Высота i-го дерева (1  <= i <= N) равна hi метров. Он решает выбрать из этих деревьев K деревьев и украсить их гирляндой. Чтобы декорации были красивее, высота украшенных деревьев должна быть как можно ближе друг к другу. Более конкретно, пусть высота самого высокого украшенного дерева будет hmax метров, а высота самого низкого декорированного дерева будет hmin метров. Чем меньше значение hmax-hmin, тем лучше. Определите минимально возможное значение hmax-hmin?

Входные данные
В первой строке записаны через пробел два числа N и K (2 <= N, K <= 105). В следующих N строках записаны целые числа hi (1 <= hi <= 109), по одному в строке.

Выходные данные
Выведите на экран ответ на задачу.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 5 3
10
15
11
14
12		 2 Если украсить первое, третье и пятое деревья, hmax=12, hmin=10, hmax-hmin=2. 
2 5 3
5
7
5
7
7		 0  

ID 38994. Хранение данных и сортировка
Темы: ЕГЭ    Алгоритмы сортировки   

В файле записаны целые положительные числа. В первой строке файла записано число N - количество чисел. В следующих N строках записаны сами числа. В ответе укажите в столбик 10 самых больших трехзначных чисел.

Файл к заданию
ID 39054. Посетить все
Темы: Алгоритмы сортировки   

Громозека играет в одиночную игру, используя числовую прямую и N фишек. Каждая из фишек расположена в некоторой целочисленной координате. Заметьте, несколько фишек могут быть размещены в одной и той же координате.
Цель игры: посетить фишками все M координат X1, X2, ..., XM, повторив следующий ход.
Ход: выберите фишку с координатой X. Поместите эту фишку в координату X+1 или X-1.
Обратите внимание, что координаты, где мы первоначально размещены фишки, уже считаются посещенными.
Найдите минимальное количество ходов, необходимое для достижения цели.

Входные данные
В первой строке программа получает на вход два целых числа: N и M (1 <= N, M <= 105). Во второй строке записаны M целых чисел X1, X2, ..., XM (-105 <= Xi <= 105). Все числа Xi различны.

Выходные данные
Выведите на экран ответ на задачу.
 

Примеры
№ Входные данные Выходные данные Пояснение
1 2 5
10 12 1 2 14		 5 Цель может быть достигнута за пять ходов следующим образом, и это минимально необходимое количество ходов.
Сначала поместите две фишки в координаты 1 и 10.
Переместите фишку с координатой 1 на 2.
Переместите фишку с координатой 10 на 11.
Переместите фишку с координатами 11 на 12.
Переместите фишку с координатами 12 на 13.
Переместите фишку с координатами 13 на 14.
2 3 7
-10 -3 0 9 -100 2 17		 19  
3 100 1
-100000		 0  

ID 39245. Шоколад полезный
Темы: Алгоритмы сортировки    ЕГЭ   

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

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

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

Файл к заданию
 
ID 39384. Скупщик шоколада
Темы: Алгоритмы сортировки    Использование сортировки   

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

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

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

Примеры
№ Входные данные Выходные данные
1 2 5
4 9
2 4		 12
2 4 30
6 18
2 5
3 10
7 9		 130
3 1 100000
1000000000 100000		 100000000000000

ID 39513. Треугольники - 2
Темы: Алгоритмы сортировки    Вывод формулы   

Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется N столбов забора (3 ≤ N ≤ 105) как различных (X1,Y1)…(XN,YN) точек на карте фермы. Он может выбрать три из них чтобы сформировать вершины треугольного пастбища, но так чтобы одна из сторон была параллельна оси x, а другая - параллельно оси y.

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

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

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

Примеры
№ Входные данные Выходные данные Пояснение
1 
4
0 0
0 1
1 0
1 2
 3 Точки (0,0), (1,0), (1,2) образуют треугольник с площадью 1.
Точки (0,0), (1,0), (0,1) образуют треугольник с площадью 0.5.
Поэтому ответ 2⋅(1+0.5)=3.

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 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 44617. Сортировка строк
Темы: Двумерные массивы    Алгоритмы сортировки   

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

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

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

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

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

Примеры
№ Входные данные Выходные данные
1 
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 45716. Сортировка главной диагонали
Темы: Двумерные массивы    Алгоритмы сортировки   

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

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

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

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

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

Примеры
№ Входные данные Выходные данные
1 
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 46031. Сортировка матрицы по сумме строк
Темы: Алгоритмы сортировки   

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

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

Ограничения
1 <= N, M <= 103
-109 <= numsi,j <= 109

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

Примеры
№ Входные данные Выходные данные
1 3 3
4 0 2
1 3 2
1 1 2		 1 1 2
1 3 2
4 0 2
 

ID 46032. Сортировка строк матрицы по половинам
Темы: Алгоритмы сортировки   

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

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

Ограничения
1 <= N, M <= 103
-109 <= numsi,j <= 109

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

Примеры
№ Входные данные Выходные данные
1 3 5
4 0 2 1 3
1 3 2 0 0
1 1 2 1 1		 1 1 2 1 1
1 3 2 0 0
4 0 2 1 3

ID 47509. Максимус спасает Элстейд
Темы: Жадный алгоритм    Массивы    Алгоритмы сортировки   

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

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

Ограничения

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


Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 
3
1 3 4 
1 1 1
 
3
 Вначале расстояния между монстрами равны [1,3,4]. Максимус уничтожает первого монстра.
Через минуту расстояния между монстрами становятся [X,2,3]. Максимус уничтожает второго монстра.
Через минуту расстояния между монстрами будут [X,X,2]. Максимус уничтожает третьего монстра.
Все три монстра могут быть уничтожены.
 
2 
4
1 1 2 3
1 1 1 1
 
1
 Вначале расстояния между монстрами равны [1,1,2,3]. Максимус уничтожает первого монстра.
Через минуту расстояния между монстрами становятся равными [X,0,1,2], и второй монстр достиг города.
Максимус может уничтожить только 1 монстра.

 
ID 48944. Результаты олимпиады
Темы: Алгоритмы сортировки   

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

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


Формат входных данных
Программа получает на вход число участников олимпиады N. Далее идет N строк, в каждой строке записана фамилия участника, затем, через пробел, набранное им количество баллов.

Формат входных данных
Выведите список участников (только фамилии) в порядке убывания набранных баллов.
ID 29546. Fenced In
Темы: Алгоритмы сортировки    Жадный алгоритм   

Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.
Поле представляет собой прямоугольник с угловыми вершинами в точках (0,0) and (A,B). ФД построил n вертикальных изгородей (0≤n≤25,000) в различных позициях a1…an (0<ai<A); каждая изгородь проходит от точки (ai,0) до точки (ai,B). Он также построил m горизонтальных изгородей (0≤m≤25,000) в в различных позициях b1…bm (0<bi<B); каждая изгородь, проходит из (0,bi) в (A,bi). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n+1)(m+1) регионов.
 
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
 
Например, ФД мог построить изгороди так:
 
+---+--+
|      |   |
+---+--+
|     |    |  
|     |    |
+---+--+
и открыть их так:
 
+---+--+
|          |  
+---+  +  
|          |  
|          |
+---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит числа A, B, n, and m (1≤A,B≤1,000,000,000). Следующие n строк содержат a1…an. Следующие m строк содержат b1…bm.

ФОРМАТ ВЫВОДА:
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )
 
Ввод Вывод
15 15 5 2
2
5
10
6
4
11
3
 44

ID 30717. Перетягивание каната
Темы: Алгоритмы сортировки    Задача на реализацию   

В 2086 году в программу зимней олимпиады решено было добавить соревнования по перетягиванию каната на льду. Для проведения финала соревнования организаторы нашли n кусков каната. Для повышения зрелищности соревнования решено было сделать связать некоторые из этих кусков в один как можно более длинный канат.

Когда начались работы по связыванию, выяснилось, что на узел, связывающий два куска каната между собой, уходит по d сантиметров каната с каждого из связываемых концов. Также, оказалось, что связывать так, что получающиеся узлы находятся близко друг к другу, невозможно: расстояние между соседними узлами должно быть хотя бы d сантиметров. Например, если d = 10, то после связывания кусков каната длиной 25 и 50 сантиметров, получается канат длиной 55 сантиметров, в 15 сантиметрах от одного из краев которого находится узел.

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

Формат входных данных
В первой строке заданы числа n (1 ≤ n ≤ 100 000) и d (1 ≤ d ≤ 1000) — количество кусков каната и длина каната, уходящая на завязывание узла. Во второй строке заданы n чисел ai (1 ≤ ai ≤ 1000) — длины имеющихся кусков каната.

Формат выходных данных
Выведите единственное число — максимальную длину каната, которую можно получить.
 

Ввод Вывод
2 10
25 50		 55
5 2
4 5 6 7 8		 14

ID 49712. Сортировка строк
Темы: Двумерные массивы    Алгоритмы сортировки   

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

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

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

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

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

Примеры
№ Входные данные Выходные данные
1 
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 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 54353. Антон решает задачи
Темы: Алгоритмы сортировки   

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

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

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

Примеры
№ Входные данные Выходные данные
1 1
23		 23
1
2 2
52 37		 126
1 2

ID 55120. Площадь прямоугольников
Темы: Алгоритмы сортировки   

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

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

Выходные данные
Вывести одно число - площадь фигуры.
ID 55450. Экономический кризис
Темы: Алгоритмы сортировки   

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

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

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

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

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

Входные данные
Первая строка содержит целое число N – количество пакетов помощи (1 ≤ N ≤ 100 000). Вторая строка содержит N целых чисел: a1, a2, . . . , an (1 ≤ ai ≤ 106).

Вторая строка содержит целое число N – количество запросов (1 ≤ M ≤ 100 000). Вторая строка содержит N целых чисел: b1, b2, . . . , bn (1 ≤ bi ≤ 106).

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

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

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