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

314 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Сортировка двумерного массива#45719

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


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

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

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

Программа должна вывести отсортированный двумерный массив.
 

Примеры
№ Входные данные Выходные данные
1 
5 7
13 5 1 8 4 14 5 
5 13 10 9 3 7 7 
3 3 9 6 3 7 5 
10 8 11 2 1 1 13 
1 12 13 15 9 11 4 
 
1 1 1 1 2 3 3 
3 3 4 4 5 5 5 
5 6 7 7 7 8 8 
9 9 9 10 10 11 11 
12 13 13 13 13 14 15
Двумерные массивыКвадратичные сортировки
✓ 112✗ 135600лёгкаяВойти и решать
Сортировка побочной диагонали#45717

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

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

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

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

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

Примеры
№ Входные данные Выходные данные
1 
5
12 4 8 13 13 
1 12 1 4 15 
2 3 5 2 3 
6 5 13 12 14 
14 9 15 4 12 

12 4 8 13 14 
1 12 1 13 15 
2 3 5 2 3 
6 5 13 12 14 
4 9 15 4 12
 
Двумерные массивыКвадратичные сортировки
✓ 119✗ 102600лёгкаяВойти и решать
Сортировка главной диагонали#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
 
Алгоритмы сортировкиДвумерные массивы
✓ 80✗ 47600лёгкаяВойти и решать
Два массива#45674

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i2, у профессора Селезнева i-й член последовательности равен i3. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз. 

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности. 


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

В единственной строке входного файла дано натуральное число i (1 <= i <= 107).


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

Выведите i-е число новой последовательности. 

 
Примеры
№ Входные данные Выходные данные
1 1 1
2 2 4
3 4 9
Вывод формулыРазбор случаевСортировка слиянием
✓ 6✗ 18900средняяВойти и решать
Два массива - 2#45460
Алиса со своим отцом профессором Селезневым записывают на листочке числа. Алиса записала n чисел, профессор Селезнев - m чисел. Алиса и профессор будут рады, если они записали одни и те же числа (без учета кратности). Помогите им определить это, так как им необходимо срочно улетать в очередное космическое путешествие. 
 
Входные данные
В первой строке содержится число n  (1 <= n <= 100000) - количество чисел, записанных Алисой. Во второй строке идет n целых чисел, не превосходящих по модулю 109 – числа Алисы. Третья строка содержит целое число m - количество чисел, записанных профессором Селезневым (1 <= m <= 100000) . В четвертой строке идет m целых чисел, не превосходящих по модулю 109 – числа профессора Селезнева.
 
Выходные данные
Выведите YES, если профессор и Алиса записали одни и те же числа, и слово NO в противном случае.
 
 
Примеры
№ Входные данные Выходные данные
1 3
2 0 7
4
2 0 0 7		 YES
Одномерные массивыСортировка слиянием
✓ 144✗ 959800средняяВойти и решать
Два массива (lite)#45459

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i2, у профессора Селезнева i-й член последовательности равен i3. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз. 

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности. 


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

В единственной строке входного файла дано натуральное число i (1 <= i <= 107).


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

Выведите i-е число новой последовательности. 

 
Примеры
№ Входные данные Выходные данные
1 1 1
2 2 4
3 4 9
Сортировка слиянием
✓ 245✗ 754700средняяВойти и решать
Сортировка слиянием#45458

Отсортируйте данный массив, используя сортировку слиянием.


Входные данные
Первая строка входных данных содержит количество элементов в массиве N, N <= 105. Далее идет N целых чисел, не превосходящих по абсолютной величине 109.


Выходные данные
Выведите эти числа в порядке неубывания.
 
Примеры
№ Входные данные Выходные данные
1 2
3 1		 1 3
Сортировка слиянием
✓ 337✗ 674600лёгкаяВойти и решать
Относительная сортировка#45263

Даны два массива arr1 и arr2. Элементы массива arr2 различны, и при этом все элементы arr2 содержатся в arr1.

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



Входные данные
Первая строка входных данных содержит целое число n - количество элементов в массиве arr1, вторая строка содержит n целых чисел - элементы массива arr1. Третья строка содержит целое число m - количество элементов в массиве arr2, четвертая строка содержит m целых чисел - элементы массива arr2.

