В этой задаче вам нужно реализовать любую из пройденных сортировок, работающих за время $O(n\log n)$. Использовать встроенные в язык сортировки и структуры данных запрещается.

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

В первой строке содержится число $n$ $(1⩽n⩽100000)$ — количество элементов в массиве. Во второй строке находятся $n$ целых чисел, по модулю не превосходящих ${10}^9$.

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

Входные данные

10
1 8 2 1 4 7 3 2 3 6

Выходные данные

1 1 2 2 3 3 4 6 7 8

А в этой задаче вам нужно реализовать сортировку подсчетом. Использовать другие сортировки запрещается.

Дан массив из $n$ элементов, которые принимают целые значения от 0 до 100. Отсортируйте этот массив в порядке неубывания элементов.

В первой строке содержится число $n$ $(1⩽n⩽200000)$ — количество элементов в массиве. Во второй строке находятся n целых чисел, от 0 до 100 каждое.

Выведите отсортированный массив.

Входные данные

5
7 3 4 2 5

Выходные данные

2 3 4 5 7

Напишите программу, которая для заданного массива $A=⟨a_1,a_2,\dots ,a_n⟩$ находит количество пар $(i,j)$ таких, что $i<j$ и $a_i>a_j$.

Первая строка входного файла содержит натуральное число $n$ $(1⩽n⩽500000)$ — количество элементов массива. Вторая строка содержит $n$ попарно различных элементов массива $A$ $(0⩽a_i⩽{10}^6)$.

В выходной файл выведите одно число — ответ на задачу.

Входные данные

4
1 2 4 5

Выходные данные

0

Входные данные

4
5 4 2 1

Выходные данные

6

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

• Insert(X) — добавить в Heap число $X$;
• Extract — достать из Heap наибольшее число (удалив его при этом).

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

Во входном файле записано количество команд $n$ $(1⩽n⩽100000)$, потом последовательность из $n$ команд, каждая в своей строке.

Каждая команда имеет такой формат: 0 <число> или 1, что означает соответственно операции Insert(<число>) и Extract. Добавляемые числа находятся в интервале от $1$ до ${10}^7$ включительно.

Гарантируется, что при выполнении команды Extract в структуре находится по крайней мере один элемент.

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

Входные данные

7
0 100
0 10
1
0 5
0 30
0 50
1

Выходные данные

100
50

Дан массив из $n$ целых чисел. Все числа от $-{10}^9$ до ${10}^9$.

Нужно уметь отвечать на запросы вида «Cколько чисел имеют значения от $l$ до $r$»?

Число $n$ $(1⩽n⩽{10}^5$). Далее $n$ целых чисел.

Затем число запросов $k$ $(1⩽k⩽{10}^5)$.

Далее $k$ пар чисел $l,r$ $(-{10}^9⩽l⩽r⩽{10}^9)$ — собственно запросы.

Выведите $k$ чисел — ответы на запросы.

Входные данные

5
10 1 10 3 4
4
1 10
2 9
3 4
2 2

Выходные данные

5 2 2 0

Даны два массива. Первый массив отсортирован по неубыванию, второй массив содержит запросы — целые числа.

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

В первой строке входных данных содержатся числа $n$ и $k$ $(0<n,k⩽{10}^5)$. Во второй строке задаются $n$ чисел первого массива, отсортированного по неубыванию, а в третьей строке — $k$ чисел второго массива. Каждое число в обоих массивах по модулю не превосходит $2\cdot {10}^9$.

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

Входные данные

5 5
1 3 5 7 9
2 4 8 1 6

Выходные данные

1
3
7
1
5

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще $n$ копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за $x$ секунд, а другой — за $y$. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

На вход программы поступают три натуральных числа $n$, $x$ и $y$, разделенные пробелом $(1⩽n⩽2\cdot {10}^8,1⩽x,y⩽10)$.

Выведите одно число — минимальное время в секундах, необходимое для получения $n$ копий.

Входные данные

4 1 1

Выходные данные

3

Входные данные

5 1 2

Выходные данные

4

Найдите такое число $x$, что $x^2+\sqrt{x}$, с точностью не менее 6 знаков после точки.

В единственной строке содержится вещественное число $1.0⩽C⩽{10}^{10}$.

Выведите одно число — искомый $x$.

Входные данные

2.0000000000

Выходные данные

1.0

Входные данные

18.0000000000

Выходные данные

4.0

