--->
55 задач
<---
Источники
Отсортируйте данный массив, используя сортировку слиянием.
Первая строка входных данных содержит количество элементов в массиве N, N ≤ 105. Далее идет N целых чисел, не превосходящих по абсолютной величине 109.
Выведите эти числа в порядке неубывания.
2 3 1
1 3
В правильном N-угольнике провели некоторые диагонали так, что он оказался разбит на треугольники. Изначально стороны N-угольника и все его диагонали черные.
Разрешается выбрать четырехугольник, в котором ровно одна диагональ, и при этом эта диагональ черного цвета (сам четырехугольник не обязан быть полностью черным) и проделать с ним следующее: заменить диагональ на противоположную (т.е. если сам четырехугольник был ABCD и в нем была диагональ AC, то она меняется на диагональ BD), после чего перекрасить стороны этого четырехугольника и новую диагональ в красный цвет.
Требуется определить, можно ли с помощью таких операций сделать так, чтобы все отрезки (т.е. стороны N-угольника и изображенные диагонали) стали красными, и не осталось бы ни одного черного отрезка. А если это возможно, то какое минимальное количество операций для этого требуется.
Вводится сначала число N (3≤N≤30000). Далее идет описание N–3 проведенных диагоналей. Каждая диагональ описывается двумя натуральными числами — номерами вершин, которые она соединяет. Гарантируется, что проведенные диагонали внутри N-угольника не пересекаются.
Выведите минимальное число действий, необходимое для того, чтобы перекрасить весь N-угольник и все его диагонали. Если перекрасить многоугольник указанным способом невозможно, выведите одно число –1 (минус один).
Примеры
| Входные данные | Выходные данные |
| 3 | –1 |
| 4 1 3 | 1 |
Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).
Напишите программу, которая для каждой пары последовательностей выведет левую медиану их объединения.
Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются последовательности. Каждая последовательность состоит из L чисел, по модулю не превышающих 30000.
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N‑1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.
Пример
Входные данные 3 6 1 4 7 10 13 16 0 2 5 9 14 20 1 7 16 16 21 22 Выходные данные 7 10 9
На склад привезли много пустых ящиков разного размера. Известно, что их все можно сложить один в один (то есть так, что каждый следующий помещается в предыдущий). Требуется определить, в какой последовательности они будут вложены друг в друга. Один ящик вкладывается в другой, если он меньше по объему.
В первой строке вводится количество ящиков – натуральное число, не превышающее 100. В следующих строках вводятся размеры ящиков: в каждой строке вводятся три натуральных числа, не превышающие 101 – размеры очередного ящика.
Требуется вывести ящики от внутреннего к внешнему.Про каждый вывести в отдельной строке его размеры в том же порядке, в котором они были указаны при вводе.
3 2 2 2 2 1 2 1 1 1
1 1 1 2 1 2 2 2 2
2 100 100 100 101 1 1
101 1 1 100 100 100
У свинофермера Васи есть свиноферма рядом с городом М. Он решил навестить своего друга в городе С.-П. По дороге из М. в С.-П. расположено N городов, в которых свинина пользуется стабильным спросом. Вася решил совместить приятное с полезным и заработать немного денег. Он взял с собой \(N\) свиней и решил продавать по одной свинье в каждом из городов.
Цены на свиней в разных городах разные. В \(j\)-ом городе за один килограмм живого веса платят \(P_j\) рублей. Расстояние до \(j\)-го города по дороге из М. в С.-П. равно \(D_j\) километров.
Васины свиньи имеют разные веса. Перевозка одного килограмма свиньи на один километр обходится в \(T\) рублей.
Помогите Васе определить, каких свиней и в каком порядке нужно продавать, чтобы заработать побольше денег.
Первая строка входного файла содержит числа \(N (1 ≤ N ≤ 1000)\) и \(T (1 ≤ T ≤ 10^9)\). Вторая строка содержит \(N\) чисел \(W_i\), задающих вес Васиных свиней \((1 ≤ W_i ≤ 10^9)\). Третья строка содержит \(N\) чисел \(D_i\), задающих расстояния до города \(i\) от \(М (1 ≤ D_i ≤ 10^9)\). Четвертая строка содержит \(N\) чисел \(P_i\), задающих цены в городах \((1 ≤ P_i ≤ 10^9)\). Все числа целые.
Выведите \(N\) чисел. \(j\)-ое число должно быть номером свиньи, которую следует продать в \(j\)-ом городке. Свиньи нумеруются с \(1\) в том порядке, как они перечислены во входном файле.
3 1 10 20 15 10 20 30 50 70 60
3 2 1