Ограничения на входные данные
  • 1 <= n, m <= 106
  • 0 <= arr1[i], arr2[i] <= 1000
  • Все элементы массива arr2 различны.
  • Каждый элемент массива arr2[i] содержится в массиве arr1.


Выходные данные
Выведите, отсортированный по условию задачи, массив arr1.
 
 
Примеры
№ Входные данные Выходные данные
1 11
2 3 1 3 2 4 6 7 9 2 19
6
2 1 4 3 9 6		 2 2 2 1 4 3 3 9 6 7 19
2 6
28 6 22 8 44 17
4
22 28 8 6		 22 28 8 6 17 44
Сортировка подсчетом
✓ 99✗ 267700средняяВойти и решать
Наибольшее произведение трех чисел - поиск сортировкой#45242

Дано целое число  N<=103 и N целых чисел. необходимо найти три числа, произведение которых максимально.

Если таких троек чисел несколько, выведите любую из них. 

Входные данные
В первой строке задано целое число 3 <= N <= 103 - количество элементов в списке.
Во второй строке заданы N целых  элементов списка, не превосходящих по модулю 30000.

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

Примеры
№ Входные данные Выходные данные
1 9
3 5 1 7 9 0 9 -3 10		 10 9 9
2 3
-5 -30000 -12		 -5 -12 -30000
Квадратичные сортировки
✓ 33✗ 186800средняяВойти и решать
Сортировка массива (сложная) - 1#45241
Дан массив целых чисел. Отсортируйте массив по невозрастанию суммы цифр каждого числа. При равенстве суммы цифр двух чисел, числа должны следовать в порядке убывания.

Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел ai - элементы массива (1 <= n <= 103, 1 <= ai <= 104).

Формат выходных данных
Выведите результирующий массив.
 
 
Примеры
№ Входные данные Выходные данные
1 4
1 43 12 10		 43 12 10 1
Квадратичные сортировки
✓ 100✗ 353500лёгкаяВойти и решать
Сортировка по квадратам чисел#45240
Дан массив целых чисел. Верните отсортированный по неубыванию массив квадратов исходных чисел.

Входные данные
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел ai - элементы массива (1 <= n <= 103, -104 <= ai <= 104).

Выходные данные
Выведите результирующий массив.
 
 
Примеры
№ Входные данные Выходные данные
1 5
-1 -4 3 0 10		 0 1 9 16 100
2 3
3 -1 1		 1 1 9
Квадратичные сортировки
✓ 118✗ 321400лёгкаяВойти и решать
Сортировка строк#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
Алгоритмы сортировкиДвумерные массивы
✓ 220✗ 368500лёгкаяВойти и решать
2022#44582

Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных пар индексов, у которых первый индекс в паре меньше второго, таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует пар 1 <= i,j <= n, для которых выполняется ai+aj=2022.

Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.



Входные данные
В первой строке содержится одно целое число n (1 <= n <= 100000) - количество элементов массива. Во второй строке заданы n целых чисел a1, a2, ..., an (0 <= ai <= 2022) - элементы массива Эвелины.

Выходные данные
Выведите одно число - количество подходящих пар.

Примечание

В первом примере не существует пар с суммой 2022.

Во втором подходят пары (1, 2), (3, 4).

В третьем примере подходят все пары (2, 4), (2, 5), (3, 4), (3, 5). 

 
Примеры
№ Входные данные Выходные данные
1 
2
1 2022
 
0
2 
4
1000 1022 1001 1021
 
2
3 
5
700 1 1 2021 2021
 
