Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 2 сек | |
Входной файл: | sequence.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | sequence.out | |||
Максимальный балл: | 100 |
Цикл лекций в университете Флатландии посвящен изучению последовательностей.
Профессор называет последовательность целых чисел a1,a2,…,aN гармоничной, если каждое число, кроме a1 и aN, равно сумме соседних: a2=a1+a3,a3=a2+a4,…,aN−1=aN−2+aN. Например, последовательность [1,2,1,−1] является гармоничной, поскольку 2=1+1, и 1=2+(−1).
Рассмотрим последовательности равной длины: A=[a1,a2,…,aN] и B=[b1,b2,…,bN]. Расстоянием между этими последовательностями будем называть величину N(A,B)=|a1−b1|+|a2−b2|+⋯+|aN−bN|. Например, d([1,2,1,−1],[1,2,0,0])=|1−1|+|2−2|+|1−0|+|−1−0|=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.
Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.
3≤N≤300 000; −109≤bi≤109
В приведенном примере оптимальной является, например, гармоничная последовательность [1,2,1,−1].
В этой задаче пять подзадач. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.
Внимание! Тест из примера не подходит под ограничения для подзадачи 1, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадачи 1.
N=3,−10≤bi≤10
3≤N≤500, −100≤bi≤100
3≤N≤100 000, −100≤bi≤100
3≤N≤1000, −109≤bi≤109
3≤N≤300 000, −109≤bi≤109
По запросу сообщается баллы за каждую подзадачу.
№ | Входной файл (sequence.in ) |
Выходной файл (sequence.out ) |
---|---|---|
1 |
|
|