Задача A. Наибольшая общая подпоследовательность
Условие
Найдите наибольшую общую подпоследовательность двух строк.
Формат входного файла
В первой строке находится первая строка, во второй строке находится вторая строка.
Строки состоят только из маленьких латинских букв.
Формат выходного файла
Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.
Ограничения
Длина каждой строки не менее 1 и не превосходят 1000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
ababaca
acaba
|
aaba
|
Задача B. Свинья-копилка
Условие
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано
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
|
Задача C. Наибольшая возрастающая подпоследовательность
Условие
Дана последовательность из 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 D. Hall of water life
Statement
The main hall of the Nearsea Institute of Unspecified Underwater Studies
has a shape of a long corridor.
Along the corridor, there are N aquariums exhibiting various
sea creatures. Aquariums are located at distances x1, …, xN
from the hall entrance (xi < xi + 1).
The institute has recently got a new director, who decided that
the aquarium maintenance is too costly, and issued an order to remove
M (0 ≤ M ≤ N − 2) aquariums.
To minimize the disruption to the looks of the hall, it was decided that:
- the first and the last aquariums should be left in their places;
- the maximum distance between the adjacent aquariums must be as small as possible.
Your program must select aquariums for removal in such a way that the above conditions are
satisfied.
Input file format
Input file contains integers N M followed by N integers xi.
Output file format
Output file should contain a single integer — the smallest possible maximum distance.
Constraints
2 ≤ N ≤ 400,
1 ≤ xi ≤ 109,
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
5 2
1 2 3 4 5
|
2
|
| 2 |
4 1
10 21 30 40
|
19
|
Задача E. Коммивояжёр возвращается!
Условие
Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!
Как обычно, коммивояжёр хочет минимизировать транспортные расходы. Он выбирает начальную планету, прилетает туда на межгалактическом корабле, после чего посещает все остальные планеты системы в порядке, минимизирующем суммарную стоимость посещения, и на другом межгалактическом корабле улетает обратно. Естественно, коммивояжёр не хочет летать ни на какую планету дважды.
Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!
Формат входного файла
В системе Альфы Центавра n планет. Это число записано в первой строке входного файла. Следующие n строк содержат по n чисел каждая: j-ое число на i-ой из этих строк — стоимость перемещения aij от i-ой планеты до j-ой. Числа в каждой строке разделены пробелами. aij = -1
означает, что из планеты i нельзя на прямую добраться до планеты j.
Формат выходного файла
Выходной файл должен содержать единственное целое число — длину оптимального пути. Если не существует пути проходящего через все планеты, вывести -1.
Ограничения
1 ≤ n ≤ 19, aij ≤ 108
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
-1 1 6
3 -1 7
4 9 -1
|
5
|
| 2 |
4
-1 1 1 1
1 -1 1 1
1 1 -1 1
1 1 1 -1
|
3
|
