Отсортируйте данный массив, используя быструю сортировку.
Первая строка входных данных содержит количество элементов в массиве \(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 |
Дано \(N\) предметов массой \(m_1, \ldots, m_N\) и стоимостью \(c_1, \ldots, c_N\) соответственно.
Ими наполняют рюкзак, который выдерживает вес не более \(M\). Определите набор предметов, который можно унести в рюкзаке, имеющий наибольшую стоимость.
В первой строке вводится натуральное число \(N\), не превышающее \(100\) и натуральное число \(M\), не превышающее \(10000\).
Во второй строке вводятся \(N\) натуральных чисел \(m_i\), не превышающих \(100\).
Во третьей строке вводятся \(N\) натуральных чисел \(с_i\), не превышающих \(100\).
Выведите номера предметов (числа от \(1\) до \(N\)), которые войдут в рюкзак наибольшей стоимости.
| Ввод | Вывод |
|---|---|
4 6 2 4 1 2 7 2 5 1 |
1 3 4 |
В дощечке в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
В первой строке входных данных записано число \(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 |
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каж дого номинала неограничен. Помогите Национальному банку решить эту задачу.
Первая строка входных данных содержит натуральное число \(N\) не превосходящее \(100\) — количество номиналов банкнот в обращении. Вторая строка входных данных содержит \(N\) различных натуральных чисел \(x_1, x_2, \ldots, x_N\), не превосходящих \(10^{6}\) — номиналы банкнот. Третья строчка содержит натуральное число \(S\), не превосходящее \(10^6\) —сумму, которую необходимо выдать.
Программа должна найти представление числа \(S\) виде суммы слагаемых из множества \(x_i\), содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку No solution.
| Ввод | Вывод |
|---|---|
5 1 3 7 12 32 40 |
32 7 1 |