Задача A. k-я порядковая статистика
Условие
K-й порядковой статистикой N-элементного массива называется число Аk,
которое будет стоять на K-м месте после сортировки этого массива
по возрастанию.
Формат входного файла
Входной файл содержит числа
N K, за которыми следуют
N чисел — массив для которого следует подсчитать
K-ю порядковую
статистику.
Формат выходного файла
Выходной файл должен содержать
K-ю порядковую статистику исходного
массива.
Ограничения
1 ≤ N ≤ 106,
1 ≤ K ≤ N,
−231 ≤ Ai ≤ 231−1
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 2
2 3 1
|
2
|
Задача B. Наибольшая возрастающая подпоследовательность
Условие
Дана последовательность из N целых чисел. Найдите любую из ее наибольших
строго возрастающих подпоследовательностей.
Формат входного файла
Во входном файле находится число
N, а за ним следует последовательность
ai из
N целых чисел.
Формат выходного файла
В выходной файл выведите длину найденной наибольшей возрастающей подпоследовательности,
а затем номера входящих в нее элементов в порядке возрастания.
Ограничения
1 ≤ N ≤ 100000;
−109 ≤ ai ≤ 109
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
5
123 456 124 124 125
|
3
1 4 5
|
Задача C. Knapsack problem
Условие
Дана последовательность из
N целых чисел. Найдите любую из ее подпоследовательностей,
сумма элементов которой равна
w, либо установите,
что искомой подпоследовательности не существует.
Формат входного файла
Во входном файле находятся числа
N и
w, а за ними следует последовательность
из
N целых чисел
ai.
Формат выходного файла
Если искомая подпоследовательность существует, выведите
N чисел 0 или 1, разделенных пробелами.
Единица на позиции
i означает, что элемент последовательности
ai принадлежит найденной
подпоследовательности, 0 означает обратное. В противном случае выведите
−1.
Ограничения
1 ≤ N ≤ 40,
0 ≤ ai,w ≤ 10000000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 7
1 5 6
|
1 0 1
|
