1. Решить задачу о перемножении матриц:
Лимит времени 1000 мс. Лимит памяти 16000 Кб.
Задача. Дана цепочка матриц <A1, A2, …, An>. Нужно расставить в ней скобки так, чтобы минимизировать число элементарных операций умножения элементов, требуемое для перемножения всей цепочки.
Входные данные. В первой строке записано целое число 2 ≤ n ≤ 100 – количество матриц. В следующей строке через пробел записаны n+1 целых чисел p0, p1, …, pn, где 1 ≤ pi ≤ 1000, такие что pi-1×pi – размерность i-й матрицы.
Выходные данные. В единственной строке выведите минимальное количество скалярных умножений, требуемое для перемножения всей цепочки.

2. Решить задачу о наибольшей общей подпоследовательности:
Лимит времени 1000 мс. Лимит памяти 16000 Кб.
Задача. Даны две последовательности целых чисел X = <x1, …, xm> и Y = <y1, y2, …, yn>. Требуется найти самую длинную общую подпоследовательность X и Y.
Входные данные. В первой строке записаны целые числа 1 ≤ m, n ≤ 1000 – длины последовательностей X и Y. В следующих двух строках через пробел записаны m целых чисел -109 ≤ xi ≤ 109 – элементы X – и n целых чисел -109 ≤ yi ≤ 109 – элементы Y.
Выходные данные. В первой строке запишите число k – длину максимальной общей подпоследовательности X и Y. Во вторую строку выведите k целых чисел, входящих в нее. Если таких подпоследовательностей несколько, выведите любую.

3. Решить задачу о наибольшей возрастающей подпоследовательности:
Лимит времени 2000 мс. Лимит памяти 65000 Кб.
Задача. Даны N целых чисел X1, X2, ..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
Выходные данные. В первой строке находится число N. В следующей строке - N чисел Xi через пробел. 1 ≤ N ≤ 10 000; 1 ≤ Xi ≤ 60 000.
Выходные данные. В первой строке выводится количество не вычеркнутых чисел, во второй - сами не вычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.
4. Решить непрерывную задачу о рюкзаке:
Лимит времени 1000 мс. Лимит памяти 16000 Кб.
Задача. Вор во время ограбления магазина обнаружил n мешков с деньгами, золотым песком и драгоценными камнями. Мешок под номером i имеет стоимость vi у.е. и весит wi кг. Вору нужно унести ценности, суммарная стоимость которых была бы как можно большей, однако грузоподъемность его рюкзака ограничивается W кг.
Входные данные. В первой строке записаны целые числа 1 ≤ n ≤ 106 – количество мешков – и 1 ≤ W ≤ 1000 – грузоподъемность рюкзака. В следующих двух строках через пробел записаны n целых чисел 1 ≤ vi ≤ 250 – общая стоимость i-го мешка – и n целых чисел 1 ≤ wi ≤ 250 – общий вес i-го мешка.
Выходные данные. Выведите максимальную суммарную стоимость унесенных ценностей с точностью до 3 знаков.

5. Решить дискретную задачу о рюкзаке:
Лимит времени 1000 мс. Лимит памяти 16000 Кб.
Задача. Вор во время ограбления магазина обнаружил предметы n типов в неограниченном количестве. Предмет под номером i имеет стоимость vi у.е. и весит wi кг. Вору нужно унести предметы, суммарная стоимость которых была бы как можно большей, однако грузоподъемность его рюкзака ограничивается W кг.
Входные данные. В первой строке записаны целые числа 1 ≤ W, n ≤ 1000 – грузоподъемность рюкзака и количество предметов. В следующих двух строках через пробел записаны n целых чисел 1 ≤ wi ≤ 250 – вес i-го предмета – и n целых чисел 1 ≤ vi ≤ 250 – стоимость i-го предмета.
Выходные данные. Выведите одно целое число – максимальную суммарную стоимость предметов.