Задача A. Максимальная подпоследовательность

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

Условие

В последовательности из N чисел выделить подпоследовательность с максимальной суммой элементов.

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

Во входном файле содержится число N за которым следуют N целых чисел xi — элементы последовательности.

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

Выходной файл должен содержать единственное число — значение максимальной суммы.

Ограничения

1 ≤ N ≤ 1000000, 1000 ≤ xi ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 5 -2 5 -2
8

Задача B. Код Хаффмана

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

Условие

Построить код Хаффмана для алфавита из 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. Пилообразная аппроксимация

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

Условие

Последовательность из N целых чисел B[0], B[1], ..., B[N-1] называется пилообразной, если выполняются следующие два условия:

  1. B[i] < B[i+1] для всех четных i от 0 до N-1 включительно.
  2. 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].

Ограничения

  1. Число N от 3 до 100 включительно.
  2. Количество элементов в массиве A равно N.
  3. Каждый элемент массива A от 1 до 1000000000 (один миллиард) включительно.
  4. Количество тестов не превосходит 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

0.054s 0.004s 15