2007_ШЕА: Двумерная динамика

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

Профессор называет последовательность целых чисел \(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\).