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


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


Условие задачи Прогресс
ID 29474. Пузырьковая сортировка
Темы: Квадратичные сортировки   

Требуется отсортировать массив по неубыванию методом "пузырька".
 
Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).
 
Выходные данные
Вывести получившийся массив.
 
Примеры
№ Входные данные Выходные данные
1
5
5 4 3 2 1
 1 2 3 4 5

ID 23590. Использование сортировки
Темы: Квадратичные сортировки   

Известны значения роста всех учащихся класса. Определите рост учащегося, который при построении учащихся по росту, в порядке возрастания, занимал бы 10-е место при счете от самого высокого ученика.

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

Входные данные
В первой строке вводится натуральное число N - количество учащихся класса (11 <= N <= 35).
Во второй строке вводятся N целых чисел - рост учащихся.

Выходные данные
Необходимо вывести на экран значение роста учащегося, который бы занимал 10-е место по росту в порядке убывания, при счете от самого высого ученика.
 
Пример
№ Входные данные Выходные данные
1 12
148 144 154 145 155 130 157 136 152 130 177 166		 136

ID 22009. Результаты олимпиады
Темы: Квадратичные сортировки   

N участников олимпиады получили уникальные номера от 1 до N. В результате решения задач на олимпиаде, каждый участник получил некоторое количество баллов (целое число от 0 до 600).  Известно, кто сколько баллов набрал. Требуется перечислить участников олимпиады в порядке невозрастания набранных ими баллов.
 
Входные данные
Вводится сначала число N (\(1<=N<=100\)) - количество участников олимпиады. Далее вводится N чисел - количества набранных участниками баллов (1-е число - это баллы, набранные участником номер 1, 2-е - участником номер 2 и т.д.).
 
Выходные данные
Выведите N чисел - номера участников в порядке невозрастания набранных ими баллов (участники, набравшие одинаковое количество баллов, могут быть выведены в любом порядке).
 
Пример
№ Входные данные Выходные данные
1
5
100 312 0 312 500
 5 2 4 1 3

ID 29476. Миссия Серенити
Темы: Квадратичные сортировки   

Экипаж Серенити межпланетного корабля класса Светлячок занимается доставкой грузов на различные планеты звездной системы. На корабле имеется секретный грузовой отсек, состоящий из N × M ячеек. Каждая ячейка грузового отсека имеет предельный объем, который она может вместить. Невозможно в ячейку вместить груз объемом больше, чем предельный объем ячейки. В одну ячейку можно поместить только ровно один груз. 
 
 Капитан Серенити Малькольм Рейнольдс продумывает размещение грузов по ячейкам. Помогите ему определить, какое максимальное количество грузов удастся доставить капитану.
 
Входные данные
В первой строке даны числа N и M (\(1 \leq N, M \leq 40\)). В каждой из последующих N строк содержится по M чисел, обозначающих предельный объем соответствующей ячейки. В (N+2)-ой строке находится число K (\(1 \leq K \leq 2000\)) – количество грузов. В (N+3)-ей строке содержатся K чисел, i-ое из которых – объем i-ого груза. Все объемы – натуральные числа, не превышающие 109.

Выходные данные
Требуется вывести одно число – максимально возможное количество грузов, которое удастся доставить.
 
Пример
№ Входные данные Выходные данные
1
3 2
5 10
7 5
5 5
6
9 5 3 5 12 10
 4

ID 33474. Обувной магазин
Темы: Квадратичные сортировки   

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

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

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

Примеры
№ Входные данные Выходные данные
1 60
2
60 63		 2
2 26 
5
30 35 40 41 42		 3

ID 38115. Доставка контейнеров
Темы: Квадратичные сортировки   

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

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

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

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

ID 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

ID 45241. Сортировка по сумме цифр числа
Темы: Квадратичные сортировки    Двумерные массивы   

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

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

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

Примеры
№ Входные данные Выходные данные
1 4
1 43 12 10		 43 12 10 1

ID 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

ID 33207. Сортировка по цифрам числа 2
Темы: Одномерные массивы    Квадратичные сортировки   

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

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

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

9
639 265 915 993 436 202 573 906 490 

Выходные данные
202 265 436 490 573 639 906 915 993
ID 33205. Пятый самый легкий
Темы: Одномерные массивы    Квадратичные сортировки   

Известны массы в килограммах N предметов (6<=N<=100). Определить массу предмета, являющегося "пятым из самых легких предметов".

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

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

6
170 150 162 148 175 181 

Выходные данные
175
ID 33203. Средние в шеренге
Темы: Одномерные массивы    Квадратичные сортировки   

Известен рост N человек (N-четное, 2<=N<=100). Определить рост тех двоих людей, которые бы оказались в середине шеренги в случае построения ее по ранжиру (по убыванию роста).

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

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

6
170 150 162 148 175 181 

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

 
ID 33202. Использование сортировки 2
Темы: Одномерные массивы    Квадратичные сортировки   

В каждом из двух классов учатся по N человек (10<=N<=30). Известны средний балл каждого ученика каждого класса, подсчитанные по ряду предметов (все значения целые). Определить, в каком классе у "третьего из самых успевающих учеников" средняя оценка больше. Вывести цифру "1" - для первого класса, "2" - для второго
Если оценки равны, вывести эту оценку

Нельзя использовать встроенную сортировку
 
Примеры:
входные данные
10
3 4 4 3 3 3 2 5 4 5 
4 5 2 2 4 4 5 2 3 5 
выходные данные
2
ID 33206. Сортировка по цифрам числа 1
Темы: Одномерные массивы    Квадратичные сортировки   

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

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

Примеры
№ Входные данные Выходные данные
1
6
75 15 62 48 70 81 
 15 48 62 75 70 81 
 
ID 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
 
ID 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