Сортировки

E: Сортировка по невозрастанию

Дан список целых чисел. Выведите все элементы этого списка в порядке невозрастания значений. Выведите новый список на экран.

1 4 2 3 4

4 4 3 2 1

F: Сортировка по неубыванию

Дан список целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный список на экран.

1 4 2 3 4

1 2 3 4 4

ZB: Слияние

Даны два списка целых чисел. Каждый из них упорядочен в порядке неубывания чисел.

Объедините эти два списка в один так, чтобы числа в нем шли также в порядке неубывания.

Гарантируется, что числа исходных списков по модулю не превосходят миллиона.

1 3 3 3 4 5 8 8
2 3 5 6 11

1 2 3 3 3 3 4 5 5 6 8 8 11

ZC: Сортировка слиянием

Дан список целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный список на экран.

Решите эту задачу при помощи алгоритма сортировки слиянием.

1 4 2 3 4

1 2 3 4 4

O: Сортировка подсчетом

Дан список из N (N≤10⁵) элементов, которые принимают целые значения от 0 до 100.

Отсортируйте этот список в порядке неубывания элементов. Выведите полученный список.

1 3 2 3 1

1 1 2 3 3

J: Результаты олимпиады

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

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

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

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

3
Ivanov 15
Petrov 10
Sidorov 20

Sidorov
Ivanov
Petrov

ZA: "Сортировка времени"

Вводится сначала число N (1≤N≤100), а затем N моментов времени. Каждый момент времени задается 3 целыми числами - часы (от 0 до 23), минуты (от 0 до 59) и секунды (от 0 до 59), каждый из них записан в отдельной строке.

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

4
10 
20 
30
7 
30 
00
23 
59 
59
13 
30 
30

7 30 0
10 20 30
13 30 30
23 59 59

K: Такси^*

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин —ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор хочет заплатить как можно меньшую сумму.

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

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

10 20 30
50 20 30

1700

Бинарный поиск

ZD: Двоичный поиск

В первой строке входных данных содержатся натуральные числа N и K (0 < N, K ≤ 100000). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 10⁹.

Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

5 4
1 4 5 8 9
5 6 1 9

YES
NO
YES
YES

ZE: Приближенный двоичный поиск

В первой строке входных данных содержатся числа N и K (0 < N, K ≤ 100001). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию, а в третьей строке – K чисел второго массива. Каждое число в обоих массивах по модулю не превосходит 2*10⁹.

Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.

5 4
1 4 5 8 10
5 6 1 9

5
5
1
8

ZF: Левый и правый двоичный поиск

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

В первой строке входных данных записано два числа N и M (1 < N, M < 20000). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка. Все числа в списках - целые 32-битные знаковые.

Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179

10 10
3 4
7 7
1 2
0

Дополнительная задача

Очень легкая задача.