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


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


Условие задачи Прогресс
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