Processing math: 100%

Задача 8. Гармоническая последовательность

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:sequence.in   Ограничение памяти:256 Мб
Выходной файл:sequence.out  
Максимальный балл:100  

Условие

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел a1,a2,,aN гармоничной, если каждое число, кроме a1 и aN, равно сумме соседних: a2=a1+a3,a3=a2+a4,,aN1=aN2+aN. Например, последовательность [1,2,1,1] является гармоничной, поскольку 2=1+1, и 1=2+(1).

Рассмотрим последовательности равной длины: A=[a1,a2,,aN] и B=[b1,b2,,bN]. Расстоянием между этими последовательностями будем называть величину N(A,B)=|a1b1|+|a2b2|++|aNbN|. Например, d([1,2,1,1],[1,2,0,0])=|11|+|22|+|10|+|10|=0+0+1+1=2.

В конце лекции профессор написал на доске последовательность из N целых чисел B=[b1,b2,,bN] и попросил студентов в качестве домашнего задания найти гармоничную последовательность A=[a1,a2,,aN], такую, что d(A,B) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние d(A,B).

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

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

Первая строка входного файла содержит целое число N — количество элементов в последовательности.

Вторая строка содержит n целых чисел b1,b2,,bN.

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

Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

Ограничения

3N300 000; 109bi109

Пояснения к примеру

В приведенном примере оптимальной является, например, гармоничная последовательность [1,2,1,1].

Описание подзадач и системы оценивания

В этой задаче пять подзадач. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадачи 1, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадачи 1.

Подзадача 1 (14 баллов)

N=3,10bi10

Подзадача 2 (14 баллов)

3N500, 100bi100

Подзадача 3 (16 баллов)

3N100 000, 100bi100

Подзадача 4 (16 баллов)

3N1000, 109bi109

Подзадача 5 (40 баллов)

3N300 000, 109bi109

Получение информации о результатах окончательной проверки

По запросу сообщается баллы за каждую подзадачу.

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

Входной файл (sequence.in) Выходной файл (sequence.out)
1
4
1 2 0 0
2

0.058s 0.008s 13