Задача A. Максимальная подпоследовательность
Условие
В последовательности из N чисел выделить
подпоследовательность с максимальной суммой элементов.
Формат входного файла
Во входном файле содержится число
N за которым следуют
N целых
чисел
xi — элементы последовательности.
Формат выходного файла
Выходной файл должен содержать единственное число — значение
максимальной суммы.
Ограничения
1 ≤ N ≤ 1000000,
−1000 ≤ xi ≤ 1000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
4 5 -2 5 -2
|
8
|
Задача B. Код Хаффмана
Условие
Построить код Хаффмана для алфавита из N символов и соответствующих им частот
встречаемости.
Формат входного файла
Во входном файле содержится число
N, за которым следуют
N чисел
fi — частота встречаемости
i−го символа.
Формат выходного файла
Выходной файл должен содержать
N строк вида
hi — коды Хаффмана
для символов в порядке, соответствующем входному файлу.
Каждый код должен представлять собой строку из цифр 0 и 1.
Если существует несколько решений, вывести любое из них.
Ограничения
2 ≤ N ≤ 100,
0 ≤ fi ≤ 100000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
6
45
13
12
16
9
5
|
0
101
100
111
1101
1100
|
Задача C. Пилообразная аппроксимация
Условие
Последовательность из N целых чисел B[0], B[1], ..., B[N-1] называется пилообразной, если выполняются следующие два условия:
- B[i] < B[i+1] для всех четных i от 0 до N-1 включительно.
- B[i] > B[i+1] для всех нечетных i от 0 до N-1 включительно.
Вам задана произвольная последовательность из N целых чисел A[0], A[1], ..., A[N-1]. Необходимо как можно
лучше приблизить ее при помощи пилообразной последовательности B[0], B[1], ..., B[N-1]. Степенью приближения
будем считать значение суммы |B[0] - A[0]| + |B[1] - A[1]| + ... + |B[N-1] - A[N-1]|. Лучшим
считается такое приближение, для которого степень приближения является минимальной.
Формат входного файла
Во входном файле содержится число N, затем N чисел - элементы массива A.
Массив целых чисел A описывает исходную последовательность A[0], A[1], ..., A[N-1], пилообразное приближение
которой необходимо найти.
Формат выходного файла
В выходной файл выведите целое число, равное минимальной возможной степени приближения последовательности A[0], A[1], ..., A[N-1] при
помощи пилообразной последовательности B[0], B[1], ..., B[N-1].
Ограничения
- Число N от 3 до 100 включительно.
- Количество элементов в массиве A равно N.
- Каждый элемент массива A от 1 до 1000000000 (один миллиард) включительно.
- Количество тестов не превосходит 50.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
5
1 100 99 101 7
|
0
|
| 2 |
5
101 2 3 1 95
|
195
|
| 3 |
10
1 2 3 4 5 6 7 8 9 10
|
8
|
| 4 |
3
1 1 1
|
1
|
| 5 |
8
257915 131153 654421 649173 247591 85697 736425 80156
|
1341434
|
