Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Сортировка по максимальному элементу в строке - 2#49370

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

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

Формат выходных данных
Программа должна вывести получившуюся матрицу.

Квадратичные сортировки

✓ 26✗ 71700средняяВойти и решать

Сортировка по сумме строк - 2#49369

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

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

Формат выходных данных
Программа должна вывести получившуюся матрицу.

Квадратичные сортировки

✓ 23✗ 17400лёгкаяВойти и решать

Сортировка по сумме строк#49368

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

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

Формат выходных данных
Программа должна вывести получившуюся матрицу.

Квадратичные сортировки

✓ 12✗ 10600лёгкаяВойти и решать

Сортировка выбором#49138

Требуется отсортировать массив по неубыванию методом "выбора".

Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

Выходные данные
Вывести получившийся массив.

Пример

№	Входные данные	Выходные данные
1	5 5 4 3 2 1	1 2 3 4 5

Сортировка вставками

✓ 795✗ 830300лёгкаяВойти и решать

Средние по росту#49039

Формат входных данных
В первой строке записано натуральное число n (n < 100, n - четное). Вторая строка содержит n положительных целых чисел m_i - рост i-го учащегося (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵).

Формат выходных данных
Напечатайте среднее арифметическое роста тех двоих людей, которые бы оказались в середине шеренги в случае построения ее по росту, начиная с самого низкого. Ваш ответ будет проверяться с точностью 10^-6.

Квадратичные сортировки

✓ 201✗ 244400лёгкаяВойти и решать

Самый легкий#49037

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел m_i - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵). В третьей строке записано натуральное число k (k ≤ n).

Формат выходных данных
Напечатайте массу предмета, являющегося "k-м самым легким предметом".

Квадратичные сортировки

✓ 125✗ 286400лёгкаяВойти и решать

K-й по счету#49035

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел v_i - значения максимальной скорости i-го автомобиля (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵). В третьей строке записано натуральное число k (k ≤ n).

Формат выходных данных
Напечатайте максимальную скорость автомобиля, являющегося "k-м самым быстрым автомобилем".

Квадратичные сортировки

✓ 106✗ 136400лёгкаяВойти и решать

Обувной магазин#48947

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

Формат входных данных
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), затем количество пар обуви в магазине и размер каждой пары. Размер — натуральное число, не превосходящее 100, количество пар обуви в магазине не превосходит 1000.

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

Квадратичные сортировки

✓ 0✗ 31 200средняяВойти и решать

Сортировка двумерного массива#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лёгкаяВойти и решать

Наибольшее произведение трех чисел - поиск сортировкой#45242

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

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

Входные данные
В первой строке задано целое число 3 <= N <= 10³ - количество элементов в списке.
Во второй строке заданы 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 целых чисел a_i- элементы массива (1 <= n <= 10³, 1 <= a_i <= 10⁴).

Формат выходных данных
Выведите результирующий массив.

Примеры

№	Входные данные	Выходные данные
1	4 1 43 12 10	43 12 10 1

Квадратичные сортировки

✓ 100✗ 353500лёгкаяВойти и решать

Сортировка по квадратам чисел#45240

Дан массив целых чисел. Верните отсортированный по неубыванию массив квадратов исходных чисел.

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

Выходные данные
Выведите результирующий массив.

Примеры

№	Входные данные	Выходные данные
1	5 -1 -4 3 0 10	0 1 9 16 100
2	3 3 -1 1	1 1 9

Квадратичные сортировки

✓ 118✗ 321400лёгкаяВойти и решать

"Сортировка" с конфеткой#38576

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

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

Примеры

№	Входные данные	Выходные данные
1	4 1 4 2 3 2 4 3 1 2	1 2 4 3

Задачи на моделирование Сортировка "пузырьком"

✓ 36✗ 5051 100средняяВойти и решать

Доставка контейнеров#38115

Малькольма Рейнольдса попросили доставить пустые контейнеры на самую отдаленную планету звездной системы. На корабле осталась только одна свободная ячейка объемом Х, в которую можно положить контейнеры. Капитан решил сложить несколько контейнеров друг в друга. Все контейнеры имеют подобные размеры. Контейнер с меньшим объемом свободно помещается в контейнер с объемом на 3 условных единицы больше. Определите, какое наибольшее количество контейнеров может доставить капитан Рейнольдс?

Входные данные
В первой строке вводится натуральное число Х - объем свободной ячейки (груз большего объема в ячейку не поместится). Во второй строке - количество контейнеров (целое неотрицательное число). В третьей строке - объем каждого контейнера. Все объемы - натуральные числа, не превосходящее 100, количество контейнеров не превосходит 1000.

Выходные данные
Выведите одно число — максимальное количество контейнеров, которое сможет доставить Малькольм Рейнольдс.

Примеры

№	Входные данные	Выходные данные
1	60 2 60 63	1
2	26 5 26 24 22 21 18	3

Квадратичные сортировки

✓ 199✗ 2 127900средняяВойти и решать

Сортировка вставками#37170

Требуется отсортировать массив по неубыванию методом "вставок".

Пример

№	Входные данные	Выходные данные
1	5 5 4 3 2 1	1 2 3 4 5

Сортировка вставками

✓ 2 316✗ 2 086300лёгкаяВойти и решать

Ожерелье#34881

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.

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

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

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

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

Выходные данные
Ваша программа должна вывести описание процесса упорядочения.

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

Количество выводимых строк не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается, программа должна вывести одно число –1

Ввод	Вывод
4 3 1 2 4	4 2 4 1 0

Задачи на моделирование Сортировка "пузырьком"

✓ 28✗ 90800средняяВойти и решать

Сортировка по цифрам числа 2#33207

Дано N трехзначных чисел (1<=N<=1000). Необходимо вывести их в порядке возрастания.

Нельзя использовать встроенную сортировку

Пример
Входные данные

639 265 915 993 436 202 573 906 490

Выходные данные
202 265 436 490 573 639 906 915 993

Квадратичные сортировки Одномерные массивы

✓ 49✗ 144600лёгкаяВойти и решать

Сортировка по цифрам числа 1#33206

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

Формат входных данных
В первой строке записано натуральное число N (1<=N<=1000). Вторая строка содержит n двузначных положительных чисел nums_i (1 ≤ i ≤ n, 10 ≤ nums_i ≤ 99).

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

Квадратичные сортировки Одномерные массивы

✓ 64✗ 88600лёгкаяВойти и решать

Пятый самый легкий#33205

Формат входных данных
В первой строке записано натуральное число n (n < 100). Вторая строка содержит n положительных целых чисел m_i - вес i-го предмета (1 ≤ i ≤ n, 1 ≤ ai ≤ 10⁵).

Формат выходных данных
Напечатайте массу предмета, являющегося "пятым самым легким предметом".

Квадратичные сортировки Одномерные массивы

✓ 167✗ 324400лёгкаяВойти и решать