Задача A. Наибольшая общая подпоследовательность

Автор:-   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Найдите наибольшую общую подпоследовательность двух строк.

Формат входного файла

В первой строке находится первая строка, во второй строке находится вторая строка. Строки состоят только из маленьких латинских букв.

Формат выходного файла

Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.

Ограничения

Длина каждой строки не менее 1 и не превосходят 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
ababaca
acaba
aaba


Задача B. Свинья-копилка

Автор:А. Кленин, краевая олимпиада 2001 г.   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела. Как известно, количество денег в копилке можно определить, только разбив ее. Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.

Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.

Дано 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. Наибольшая возрастающая подпоследовательность

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Дана последовательность из 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

Author:A. Klenin   Time limit:3 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

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:

  1. the first and the last aquariums should be left in their places;
  2. 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. Коммивояжёр возвращается!

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!

Как обычно, коммивояжёр хочет минимизировать транспортные расходы. Он выбирает начальную планету, прилетает туда на межгалактическом корабле, после чего посещает все остальные планеты системы в порядке, минимизирующем суммарную стоимость посещения, и на другом межгалактическом корабле улетает обратно. Естественно, коммивояжёр не хочет летать ни на какую планету дважды.

Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!

Формат входного файла

В системе Альфы Центавра 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

0.063s 0.003s 21