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

Задачи из рубрикатора

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

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