Сортировки

Новые методы работы со списками.

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

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

Передача списка в качестве параметра

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

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

B = A[:]

или использовать функцию copy из одноименного модуля:

from copy import *
B = copy(A)

Упражнения

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

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

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

Решение оформите в виде функции IsAscending(A). В данной функции должен быть один цикл while, не содержащий вложенных условий и циклов — используйте схему линейного поиска.

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

E: Сортировка выбором

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

Решите эту задачу при помощи алгоритма сортировки выбором. Решение оформите в виде функции SelectionSort(A).

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

В этой задаче разрешается модифицировать исходный список, в частности, удалить из списка i-й элемент можно при помощи метода pop(i), и использовать новый список для добавления в него элементов.

1 4 2 3 4

4 4 3 2 1

F: Сортировка вставкой

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

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

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

В алгоритме сортировки вставкой в каждый произвольный момент начальная часть массива уже отсортирована. В решении имеется цикл for i in range(1, len(A)), внутри которого в предположении, что элементы списка A[0], A[1], ..., A[i-1] уже отсортированы, элемент A[i] добавляется в отсортированную часть списка. Для этого находится позиция, в которую необходимо вставить элемент A[i], затем осуществляется циклический сдвиг фрагмента уже отсортированной части.

1 4 2 3 4

1 2 3 4 4

G: Сортировка пузырьком

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

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

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

Вспомогательным списком пользоваться нельзя.

1 4 2 3 4

4 4 3 2 1

Функция sorted и метод sort

Функция sorted получает в качестве аргумента список, и возвращает ссылку на новый список, содержащий те же элементы в порядке возрастания. Пример:

A = [1, 6, 2, 5, 3, 4]
B = sorted(A)

Метод sort применяется к списку и переставляет элементы списка в порядке возрастания. Пример:

A.sort()

Например, вот решение задачи про сортировку в порядке неубывания в одну строку:

print(" ".join(list(map(str,sorted(list(map(int,input().split())))))))

У функции sorted и метода sort есть параметр reverse. Если этот параметр установить в True, то сортировка будет выполняться в порядке невозрастания. Пример:

B = sorted(A, reverse = True)
A.sort(reverse = True)

Упражнения

H: Создание архива

Системный администратор вспомнил, что давно не делал архива пользовательских файлов. Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.

Известно, какой объем занимают файлы каждого пользователя.

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

Программа получает на вход в одной строке число S – размер свободного места на диске (натуральное, не превышает 10000), и число N – количество пользователей (натуральное, не превышает 100), после этого идет N чисел - объем данных каждого пользователя (натуральное, не превышает 1000), записанных каждое в отдельной строке.

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

100 2
200
50

1

100 3
50
30
50

2

I: Обувной магазин^*

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

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

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

60
60 63

2

35
30 40 35 42 35

2

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

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

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

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

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

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

3
Ivanov 15
Petrov 10
Sidorov 20

Sidorov
Ivanov
Petrov

K: Такси^*

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

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

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

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

10 20 30
50 20 30

1700

L: Коньки^*

В 179 школе есть много коньков самых разных размеров. Школьник может надеть коньки любого размера, который не меньше размеров его ноги. Известны размеры всех коньков и размеры ног школьников. Определите, какое наибольшее число школьников сможет одновременно пойти покататься.

Первая строка содержит список натуральных чисел  размеры коньков. Вторая строка содержит список размеров ног школьников.

Выведите единственное число — наибольшее количество школьников, которое сможет пойти на каток.

41 40 39 42
42 41 42

2

M: Чемпионат по стрельбе^*

На региональном этапе Всероссийской олимпиады школьников по информатике 23 января 2011 года предлагалась следующая задача.

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

Расспросив папу, школьник выяснил, что количество очков, которое набрал папа, заканчивается на 5, один из победителей чемпионата стрелял раньше папы, а папин друг, который стрелял сразу после папы, набрал меньше очков. Теперь он заинтересовался, какое самое высокое место мог занять его папа на том чемпионате.

Будем считать, что участник соревнования занял k-е место, если ровно (k-1) участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место.

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

Программа получает на вход целое число n — количество участников чемпионата страны по стрельбе (3≤n≤10⁵). Далее идет n положительных целых чисел, каждое из которых не превышает 1000, — очки участников чемпионата, приведенные в том порядке, в котором они выполняли стрельбу.

Выведите одно целое число — самое высокое место, которое мог занять папа школьника. Если не существует ни одного участника чемпионата, который удовлетворяет, описанным выше условиям, выведите в выходной файл число 0.

7
10 20 15 10 30 5 1

6

3
15 15 10

1

3
10 15 20

0

N: SMS-голосование

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

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

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

Неверные номера, присланные телезрителями (то есть большие чем N) необходимо игнорировать.

3
1 2 2 1 3 2 3

2

2
1 2 2 1

1 2

3
4 3 4

3

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

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

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

Решение оформите в виде функции CountSort(A), которая модифицирует передаваемый ей список. Использовать встроенные функции сортировки нельзя.

1 3 2 3 1

1 1 2 3 3

P: Клавиатура

На региональном этапе Всероссийской олимпиады школьников по информатике в 2009 году предлагалась следующая задача.

Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.

При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие — нет.

Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.

Первая строка входных данных содержит целое число n (1≤n≤1000) — количество клавиш на клавиатуре. Вторая строка содержит n целых чисел — с₁, с₂, … , с_n, где с_i (1≤c_i≤100000) — количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1≤k≤100000) — общее количество нажатий клавиш, и последняя строка содержит k целых чисел p_j (1≤p_j≤n) — последовательность нажатых клавиш.

Программа должна вывести n строк, содержащих информацию об исправности клавиш. Если i-я клавиша сломалась, то i-ая строка должна содержать слово YES, если же клавиша работоспособна — слово NO.

5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5

YES
NO
NO
NO
YES

Q: Задача Иосифа Флавия^*

N человек, пронумерованных числами от 1 до N стоят в кругу. Они начинают считаться, каждый K-й по счету человек выбывает из круга, после чего счет продолжается со следующего за ним человека.

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

Программа получает на вход числа N и K, не превосходящие 100 и должна вывести одно число от 1 до N.

5 7

4

В этом примере люди выбывают в таком порядке: 2, 5, 1, 3, остался номер 4.

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

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

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

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

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