Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 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 |
|
|