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


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


Условие задачи Прогресс
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 целых чисел a- элементы массива (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 целых чисел a- элементы массива (1 <= n <= 1031 <= 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