Маленький мальчик Ферма́ живет в деревне. Наступают холодные времена, поэтому бабушка попросила мальчика сходить в лес, чтобы собрать дров. В лесу около деревни, в которой живет Ферма, находится волшебная Поляна Дров, на которой всегда лежат дрова, и никогда не кончаются. Естественно, Ферма должен пойти именно туда.

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

• Деревня находится в точке с координатами $(0,1)$.
• Поляна находится в точке с координатами $(1,0)$.
• Граница между лесом и полем — горизонтальная прямая $y=a$, где $a$ — некоторое число $(0⩽a⩽1)$.
• Скорость передвижения по полю составляет $V_p$, скорость передвижения по лесу — $V_f$. Вдоль границы можно двигаться как по лесу, так и по полю.

Найдите точку, в которой мальчик Ферма должен войти в лес, чтобы дойти до Поляны Дров как можно быстрее.

В первой строке входного файла содержатся два положительных целых числа — $V_p$ и $V_f$ $(1⩽V_p,V_f⩽{10}^5)$. Во второй строке содержится единственное вещественное число — координата по оси $O_y$ границы между лесом и полем $a$ $(0⩽a⩽1)$

В единственной строке выходного файла выведите вещественное число с точностью не менее 4 знаков после запятой — координата по оси $O_x$ точки, в которой мальчик Ферма должен войти в лес.

Входные данные

5 3
0.4

Выходные данные

0.783310604

У Демьяны есть $n$ драгоценностей. Каждая из драгоценностей имеет ценность $v_i$ и вес $w_i$. С тех пор, как её мужа Джонни уволили в связи с последним финансовым кризисом, Демьяна решила продать несколько драгоценностей. Для себя она решила оставить лишь $k$ лучших. Лучших в смысле максимизации достаточно специфического выражения: пусть она оставила для себя драгоценности номер $i_1,i_2,\dots ,i_k$, тогда максимальной должна быть величина

$$\frac{\sum _{j=1}^k{v}_{i_j}}{\sum _{j=1}^k{w}_{i_j}}$$

Помогите Демьяне выбрать $k$ драгоценностей требуемым образом.

На первой строке $n$ и $k$ $(1⩽k⩽n⩽100000)$.

Следующие $n$ строк содержат пары целых чисел $v_i$, $w_i$ $(0⩽v_i⩽{10}^6,$ $1⩽w_i⩽{10}^6)$, сумма всех $v_i$ не превосходит ${10}^7$, сумма всех $w_i$ также не превосходит ${10}^7)$.

Выведите $k$ различных чисел от $1$ до $n$ — номера драгоценностей. Драгоценности нумеруются в том порядке, в котором перечислены во входных данных. Если есть несколько оптимальных ответов, выведите любой.

Входные данные

3 2
1 1
1 2
1 3

Выходные данные

1
2

Дан массив из $n$ положительных целых чисел. Нужно разбить его на $k$ отрезков так, чтобы максимальная сумма на отрезке была минимально возможной.

Первая строка содержит целые числа $n$ и $k$ $(1⩽k⩽n⩽{10}^5)$. Вторая строка содержит элементы массива $a_i$ $(1⩽a_i⩽{10}^9)$.

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

Входные данные

10 4
1 3 2 4 10 8 4 2 5 3

Выходные данные

12

Петя составил таблицу умножения размера $n\times n$. Ячейка в $i$-й строке и $j$-м столбце содержит значение $i\cdot j$. Петю заинтересовал вопрос: какое число в таблице является $k$-м по возрастанию? Помогите Пете ответить на этот вопрос.

Ввод содержит два целых числа $n$ и $k$ $(1⩽n⩽{10}^5,1⩽k⩽n^2)$.

Выведите одно число — $k$-е число по возрастанию в таблице.

Входные данные

3 4

Выходные данные

3

Входные данные

5 16

Выходные данные

10

Есть два массива $a$ и $b$, каждый из которых состоит из $n$ чисел. Для каждой пары чисел $(i,j):1⩽i,j⩽n$ выпишем сумму чисел $a_i+b_j$. Найдите в полученном множестве сумм $k$-ю по возрастанию.

Первая строка содержит целые числа $n$ и $k$ $(1⩽n⩽{10}^5,1⩽k⩽n^2)$. Вторая строка содержит элементы массива $a$, третья строка содержит элементы массива $b$. Все элементы массивов — целые положительные числа, не больше ${10}^9$.

Выведите одно число — искомая $k$-я сумма.

Входные данные

5 10
4 2 6 4 8
7 3 1 9 5

Выходные данные

9