4
Алгоритмы обработкиБинарный поиск в массивеИспользование сортировки
✓ 5✗ 22900средняяВойти и решать
Мишины кубики#43718
У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.


Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные
1 6 4 2
aaaaaa
bbbb		 aabaabaa
"Два указателя"Жадный алгоритмЗадача на реализациюИспользование сортировкиПростые задачи на перебор
✓ 28✗ 1141 100средняяВойти и решать
Радостная фигура#43714
Маленький Миша любит играть счетными палочками. Счетные палочки он берет у своей сестры первоклассницы. Так как он редко возвращает их назад, маме приходится часто покупать новые палочки. Поэтому не все палочки у Миши одинаковые, но все палочки имеют целочисленную длину.
Сегодня Миша строит из палочек следующую фигуру. Он начал из угла комнаты. Мы с вами обозначим, условно, этот угол координатой (0, 0). Дальше Миша выкладывает палочку параллельно одной из двух стен, исходящей из данного угла. Будем считать, что стены ровные и образуют друг с другом в точке (0, 0) угол 90 градусов. При этом, Миша никогда не выкладывает две подряд палочки одновременно параллельно одной и той же стене (другими словами, он всегда чередует направление палочек).
Миша, хоть и маленький и не знает геометрии, но все же всегда радуется, если конец его фигуры находится как можно дальше от стартового угла. Помогите Мише выложить фигуру, которая его обрадует. Любые две палочки, которые выкладывает Миша всегда имеют минимум одну точку касания или пересечения.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит целое число n (1<= n <= 100000) — количество палочек, которые есть у Миши. Вторая строка содержит n целых чисел a1,...,an (1 <= ai <= 10000) - длины Мишиных палочек.

Выходные данные
Выведите одно целое число — квадрат максимального расстояния от угла с координатой (0,0) до конечной точки фигуры, которую построил Миша.
 
 
Примеры
№ Входные данные Выходные данные
1 3
1 2 3		 26
2 4
1 1 2 2		 20
Жадный алгоритмИспользование сортировки
✓ 55✗ 100700средняяВойти и решать
Ресторан#39963
Ресторан получил n заказов на проведение банкета. Каждый заказ характеризуется двумя величинами: моментом начала банкета li и моментом конца ri (li ≤ ri).

Руководство ресторана может либо принять заказ, либо отвергнуть его. Какое наибольшее количество заказов может быть принято?

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

Входные данные:
В первой строке находится целое число n (1 ≤ n ≤ 200000) — количество заказов. В каждой из следующих n строк находится пара целых чисел li, ri (0 ≤ li ≤ ri ≤ 109).

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

Примеры:
 
Входные данные Выходные данные
2
7 11
4 7		 1
5
1 2
2 3
3 4
4 5
5 6		 3
6
4 8
1 5
4 7
2 5
1 3
6 8		 2
Бинарный поиск в массивеДинамическое программированиеИспользование сортировки
✓ 88✗ 25600лёгкаяВойти и решать
ДВ-2022#39815

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

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

Алгоритмы сортировкиЕГЭ_информатикаЕГЭ-26. Обработка массива целых чисел. Сортировка
1 300труднаяВойти и решать
Треугольники - 2#39513
Фермер Джон хочет создать треугольное пастбище для своих коров.
Всего имеется 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.
Алгоритмы сортировкиВывод формулы
✓ 1✗ 11 200средняяВойти и решать
Концертная площадка#39498

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

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

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

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

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

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



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

Алгоритмы сортировкиЕГЭ_информатикаЕГЭ-26. Обработка массива целых чисел. Сортировка
1 400труднаяВойти и решать
Социальное дистанцирование II#39389
Фермер Джон продолжает бороться за здоровье своих коров.
Имеется N cows (1≤N≤1000) коров, некоторые из которых больны. Коровы выстроены в ряд (на числовой прямой), корова i стоит на позиции xi. ФД знает что если другая корова находится в радиусе R от больной, то она тоже заболевает. А потом заболевают коровы, которые находятся в радиусе R от этой и т.д.

К несчастью, ФД не знает точное значение R. Однако он знает, какие из его коров больны. По этим данным определите минимальное количество изначально инфицированных болезнью коров.

Входные данные
Первая строка ввода содержит N. Каждая из последующих N строк описывает одну корову двумя числами x и s, где x - позиция коровы, а s равно 0 для здоровой коровы и 1 для больной. Как минимум 1 корова больна. И все коровы, которые могли стать больными от распространения болезни уже больны.
Выходные данные
Определите минимальное количество коров, которые изначально были больны, перед любым распространением болезни.
Примеры
№ Входные данные Выходные данные
1 6
7 1
1 1
15 1
3 1
10 0
6 1		 3
Сканирующая прямая
✓ 1✗ 4—Войти и решать
Поделиться
Класснуть