Изменяемые и неизменяемые объекты в Python (mutable and immutable).
В питоне всё, что можно положить в переменную, является объектом.
А сама переменная является ссылкой на этот объект.
a = 1
a = 2
b = a
Объекты «живут» в своём мире независимо от переменных, а переменные — один из способов обратиться извне к миру объектов.
Так в примере выше объект Целое-число-1 продолжает жить даже после того, как мы поменяли переменную a.
Объекты в питоне бывают двух значительно отличающихся сортов: изменяемые (mutable) и неизменяемые (immutable).
Неизменяемыми являются целые и действительные числа (int, float), строки (str), последовательности байтов (бинарные данные, bytes), а также кортежи, все элементы которых неизменяемы (tuple).
Напротив, списки (list), словари (dict) и множества (set) являются изменяемыми.
Что всё это значит?
Неизменяемые объекты обладают замечательным свойством: они не могут измениться в результате работы программы.
Если некоторая переменная «смотрит» на неизменяемый объект, то можно быть уверенным, что её значение не поменяется, если только ей не присвоить ссылку на другой объект.
Например, в результате выполнения кода a = 1 в переменной a хранится ссылка на объект Целое-число-1, и что бы не происходило с другими переменными, a будет всегда равно 1.
Изменяемые объекты не обладают таким постоянством.
Они скорее напоминают контейнер для хранения: контейнер остаётся на месте, а вот содержимое может сильно измениться.
Что всё это для нас значит?
Ну, например, если передать список в «чужую» функцию, то его могут испортить до неузнаваемости:
Здесь можно поиграться с этим примером и посмотреть на то, что происходит с ссылками:
Обратите внимание, при передаче списка в функцию можно модифицировать элементы списка при помощи присваиваний A[i] = ..., методов pop, append, insert и т.д.
Это не является модификацией списка, как целого, т.е. имя A по-прежнему указывает на тот же список, при этом
содержимое списка меняется.
Не всегда такое поведение является ожидаемым:
a = [1, 2, 3]
b = a
b.insert(0, 'ops')
b.pop()
print(b) # -> ['ops', 1, 2]
print(a) # -> ['ops', 1, 2]
Присваивание b = a не создает новый список,
а всего лишь делает b ссылкой на уже
существующий список.
Для того, чтобы «сохранить» старый список, нужно создавать его копию:
Метод .copy() создаёт новый список, в котором хранятся в точности те же ссылки.
Это означает, что если в списке будет лежать другой список, то копия будет на него ссылаться:
В упражнениях A-C необходимо реализовать функцию, модифицирующую переданные ей списки.
Программа не должна содержать никакого кода вне функций.
A: Только положительные
Для поднятия настроения населения, были запрещены отрицательные числа. Поэтому в данном списке
нужно оставить только положительные числа, удалив из списка все отрицательные числа и нули.
Решение оформите в виде функции positive(a). Функция получает на вход список
чисел и должна удалить из этого списка неположительные значения, оставив только положительные числа,
не меняя их порядка. Функция должна модицифицировать тот список, который ей передали, и не возвращать значение при этом.
Сдайте на проверку только тело функции.
[1, -1, 0, 2, 1]
[1, 2, 1] # Вывода нет, это изменённый список
[-1, -1, -1, -1]
[] # Вывода нет, это изменённый список
Вот пример того, как нужно тестировать вашу функцию:
def positive(a):
a.pop() # Вместо pop нужны правильные модификации
test = [1, -1, 0, 2, 1]
positive(test)
print(test) # Должен выдать [1, 2, 1]
Код вызова функции для тестирования
source_list = eval(input())
source_list_saved = source_list
res = positive(source_list)
if res is not None:
print("Функция не должна возвращать значение")
elif source_list != source_list_saved:
print("Вызов функции изменил значение переданной ссылки при помощи глобальных переменных")
else:
print(source_list)
IDE
B★: Только положительные — за O(n)
Решите предыдущую задачу при условии, что сложность решения должна быть \(O(n)\), где
\(n\) — размер исходного массива.
В тестах массив может иметь длину до \(10^5\) элементов, ограничение
по времени работы программы — 1 секунда.
Подсказка
Да что-то непонятное тут требуют...
Идея очень красивая!
Нужно создать переменную num_pos, в которой мы храним количество найденных положительных элементов.
Сначала там 0.
Дальше идём по списку от начала и до конца.
Если очередной элемент отрицательный, то идём дальше.
Если положительный, то запишем его по индексу num_pos и прибавим к num_pos единицу.
А когда числа закончатся, удалить весь хвост после num_pos.
IDE
C: Обмен списков
Напишите функцию swap(a, b), которая обменивает
содержимое двух данных списков a и b.
Решение должно иметь сложность $O(len(a) + len(b))$.
Код вызова функции для тестирования
list1 = eval(input())
list2 = eval(input())
list1_saved = list1
list2_saved = list2
res = swap(list1, list2)
if res is not None:
print("Функция не должна возвращать значение")
elif list1 != list1_saved or list2 != list2_saved:
print("Функция изменила ссылки на переданные списки, это означает использование глобальных переменных")
else:
print(list1)
print(list2)
IDE
Упражнения на реализацию квадратичных алгоритмов сортировки
В упражнениях D-F необходимо реализовать конкретный алгоритм сортировки.
Именно тот алгоритм, который указан в задании.
Программа не должна содержать никакого кода вне функций.
D: Сортировка выбором
Дан список сравнимых между собой элементов (чисел, строк и т.д.).
Упорядочите его в порядке неубывания значений.
Решите эту задачу при помощи алгоритма сортировки выбором.
Решение оформите в виде функции selection_sort(a).
Эта функция должна вернуть новый список, упорядочив
значения исходного списка.
В алгоритме сортировки выбором мы находим наименьший элемент
в списке и ставим его на первое место, затем находим наименьший
элемент из оставшихся и ставим его на второе место и т.д.
В этой задаче разрешается модифицировать исходный список,
в частности, удалить из списка i-й элемент
можно при помощи метода pop(i), и использовать
новый список для добавления в него элементов.
[1, 4, 2, 3, 4]
[1, 2, 3, 4, 4]
['one', 'two', 'three', 'four']
['four', 'one', 'three', 'two']
Код вызова функции для тестирования
a = eval(input())
sorted = None
res = selection_sort(a)
if type(res) != list:
print("Функция должна возвращать список")
else:
print(res)
IDE
E: Сортировка пузырьком
Реализуйте алгоритм сортировки пузырьком.
Решение оформите в виде функции bubble_sort(A).
Эта функция должна изменить переданный ей список, не возвращая значения.
В алгоритме пузырьковой сортировки осуществляется проход
по списку от начала к концу, и если два соседних элемента списка
стоят в неверном порядке, то они переставляются в правильном
порядке. В результате максимальный элемент списка окажется
на последнем месте. Повторим эту
процедуру еще несколько раз, чтобы поставить все элементы на свои места.
Алгоритм должен заканчивать работу в случае, если на очередном
проходе ни одна перестановка элементов не была выполнена, то есть
массив уже стал упорядоченным.
Вспомогательным списком пользоваться нельзя.
[1, 4, 2, 3, 4]
[1, 2, 3, 4, 4]
['one', 'two', 'three', 'four']
['four', 'one', 'three', 'two']
Код вызова функции для тестирования
a = eval(input())
sorted = None
res = bubble_sort(a)
if res is not None:
print("Функция не должна возвращать значение")
else:
print(a)
IDE
F: Сортировка вставкой
Реализуйте алгоритм сортировки вставками.
Решение оформите в виде функции insertion_sort(a).
Эта функция должна изменить переданный ей список, не возвращая значения.
В этой задаче нельзя пользоваться дополнительным списком
и операциями удаления и вставки элементов.
В алгоритме сортировки вставкой в каждый произвольный момент
начальная часть списка уже отсортирована. В решении имеется цикл
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]
['one', 'two', 'three', 'four']
['four', 'one', 'three', 'two']
Код вызова функции для тестирования
a = eval(input())
sorted = None
res = insertion_sort(a)
if res is not None:
print("Функция не должна возвращать значение")
else:
print(a)
IDE
Функция sorted и метод sort
Функция sorted получает в качестве аргумента список, и возвращает ссылку на новый список,
содержащий те же элементы в порядке возрастания. Пример:
A = [1, 6, 2, 5, 3, 4]
B = sorted(A)
Метод sort применяется к списку и переставляет элементы списка в порядке возрастания. Пример:
A.sort()
Например, вот решение задачи про сортировку в порядке неубывания в одну строку:
У функции sorted и метода sort есть параметр reverse. Если этот
параметр установить в True, то сортировка будет выполняться в порядке невозрастания. Пример:
B = sorted(A, reverse=True)
A.sort(reverse=True)
Упражнения на использование стандартной сортировки
В следующих заданиях необходимо решить задачи, используя стандартную функцию
sorted или метод sort. Квадратичные алгоритмы
в этих задачах использовать не получится, т.к. они медленные.
G: Создание архива
Системный администратор вспомнил, что давно не делал архива пользовательских файлов.
Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.
Известно, какой объем занимают файлы каждого пользователя.
Напишите программу, которая по заданной информации о пользователях и свободному объему на архивном диске определит максимальное число пользователей,
чьи данные можно поместить в архив, при этом используя свободное место как можно более полно.
Программа получает на вход в одной строке число S размер свободного места на диске,
и число N — количество пользователей, после этого идет N чисел — объем
данных каждого пользователя, записанных каждое в отдельной строке.
Выведите наибольшее количество пользователей, чьи данные могут быть помешены в архив.
Используйте стандартную сортировку. Решение должно иметь сложность стандартной сортировки + O(N).
Решение не должно модифицировать исходный список после считывания и сортировки.
100 2
200
50
1
100 3
50
30
50
2
IDE
H: Такси
После затянувшегося совещания директор фирмы решил заказать такси,
чтобы развезти сотрудников по домам. Он заказал N машин —ровно столько, сколько у него сотрудников.
Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.
Директор знает, какому сотруднику сколько километров от работы до дома
(к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине).
Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор
хочет заплатить как можно меньшую сумму.
В первой строке записаны N чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании.
Во второй строке записаны N чисел — тарифы за проезд одного километра в такси.
Выведите одно целое число — наименьшую сумму, которую придется заплатить за доставку всех сотрудников.
10 20 30
50 20 30
1700
IDE
I: Скидки
В супермаркете проводится беспрецедентная акция – «Покупая два любых товара,
третий получаешь бесплатно*», а внизу мелким шрифтом приписано
«* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».
Вася, идя в супермаркет, определился, какие товары он хочет купить, и узнал, сколько они стоят.
Помогите ему определить минимальную сумму денег, которую ему нужно взять с собой, чтобы в итоге стать счастливым обладателем этих товаров.
Программа получает на вход 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, не взяв никакого подарка.
IDE
J: Количество различных чисел
Дан список чисел. Определите, сколько в нем различных чисел.
Используйте встроенную сортировку языка Python. Решение должно иметь
сложность встроенной сортировки + O(n).
1 7 9 7 1
3
IDE
K: Два ближайших числа
Дан список чисел (содержащий не менее двух элементов). Найдите в нем два ближайших друг к другу числа
(то есть два числа с наименьшей разностью).
Выведите эти числа в порядке неубывания.
Используйте встроенную сортировку языка Python. Решение должно иметь
сложность встроенной сортировки + O(n).
9 4 1 6
4 6
IDE
L: Строительство магазина
В некотором городе на прямой улице расположено \(n\) домов.
\(i\)-й дом задан неотрицательной величиной \(x_i\) — расстоянием
от начала улицы до дома, таким образом, расстояние между двумя
домами \(i\) и \(j\) равно \(|x_i-x_j|\).
В одном из этих домов необходимо открыть магазин таким образом, чтобы
суммарное расстояние от магазина до остальных домов было наименьшим.
Программа получает на вход список различных неотрицательных ччисел —
координаты домов и должна вывести координату дома, в котором необходимо открыть магазин.
1 2 3 4
2
IDE
M: Свадьбы
Одна очень предприимчивая и симпатичная девушка решила собрать себе денег на роскошную жизнь.
У нее есть \(N\) поклонников, про каждого из них она узнала размер его состояния \(P_i\).
Девушка намерена выйти замуж и сразу же развестись с некоторыми из своих поклонников.
По законам страны в случае развода каждый из супругов получает ровно половину их общего
состояния.
Первая строка входных данных содержит \(N\) чисел \(X_1\), ..., \(X_N\) — размеры
состояний поклонников. Вторая строка содержит одно число \(Y\) — состояние девушки.
Выведите одно действительное число — максимальную сумму
денег, которая может оказаться у девушки в результате махинаций.
5 10
5
7.5
1 3 2
0
2.125
1
2
2.0
IDE
N: Выборы в США
Президент в США выбирается коллегией выборщиков в результате непрямых выборов. Рассмотрим упрощенную модель таких
выборов.
Все избиратели делятся на \(K\) групп (необязательно равных по численности),
каждая группа имеет одного представителя в коллегии выборщиков.
Сначала в каждой группе проводится голосование по поставленному вопросу, если строго более половины
избирателей группы высказывается “за”, то представитель этой группы в коллегии выборщиков
голосует ”за“ от имени всей группы. Решение принимается, если строго более половины
выборщиков (то есть групп) проголосовали “за”.
При такой системе решение может быть принято коллегией выборщиков, даже если “за”
высказалось менее половины от общего числа избирателей.
Программа получает на вход \(K\) чисел — размеры групп.
Программа должна вывести минимальное количество изибираетелей, которое могло проголосовать “за”,
если в итоге решение было принято коллегией выборщиков.
5 5 7
6
4 2 1 3 7
5
IDE
O: Субботник
В классе учатся \(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
170
205
225
190
260
130
225
160
60
IDE
P: Обувной магазин
В обувном магазине продается обувь разного размера.
Известно, что одну пару обуви можно надеть на другую,
если она хотя бы на три размера больше. В магазин пришел покупатель.
Требуется определить, какое наибольшее количество пар обуви сможет
предложить ему продавец так, чтобы он смог надеть их все одновременно.
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), в следующей строке — размеры
каждой пары обуви в магазине через пробел. Размер — натуральное число, не превосходящее 100.
Выведите единственное число —максимальное количество пар обуви, которое сможет надеть покупатель.
60
60 63
2
35
30 40 35 42 35
2
Выведите единственное число —максимальное
количество пар обуви, которое сможет надеть покупатель.
IDE
Q★: Несоставляемая масса
Дано \(N\) гирек, массы которых — целые числа. Определите минимальную целочисленную массу груза,
которую нельзя уравновесить на чашечных весах при помощи какого-то подмножества данного набора гирек.
Программа получает на вход \(N\le 10^5\) чисел — массы гирек (целые числа,
не превосходящие \(10^9\)). Программа должна вывести одно число — искомую массу.
1 1 5 1
4
1 2 4 8
16
IDE
R: Коньки
В 179 школе есть много коньков самых разных размеров. Школьник может надеть коньки любого размера, который не меньше
размеров его ноги. Известны размеры всех коньков и размеры ног школьников. Определите, какое наибольшее число школьников
сможет одновременно пойти покататься.
Первая строка содержит список натуральных чисел размеры коньков. Вторая строка содержит
список размеров ног школьников.
Выведите единственное число — наибольшее количество школьников, которое сможет пойти на каток.
41 40 39 42
42 41 42
2
IDE
Cортировка списков и кортежей в Python
Иногда возникает необходимость сортировать не только числовые последовательности, но и более сложные объекты.
В языке Python можно сортировать список с любыми объектами, если их можно сравнивать друг с другом.
Начнём с того, что Python умеет сравнивать списки и кортежи:
Сравнивает он их поэлементно (или лексикографически), то есть сначала сравнивает первые элементы.
Владелец большего первого элемента и сам больше.
Если же первые элементы совпадают, то мы сравниваем вторые элементы.
Так мы движемся до тех пор, пока i-й элемент одного списка не станет больше i-го элемента второго списка, тогда первый победит.
Если какой-то список закончился раньше, то он меньше.
А иначе списки совпадают.
Итак, если списки можно сравнивать, то их можно и сортировать.
Конечно же, для того, чтобы такой «сложный» список можно было отсортировать, необходимо, чтобы его элементы можно было сравнить.
>>> sorted([[1, 2], [1, 'a']])
Traceback (most recent call last):
File "< string >", line 301, in runcode
File "< interactive input >", line 1, in < module >
TypeError: unorderable types: str() < int()
Упражнения на сортировку кортежей
S: Сортировка по последней цифре
Даны \(N\) натуральных чисел. Упорядочите их
в порядке возрастания последней цифры числа, а при равенстве
последней цифры — по возрастанию самих чисел.
Упорядоченные числа выведите через пробел.
123 321 333
321 123 333
IDE
T: Личные дела
Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам,
а внутри класса по фамилиям.
В первой строке входных данных записано число \(N\) — количество личных дел.
Далее записано \(N\) строк, каждая из которых состоит из фамилии учащегося (строка без пробелов)
и номера класса (целое число от 1 до 11).
Нужно вывести список всех учащихся, сначала выводя номер класса, затем — фамилию учащегося.
Список должен быть отсортирован по классу, а затем по фамилии.
Указание: составьте список из кортежей: номер класса и фамилия участника.
3
Ivanov 10
Petrov 9
Sidorov 9
9 Petrov
9 Sidorov
10 Ivanov
IDE
U: Решение задач
Мальчик Антон решает вступительную работу в летний математический лагерь.
В ней \(N\) заданий, которые можно выполнять в произвольном порядке.
Разные задачи требуют разного времени для решения в зависимости от их сложности.
Пусть сложность \(i\)-го задания равна \(T_i\).
Если задание с номером \(i\) выполнять \(j\)-м по счету, Антону потребуется \(T_i\times j\) времени:
чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую,
то потребуется \(T_1\times 1 + T_2\times2\) времени, а если выполнить сначала вторую задачу, а затем первую —
то \(T_2\times 1 + T_1\times2\) . Подскажите Антону, в каком порядке нужно решать задачи,
чтобы на выполнение всей работы ушло как можно меньше времени.
Единственная строка входных данных содержит
\(N\) целых чисел \(T_1\), \(T_2\), ..., \(T_N\) через пробел —
сложности данных задач.
Требуется вывести номера задач в том порядке, в котором их нужно решать,
чтобы уложиться в минимальное время. Если решений несколько, нужно вывести любое из них.
2 3
2 1
IDE
V: Сортировка дробей
В этой задаче вам нужно научиться сортировать не числа, а рациональные дроби.
Программа получает на вход \(N\) дробей: сначала задается число \(N\), потом
идет \(N\) строк, в каждой из которых записана одна дробь. Дробь записана
в виде \(a/b\), где \(a\) и \(b\) —натуральные числа.
Программа должна вывести список этих дробей в порядке неубывания.
Если в списке есть две равные дроби \(a/b=c/d\), то раньше
выводится дробь, у которой меньше числитель.
Указание. Составьте список из кортежей (a / b, a, b).
3
4/2
2/6
1/2
2/6
1/2
4/2
IDE
W: World of tanks
Ваш танк находится на краю поля боя, будем считать, что он стоит в центре координат.
Поле боя простирается на восток и на нем находятся танки противников, которые будем считать
точками с целочисленными координатами. Вы можете стрелять по прямой, и ваши бронебойные заряды уничтожают
все танки противников, находящихся на линии выстрела. Определите, какое наименьшее число выстрелов
необходимо для уничтожения всех танков противника.
Первая строка входных данных содержит количество танков \(N\le 10^5\). Следующие
\(N\) строк содержат по два числа \(x_i\) и \(y_i\) — координаты танков
(\(0\lt x_i\le 10^3\), \(-10^3\le y_i\le 10^3\)).
Программа должна вывести одно число — необходимое количество выстрелов \(K\).
В следующей строке необходимо вывести \(K\) чисел от 1 до \(N\) —
номера танков противника, по котором необходимо произвести выстрелы.
4
1 0
1 -1
2 2
3 3
3
1 2 4
IDE
X: ICPC
На командных олимпиадах по программированию, проводимых по правилам ICPC, команды в турнирной таблице
упорядочены следующим образом:
по количеству решенных задач в порядке убывания.
при равенстве числа решенных задач — по штрафному времени в порядке возрастания.
при равенстве первых двух параметров — по номеру команды в порядке возрастания.
Упорядочите результаты олимпиады по этим правилам.
Первая строка входных данных содержит количество команд \(n\) (\(1\le n\le 100\,000\)),
участвовавших в турнире.
Следующие \(n\) строк содержат результаты команд. В \(i\)-й строке записано два целых числа
\(s_i\) (\(0\le s_i\le 100\)) — количество задач, решенных \(i\)-й командой
и \(t_i\) (\(0\le t_i\le 100\,000\)) — штрафное время \(i\)-й команды.
Программа должна вывести \(n\) чисел от 1 до \(n\) — номера команд в порядке их следования
в турнирной таблице.
5
3 50
5 720
1 7
0 0
8 50
5 2 1 3 4
IDE
Y: Рейтинг кавалеров
Другая симпатичная и предприимчивая девушка ищет себе идеального партнера для танцев.
Идеальный кавалер по ее представлениями должен иметь рост 180 сантиметров,
поэтому прежде всего она хочет найти юношу, чей рост как можно ближе к 180 сантиметрам.
Будет ли кавалер выше или ниже указанной величины, не имеет значения
(то есть юноши с ростом 179 и 181 сантиметр одинаково привлекательны).
Среди всех кандидатов одного роста ей нужен кто-то, чей вес насколько это возможно,
близок к 75 килограмм, но не превышает этой величины. Если же все кандидаты
одного роста весят более 75 килограмм, то девушка выберет самого легкого из них.
Вам дан список кавалеров, содержащий имя партнера, его рост и вес.
Отсортируйте список по критерию привлекательности роста, при равной привлекательности
роста mdash;по привлекательности веса. При одинаковых параметрах роста и веса
список должен быть отсортирован в лексикографическом порядке.
Выведите отсортированный список (только имена кавалеров).
10
George 195 110
Thomas 180 75
John 180 75
James 180 65
Andrew 165 110
Martin 170 70
William 180 77
Franklin 195 70
Benjamin 165 70
Theodore 165 80
John
Thomas
James
William
Martin
Benjamin
Franklin
Theodore
Andrew
George
IDE
Z★: Сортировка масс
Как известно, Россия является одним из ведущих экспортеров нефти.
Разные страны мира, от достаточно больших до сравнительно маленьких,
нуждаются в этой нефти как в воздухе. В ее состав в больших количествах
входят ароматические углеводороды, которые обуславливают ее высокое качество.
Доставка нефти в пункт назначения осуществляется с помощью нефтепровода.
Считается, что количество нефти, отправленное в страну назначения,
равно количеству полученной нефти. На самом деле это, конечно, не так.
Как и многое другое, нефть воруют некоторые несознательные личности.
Причем неофициально считается, что больше нефти воруют в нефтепроводах
тех стран, куда нефти посылается больше (может быть, несознательные
личности считают, что приносят, таким образом, меньше ущерба, кто знает...).
Официальное руководство компании РусскаяНефть решило узнать, правдивый
это слух или нет, чтобы усилить (а может просто установить) охрану
на тех нефтепроводах, где больше всего воруют нефть.
Для этого им нужно отсортировать нефтепроводы по количеству нефти,
которая протекает в направлении какой-то страны за сутки.
У компании РусскаяНефть, как и у любой уважающей себя компании,
есть несколько штатных программистов, и руководство предложило им решить эту,
в сущности, нетрудную задачу. Но программистов поставило в тупик то,
что данные о количестве нефти представлены в разных единицах измерения
(начиная от граммов и заканчивая тоннами).
Поэтому они решили найти человека, который был бы в силах решить
эту задачу за них, и обещают взять его на работу в эту перспективную
и процветающую компанию. Решите задачу, и, кто знает, может, повезет именно Вам?
В первой строке входных данных находится целое число \(N\) (\(1\le N\le 1000\)) —
количество нефтепроводов. В каждой из следующих \(N\) строк находится количество
(точнее — масса) нефти, транспортированной по соответствующему нефтепроводу
за сутки, по одному в строке. Масса нефти задана целым числом от 1 до 10000
с указанием соответствующей единицы измерения. Число и единица измерения разделены ровно одним пробелом.
Единица измерения задается одной из трех букв: g (граммы), p (пуды), t (тонны), причем перед этой буквой
может стоять одна из приставок: m (милли-), k (кило-), M (мега-), G (гига-).
Напомним, что эти приставки обозначают умножение единицы измерения на
10-3, 103, 106 и 109 соответственно.
1 пуд = 16380 граммов, 1 тонна = 106 граммов.
Выведите N строк, в которых должны быть записаны массы нефти в порядке неубывания.
Каждая строка должна описывать массу нефти в одном из нефтепроводов.
Масса должна быть описана согласно формату входного файла.
Единицы измерения масс в выходном файле не обязаны соответствовать
единицам измерения масс во входном файле, главное, чтобы массы
были равны исходным. Все числа в выходном файле, также как
и во входном, должны быть натуральными и не превышать 10000.
5
234 g
4576 mp
2 t
32 mg
2 Mg
32 mg
234 g
4576 mp
2 t
2 t
IDE
ZA★★: Ханойская сортировка
Кто-то перепутал Ханойскую головоломку и разместил диски на первом
стержне не соблюдая правила игры. Переложите эти диски так, чтобы они
оказались на одном из стержней строго в порядке возрастания номеров.
Программа получает на вход число дисков n≤10.
Во второй строке записаны n чисел —
номера дисков на первом стержне сверху вниз.
Перемещать диск можно только в том случае,
если он кладется на диск большего номера.
Выведите последовательность перекладываний,
размещающая диски на любом стержне в порядке возрастания номеров.
Формат вывода одного перекладывания:
A B C, где A номер
перемещаемого диска (1≤A≤n), B —
номер стержня с которого снимается диск, C —
номер стержня на который кладется диск.
