Задача A. Knapsack problem ≡

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

Условие

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

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

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

Условие

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

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

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

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

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

Ограничения

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

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

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

aaba

Problem C. 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

Задача D. Домино (классика) ≡

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

Условие

Найти количество способов замостить домино 1 × 2 поле n × m.

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

Во входном файле содержатся числа n и m.

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

В выходной файл выведите ответ.

Ограничения

1 ≤ n ≤ 16;

1 ≤ m ≤ 10;

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2 3
 
3
0.037s 0.005s 13