ЛАБОРАТОРНАЯ №3. Динамическое программирование. A. Взрывоопасность. B. Сумма. Формат входных данных. Формат выходных данных. Примеры. C. Возрастающая последовательность

ЛАБОРАТОРНАЯ №3

Динамическое программирование

Input file name:	input. txt
Output file name:	output. txt
Time limit (per test case):	1 sec
Memory limit (per test case):	64 MB
Score:	100 points

A. Взрывоопасность

На одном из секретных заводов осуществляется обработка радиоактивных материалов, в результате которой образуются радиоактивные отходы двух типов: типа А (особо опасные) и типа Б (неопасные). Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых размеров, после чего эти контейнеры укладываются в стопку один над другим для сохранения. Стопка является взрывоопасной, если в ней соседствуют два ящика с отходами типа А.

Требуется написать программу, которая подсчитывает количество возможных вариантов формирования невзрывоопасной стопки из заданного общего числа контейнеров N.

Входные данные: Во входном файле содержится единственное число N (1£ N£ 81).

Выходные данные: В выходной файл необходимо вывести искомое число вариантов.

input. txt	output. txt

B. Сумма

Даны N целых чисел. Найти местоположение подпоследовательности подряд идущих чисел с максимальной суммой.

Формат входных данных

Во входном файле в первой строке записано число N — количество чисел (1≤ N≤ 10000). Во второй строке заданы N целых чисел. Каждое из этих чисел не превышает 256.

Формат выходных данных

В выходной файл выведите два числа — номера первого и последнего элементов найденной подпоследовательности.

Примеры

input. txt	output. txt
0 2 0 4 5 -12 7 -4 9	7 9

C. Возрастающая последовательность

Даны N целых чисел. В заданной последовательности чисел найти возрастающую последовательность максимальной длины.