Отсортируйте данный массив, используя быструю сортировку.
Первая строка входных данных содержит количество элементов в массиве \(N\) (\(N \leq 10^5\)). Далее идет \(N\) целых чисел, не превосходящих по абсолютной величине \(10^9\).
Выведите эти числа в порядке неубывания.
| Ввод | Вывод |
|---|---|
2 3 1 |
1 3 |
Дано \(n\) отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат. Точка \(x\) считается принадлежащей отрезку с концами \(a\) и \(b\) , если выполняется двойное неравенство \(\min(a, b) \leq x \leq \max(a, b)\).
Первая строка содержит два целых числа \(n \ (1 \leq n \leq 10^5)\) – число отрезков и \(m \ (1 \leq m \leq 10^5 )\) – число точек. В следующих \(n\) строках по два целых числи \(a_i\) и \(b_i\) – координаты концов соответствующего отрезка(например, может быть пара 5 2). В последней строке \(m\) целых чисел – координаты точек. Все числа по модулю не превосходят \(10^9\).
В выходной файл выведите \(m\) чисел – для каждой точки количество отрезков, в которых она содержится.
| Ввод | Вывод |
|---|---|
3 2 0 5 -3 2 7 10 1 6 |
2 0 |
1 3 -10 10 -100 100 0 |
0 0 1 |
Ошибка при обработке input/output_format: [Errno 2] No such file or directory: '/home/judges/problems/algorithms/knapsack/informatics-003090-knapsack/statement.xml'
Ошибка при обработке примеров: [Errno 2] No such file or directory: '/home/judges/problems/algorithms/knapsack/informatics-003090-knapsack/statement.xml'
В дощечке в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
В первой строке входных данных записано число \(N\) - количество гвоздиков \((2 \le N \le 100)\). В следующей строке заданы \(N\) чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
Выведите единственное число - минимальную суммарную длину всех ниточек.
| Ввод | Вывод |
|---|---|
5 4 10 0 12 2 |
6 |
Черепаха хочет переползти из левого верхнего угла поля размером \(N\) на \(M\) клеток (\(2 \leq N,M \leq 1000\)) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Кроме того, проходя через каждую клетку, Черепаха получает (или теряет) несколько золотых монет (это число известнодля каждой клетки).
Определите, какое максимальное количество монет может собрать Черепаха по пути и как ей нужно идти для этого.
В первой строке вводятся два натуральных числа: \(N\) и \(M ( 2 \leq N,M \leq 1000 )\), разделённые пробелом. В каждой из следующих \(N\) строк записаны через пробел по \(M\) чисел, которые обозначают количество монет, получаемых Черепашкой при проходе через каждую клетку. Если это число отрицательное, Черепашка теряет монеты.
В первой строке программа должна вывести наибольшее количество монет, которое может собрать Черепаха. Во второй строке без пробелов выводятся команды, которые нужно выполнить Черепахе: буква 'R' (от слова right) обозначает шаг вправо, а буква 'D' (от слова down) – шаг вниз. Если ответов несколько, выведите самый нижний маршрут.
| Ввод | Вывод |
|---|---|
3 3 0 2 -3 2 -5 7 1 2 0 |
6 RRDD |
Лесенкой называется набор кубиков, в котором каждый горизонтальный слой содержит меньше кубиков, чем слой под ним.
|
|
|
|
|||||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
Подсчитать количество различных лесенок, которые могут быть построены из \(N\) кубиков.
Вводится одно число \(N (1 \leq N \leq 150)\).
Выведите искомое количество лесенок.
| Ввод | Вывод |
|---|---|
3 |
2 |
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.
В первой строке входных данных содержится число \(N\) – длина первой последовательности \((1 \leq N \leq 10^3)\). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие \(10^4\) по модулю.
В третьей строке записано число \(M\) – длина второй последовательности \((1 \leq M \leq 10^3)\). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие \(10^4\) по модулю.
Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.
| Ввод | Вывод |
|---|---|
3 1 2 3 3 2 3 1 |
2 3 |
3 1 2 3 3 3 2 1 |
1 |
Дана последовательность, требуется найти её наибольшую возрастающую подпоследовательность.
В первой строке входных данных задано число \(N\) - длина последовательности \((1 \leq N \leq 10^3)\). Во второй строке задается сама последовательность (разделитель - пробел). Элементы последовательности - целые числа, не превосходящие \(10^4\) по модулю.
Требуется вывести наибольшую возрастающую подпоследовательность данной последовательности. Если таких подпоследовательностей несколько, необходимо вывести одну (любую) из них.
| Ввод | Вывод |
|---|---|
6 3 29 5 5 28 6 |
3 5 28 |
10 4 8 2 6 2 10 6 29 58 9 |
4 8 10 29 58 |
Числовая последовательность задана рекуррентной формулой: \(a_{i+1} = k \cdot a_i + b \mod m\). Найдите длину её наибольшей возрастающей подпоследовательности.
Программа получает на вход пять целых чисел: длину последовательности \(n\) \((1 \leq n \leq 10^5)\), начальный элемент последовательности \(a_1\), параметры \(k\), \(b\), \(m\) для вычисления последующих членов последовательности \((1 \leq m \leq 10^4)\), \(0 \leq k \lt m\), \(0 \leq b \lt m, 0 \leq a_1 \lt m\)).
Требуется вывести наибольшую возрастающую подпоследовательность данной последовательности, разделяя числа пробелами. Если таких последовательностей несколько, необходимо вывести одну (любую) из них.
| Ввод | Вывод |
|---|---|
5 41 2 1 100 |
41 67 71 |
7 1 2 1 10 |
1 3 5 7 |
Ошибка при обработке input/output_format: [Errno 2] No such file or directory: '/home/judges/problems/algorithms/knapsack/informatics-003087-atm/statement.xml'
Ошибка при обработке примеров: [Errno 2] No such file or directory: '/home/judges/problems/algorithms/knapsack/informatics-003087-atm/statement.xml'