Сортировки

Напомню некоторые методы работы со списками

A.pop() — удалить последний элемент из списка. A.pop(i) — удалить из списка элемент с индексом i.

A.insert(i, val) — вставить в список A в позицию с индексом i элемент со значением val. Элементы, которые раньше имели индексы i и более сдвигаются вправо.

Копирование списков

Присваивание B = A не создает новый список, а всего лишь делает B ссылкой на уже существующий список. Для создания копии списка можно использовать срезы:

B = A[:]

Упражнения

A: Возрастает ли список?

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

Выведите YES, если массив монотонно возрастает и NO в противном случае.

1 7 9

YES

B: Последний максимум

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

1 2 1 2 1

2 3

C: Количество цифр

Дана последовательность чисел, состоящая только из чисел 1, ..., 9. Последовательность завершается числом 0. Каждое число записано в отдельной строке.

Подсчитайте, сколько раз в этой последовательности встречаются значения 1, 2, ..., 9. Сохранять всю последовательность введенных чисел в списке нельзя.

Программа должна вывести ровно 9 чисел: количество единиц, двоек, ..., девяток в данной последовательности.

1
2
3
4
5
1
1
1
2
2
0

4 3 1 1 1 0 0 0 0

D: Противоположные элементы

Дан список чисел. Определите, есть ли в нем два противоположных (то есть дающих в сумме 0) числа.

Если такие числа есть в массиве, выведите их индексы в порядке возрастания. Если таких чисел в массиве нет, ничего не выводите.

1 2 3 -2 -4

1 3

ZG: Второй максимум

Дан список. Представьте, что в этом списке удалили наибольшее число (если таких чисел несколько, то удалили только одно из них). Какое число сейчас будет наибольшим?

Легенда задачи. На столе лежат N кучек монет, известно количество монет в каждой кучке. N пиратов по очереди выбирают кучку и забирают себе все монеты из нее. Естественно, каждый пират хочет, чтобы ему досталось как можно больше монет. Первым кучку выбирает пират Петя, вторым - пират Вася, после них свои кучки выбирают другие пираты. Сколько монет достанется Васе?

Все числа записаны в одной строке, все числа натуральные.

Важное ограничение: решите эту задачу за один проход по списку.

1 2 1 2 1

2

1 2 10 3 5

5

Собственно сортировки

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

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

1 4 2 3 4

4 4 3 2 1

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

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

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

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

Задачи на сортировки

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

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

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