Задача A. Наибольшая возрастающая подпоследовательность
Условие
Дана последовательность из 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
|
Problem B. Longest Ordered Subsequence
Statement
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ., aN) be any sequence (ai1, ai2, ., aiK), where 1 ≤ i1 < i2 < ... < iK ≤ N. For example, the sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences of this sequence are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
Input file format
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces.
Output file format
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.
Constraints
1 ≤ N ≤ 1000
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
7
1 7 3 5 9 4 8
|
4
|
Задача C. Свинья-копилка
Условие
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано
E — вес пустой копилки,
F — вес копилки с монетами,
N — количество достоинств монет,
Ci и
Wi — достоинство и вес каждого вида монет (
1 ≤ i ≤ N).
Требуется определить минимальную сумму, которая может содержаться в копилке.
Формат входного файла
В первой строке входного файла содержатся числа E F N.
В следующих N строках находятся по два числа — Ci Wi.
Все числа во входном файле — целые.
Формат выходного файла
В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке.
Если заданный вес копилки F не может быть достигнут с монетами заданного типа,
то в выходной файл следует записать число −1.
Ограничения
1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100
1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
10 110 2
1 1
30 50
|
60
|
| 2 |
10 110 2
1 1
50 30
|
100
|
| 3 |
1 6 2
10 3
20 4
|
-1
|
Задача D. 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
|
