A: Два ближайших числа

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

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

Первая строка входных данных содержит количество чисел \(n\), вторая строка содержит \(n\) целых неотрицательных чисел, не превосходящих \(10^9\).

Используйте встроенную сортировку. Решение должно иметь сложность встроенной сортировки + O(n).

4
9 4 1 6

4 6

B: Строительство магазина

В некотором городе на прямой улице расположено \(n\) домов. \(i\)-й дом задан неотрицательной величиной \(x_i\) — расстоянием от начала улицы до дома, таким образом, расстояние между двумя домами \(i\) и \(j\) равно \(|x_i-x_j|\).

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

Программа получает на вход список различных неотрицательных чисел (сначала — количество чисел, затем сами числа) — координаты домов и должна вывести координату дома, в котором необходимо открыть магазин.

4
1 2 3 4

2

C: Скидки

В супермаркете проводится беспрецедентная акция – «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».

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

Программа получает на вход число N (1≤N≤1000), а затем N чисел – стоимости выбранных Васей товаров. Все стоимости – натуральные числа, не превышающие 10000.

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

6
1 5 4 3 5 7

19

5
3 15 25 8 8

51

D: Свадьбы

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

Первая строка входных данных содержит число \(N\). Вторая строка входных данных содержит \(N\) чисел \(X_1\), ..., \(X_N\) — размеры состояний поклонников. Третья строка содержит одно число \(Y\) — состояние девушки.

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

2
5 10
5

7.5

3
1 3 2
0

2.125

1
1
2

2.0

E: Выборы в США

Президент в США выбирается коллегией выборщиков в результате непрямых выборов. Рассмотрим упрощенную модель таких выборов.

Все избиратели делятся на \(K\) групп (необязательно равных по численности), каждая группа имеет одного представителя в коллегии выборщиков. Сначала в каждой группе проводится голосование по поставленному вопросу, если строго более половины избирателей группы высказывается “за”, то представитель этой группы в коллегии выборщиков голосует ”за“ от имени всей группы. Решение принимается, если строго более половины выборщиков (то есть групп) проголосовали “за”.

При такой системе решение может быть принято коллегией выборщиков, даже если “за” высказалось менее половины от общего числа избирателей.

Программа получает на вход число \(K\), затем \(K\) чисел — размеры групп.

Программа должна вывести минимальное количество избирателей, которое могло проголосовать “за”, если в итоге решение было принято коллегией выборщиков.

3
5 5 7

6

5
4 2 1 3 7

5

F: Коньки

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

Первая строка содержит число \(N\) — количество коньков (\(0\le N\le 10^5\)). Вторая строка содержит \(N\) натуральных чисел — размеры коньков. Третья строка содержит число \(M\) — количество школьников (\(0\le M\le 10^5\)). Четвертая строка содержит \(M\) натуральных чисел — размеры ног школьников.

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

4
41 40 39 42
3
42 41 42

2

G: Личные дела

Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.

В первой строке входных данных записано число \(N\) (\(1 \le N \le 1000\)) – количество личных дел. Далее записано \(N\) строк, каждая из которых состоит из фамилии учащегося (строка без пробелов) и номера класса (целое число от 1 до 11).

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

Указание: составьте список из кортежей: номер класса и фамилия участника.

3
Ivanov 10
Petrov 9
Sidorov 9

9 Petrov
9 Sidorov
10 Ivanov

H: Сортировка дробей

В этой задаче вам нужно научиться сортировать не числа, а рациональные дроби. Программа получает на вход \(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

I: Рейтинг кавалеров

Другая симпатичная и предприимчивая девушка ищет себе идеального партнера для танцев.

Идеальный кавалер по ее представлениями должен иметь рост 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

J: Сортировка масс

Как известно, Россия является одним из ведущих экспортеров нефти. Разные страны мира, от достаточно больших до сравнительно маленьких, нуждаются в этой нефти как в воздухе. В ее состав в больших количествах входят ароматические углеводороды, которые обуславливают ее высокое качество. Доставка нефти в пункт назначения осуществляется с помощью нефтепровода. Считается, что количество нефти, отправленное в страну назначения, равно количеству полученной нефти. На самом деле это, конечно, не так. Как и многое другое, нефть воруют некоторые несознательные личности. Причем неофициально считается, что больше нефти воруют в нефтепроводах тех стран, куда нефти посылается больше (может быть, несознательные личности считают, что приносят, таким образом, меньше ущерба, кто знает...). Официальное руководство компании РусскаяНефть решило узнать, правдивый это слух или нет, чтобы усилить (а может просто установить) охрану на тех нефтепроводах, где больше всего воруют нефть.

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

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

В первой строке входных данных находится целое число \(N\) (\(1\le N\le 1000\)) — количество нефтепроводов. В каждой из следующих \(N\) строк находится количество (точнее — масса) нефти, транспортированной по соответствующему нефтепроводу за сутки, по одному в строке. Масса нефти задана целым числом от 1 до 10000 с указанием соответствующей единицы измерения. Число и единица измерения разделены ровно одним пробелом. Единица измерения задается одной из трех букв: g (граммы), p (пуды), t (тонны), причем перед этой буквой может стоять одна из приставок: m (милли-), k (кило-), M (мега-), G (гига-). Напомним, что эти приставки обозначают умножение единицы измерения на 10^-3, 10³, 10⁶ и 10⁹ соответственно. 1 пуд = 16380 граммов, 1 тонна = 10⁶ граммов.

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

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

5
234 g
4576 mp
2 t
32 mg
2 Mg

32 mg
234 g
4576 mp
2 t
2 t