Модуль: Линейный перебор


Задача

4 /5


Гармоничная последовательность lite - 1

Задача

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

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1]  является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\)   и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

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

Входные данные
Первая строка содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 100\)).
Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .

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



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Python9
Комментарий учителя