В упражнениях A-C необходимо реализовать функцию, модифицирующую переданные ей списки.
Для поднятия настроения населения, были запрещены отрицательные числа. Поэтому в данном списке нужно оставить только положительные числа, удалив из списка все отрицательные числа и нули.
Решение оформите в виде функции positive(a). Функция получает на вход список
чисел и должна удалить из этого списка неположительные значения, оставив только положительные числа,
не меняя их порядка. Функция должна модифицировать тот список, который ей передали, и не возвращать значение при этом.
Сдайте на проверку только тело функции.
| Список a до вызова функции | Список a после вызова positive(a) |
|---|---|
[1, -1, 0, 2, 1] |
[1, 2, 1] |
Решите предыдущую задачу при условии, что сложность решения должна быть \(O(n)\), где \(n\) — размер исходного массива.
В тестах массив может иметь длину до \(10^5\) элементов, ограничение по времени работы программы — 1 секунда.
Напишите функцию swap(a, b), которая обменивает
содержимое двух данных списков a и b.
Решение должно иметь сложность O(len(a) + len(b)).
В упражнениях D-F необходимо реализовать конкретный алгоритм сортировки. Именно тот алгоритм, который указан в задании.
Дан список сравнимых между собой элементов (чисел, строк и т.д.). Упорядочите его в порядке неубывания значений.
Решите эту задачу при помощи алгоритма сортировки выбором.
Решение оформите в виде функции selection_sort(a).
Эта функция должна вернуть новый список, упорядочив
значения исходного списка.
В этой задаче разрешается модифицировать исходный список, в частности, можно удалять из исходного списка элементы по одному, добавляя их в новый список.
| Вызов функции | Возвращаемое значение |
|---|---|
selection_sort([1, 4, 2, 3, 4]) |
[1, 2, 3, 4, 4] |
selection_sort(['one', 'two', 'three', 'four']) |
['four', 'one', 'three', 'two'] |
Реализуйте алгоритм сортировки пузырьком.
Решение оформите в виде функции bubble_sort(A).
Эта функция должна изменить переданный ей список, не возвращая значения.
Алгоритм должен заканчивать работу в случае, если на очередном проходе ни одна перестановка элементов не была выполнена, то есть массив уже стал упорядоченным.
| Список a до вызова функции | Список a после вызова bubble_sort(a) |
|---|---|
[1, 4, 2, 3, 4] |
[1, 2, 3, 4, 4] |
['one', 'two', 'three', 'four'] |
['four', 'one', 'three', 'two'] |
Реализуйте алгоритм сортировки вставками.
Решение оформите в виде функции insertion_sort(a).
Эта функция должна изменить переданный ей список, не возвращая значения.
Реализация алгоритма сортировки вставкой должна работать быстро на уже упорядоченном массиве или на массиве, который близок к упорядоченному.
| Список a до вызова функции | Список a после вызова insertion_sort(a) |
|---|---|
[1, 4, 2, 3, 4] |
[1, 2, 3, 4, 4] |
['one', 'two', 'three', 'four'] |
['four', 'one', 'three', 'two'] |
В следующих заданиях необходимо решить задачи, используя стандартную функцию
sorted или метод sort. Квадратичные алгоритмы
в этих задачах использовать не получится, т.к. они медленные.
Системный администратор вспомнил, что давно не делал архива пользовательских файлов. Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.
Известно, какой объем занимают файлы каждого пользователя.
Напишите программу, которая по заданной информации о пользователях и свободному объему на архивном диске определит максимальное число пользователей, чьи данные можно поместить в архив, при этом используя свободное место как можно более полно.
Программа получает на вход в одной строке число S размер свободного места на диске, и число N — количество пользователей, после этого идет N чисел — объем данных каждого пользователя, записанных каждое в отдельной строке.
Выведите наибольшее количество пользователей, чьи данные могут быть помешены в архив.
Используйте стандартную сортировку. Решение должно иметь сложность стандартной сортировки + O(N). Решение не должно модифицировать исходный список после считывания и сортировки.
| Ввод | Вывод |
|---|---|
100 2 |
1 |
100 3 |
2 |
После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин —ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.
Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор хочет заплатить как можно меньшую сумму.
В первой строке записаны N чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании. Во второй строке записаны N чисел — тарифы за проезд одного километра в такси.
Выведите одно целое число — наименьшую сумму, которую придется заплатить за доставку всех сотрудников.
| Ввод | Вывод |
|---|---|
10 20 30 |
1700 |
В супермаркете проводится беспрецедентная акция – «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».
Вася, идя в супермаркет, определился, какие товары он хочет купить, и узнал, сколько они стоят. Помогите ему определить минимальную сумму денег, которую ему нужно взять с собой, чтобы в итоге стать счастливым обладателем этих товаров.
Программа получает на вход N чисел – стоимости выбранных Васей товаров. Все стоимости – натуральные числа, не превышающие 10000.
Выведите одно число – сумму денег, которую Вася должен взять с собой в супермаркет (минимально возможную).
| Ввод | Вывод | Пояснение |
|---|---|---|
1 5 4 3 5 7 |
19 |
Вася сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 – заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок. |
3 15 25 8 8 |
51 |
Вася в первый заход в супермаркет купит товары стоимостью 15 и 25 рублей, в качестве подарка взяв товар стоимостью 8 рублей. А во второй заход в супермаркет купит товары стоимостью 3 и 8, не взяв никакого подарка. |
Дан список чисел. Определите, сколько в нем различных чисел.
Используйте встроенную сортировку языка Python. Решение должно иметь сложность встроенной сортировки + O(n).
| Ввод | Вывод |
|---|---|
1 7 9 7 1 |
3 |
Дан список чисел (содержащий не менее двух элементов). Найдите в нем два ближайших друг к другу числа (то есть два числа с наименьшей разностью).
Выведите эти числа в порядке неубывания.
Используйте встроенную сортировку языка Python. Решение должно иметь сложность встроенной сортировки + O(n).
| Ввод | Вывод |
|---|---|
9 4 1 6 |
4 6 |
В некотором городе на прямой улице расположено \(n\) домов. \(i\)-й дом задан неотрицательной величиной \(x_i\) — расстоянием от начала улицы до дома, таким образом, расстояние между двумя домами \(i\) и \(j\) равно \(|x_i-x_j|\).
В одном из этих домов необходимо открыть магазин таким образом, чтобы суммарное расстояние от магазина до остальных домов было наименьшим.
Программа получает на вход список различных неотрицательных чисел — координаты домов и должна вывести координату дома, в котором необходимо открыть магазин.
| Ввод | Вывод |
|---|---|
1 2 3 4 |
2 |
Одна очень предприимчивая и симпатичная девушка решила собрать себе денег на роскошную жизнь. У нее есть \(N\) поклонников, про каждого из них она узнала размер его состояния \(P_i\). Девушка намерена выйти замуж и сразу же развестись с некоторыми из своих поклонников. По законам страны в случае развода каждый из супругов получает ровно половину их общего состояния.
Первая строка входных данных содержит \(N\) чисел \(X_1\), ..., \(X_N\) — размеры состояний поклонников. Вторая строка содержит одно число \(Y\) — состояние девушки.
Выведите одно действительное число — максимальную сумму денег, которая может оказаться у девушки в результате махинаций.
| Ввод | Вывод |
|---|---|
5 10 |
7.5 |
1 3 2 |
2.125 |
1 |
2.0 |
Президент в США выбирается коллегией выборщиков в результате непрямых выборов. Рассмотрим упрощенную модель таких выборов.
Все избиратели делятся на \(K\) групп (необязательно равных по численности), каждая группа имеет одного представителя в коллегии выборщиков. Сначала в каждой группе проводится голосование по поставленному вопросу, если строго более половины избирателей группы высказывается “за”, то представитель этой группы в коллегии выборщиков голосует ”за“ от имени всей группы. Решение принимается, если строго более половины выборщиков (то есть групп) проголосовали “за”.
При такой системе решение может быть принято коллегией выборщиков, даже если “за” высказалось менее половины от общего числа избирателей.
Программа получает на вход \(K\) чисел — размеры групп.
Программа должна вывести минимальное количество избирателей, которое могло проголосовать “за”, если в итоге решение было принято коллегией выборщиков.
| Ввод | Вывод |
|---|---|
5 5 7 |
6 |
4 2 1 3 7 |
5 |
В классе учатся \(N\) человек. Классный руководитель получил указание разбить их на \(R\) бригад по \(C\) человек в каждой и направить на субботник (\(N = RC\)).
Все бригады на субботнике будут заниматься переноской бревен. Каждое бревно одновременно несут все члены одной бригады. При этом бревно нести тем удобнее, чем менее различается рост членов этой бригады.
Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!
Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по четыре человека в каждой. Тогда одним из вариантов является такой:
1 бригада: люди с ростом 225, 205, 225, 260.
2 бригада: люди с ростом 160, 190, 170, 130.
При этом максимальное число неудобства будет во второй бригаде, оно будет равно 60, и это наилучший возможный результат.
Первая строка входных данных содержит два натуральные числа \(R\) и \(C\) — количество бригад и количество человек в каждой бригаде. Далее вводятся \(N = RC\) целых чисел по одному числу в строке — рост каждого из \(N\) учеников.
Выведите одно число — наименьшее возможное значение максимального числа неудобства сформированных бригад.
| Ввод | Вывод |
|---|---|
2 4 |
60 |
В обувном магазине продается обувь разного размера. Известно, что одну пару обуви можно надеть на другую, если она хотя бы на три размера больше. В магазин пришел покупатель. Требуется определить, какое наибольшее количество пар обуви сможет предложить ему продавец так, чтобы он смог надеть их все одновременно.
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), в следующей строке — размеры каждой пары обуви в магазине через пробел. Размер — натуральное число, не превосходящее 100.
Выведите единственное число —максимальное количество пар обуви, которое сможет надеть покупатель.
| Ввод | Вывод |
|---|---|
60 |
2 |
35 |
2 |
Дано \(N\) гирек, массы которых — целые числа. Определите минимальную целочисленную массу груза, которую нельзя уравновесить на чашечных весах при помощи какого-то подмножества данного набора гирек.
Программа получает на вход \(N\le 10^5\) чисел — массы гирек (целые числа, не превосходящие \(10^9\)). Программа должна вывести одно число — искомую массу.
| Ввод | Вывод |
|---|---|
1 1 5 1 |
4 |
1 2 4 8 |
16 |
В 179 школе есть много коньков самых разных размеров. Школьник может надеть коньки любого размера, который не меньше размеров его ноги. Известны размеры всех коньков и размеры ног школьников. Определите, какое наибольшее число школьников сможет одновременно пойти покататься.
Первая строка содержит список натуральных чисел размеры коньков. Вторая строка содержит список размеров ног школьников.
Выведите единственное число — наибольшее количество школьников, которое сможет пойти на каток.
| Ввод | Вывод |
|---|---|
41 40 39 42 |
2 |
Интернет-магазину нужно доставить заказы \(n\) покупателям, которые расположены на одной улице. Офис магазина находится на этой же улице. Расположения всех покупателей и офиса задаются координатами на прямой.
Курьер Бенвенуто должен развезти за день \(k\) заказов. Он пришёл в офис первым и может выбрать любые \(k\) заказов. Он хочет выбрать заказы так, чтобы проделать за день как можно меньший путь с учётом того, что он выезжает из офиса и должен вернуться в офис.
Определите путь, которй проедет Бенвенуто.
Первая строка входных данных содержит три числа: \(n\), \(k\) и \(x\), где \(x\) — координата офиса. Следующая строка содержит \(n\) чисел — координаты клиентов. Ограничения: \(1\le k\le n\le 10^5\), все координаты — целые положительные числа, не превосходящие \(10^9\).
В примере из условия Бенвенуто выезжает из точки \(x=10\), отвозит два заказа клиентам в точках 11 и 13 и возвращается назад. Он проедет расстояние 6.
| Ввод | Вывод |
|---|---|
7 2 10 |
6 |
Кто-то перепутал Ханойскую головоломку и разместил диски на первом стержне не соблюдая правила игры. Переложите эти диски так, чтобы они оказались на одном из стержней строго в порядке возрастания номеров.
Программа получает на вход число дисков \(n \le 10\). Во второй строке записаны \(n\) чисел — номера дисков на первом стержне сверху вниз.
Перемещать диск можно только в том случае, если он кладется на диск большего номера. Выведите последовательность перекладываний, размещающая диски на любом стержне в порядке возрастания номеров. Формат вывода одного перекладывания: \(A\) \(B\) \(C\), где \(A\) — номер перемещаемого диска (\(1\le A\le n\)), \(B\) — номер стержня с которого снимается диск, \(C\) — номер стержня на который кладется диск.
| Ввод | Вывод |
|---|---|
3 |
2 1 2 |