Problem
Une série de conférences à l'Université de Flatland est consacrée à l'étude des séquences.
Le professeur appelle une suite d'entiers
\(a_1, a_2, ..., a_n\) harmonieux si tous les nombres sauf
\(a_1\) et
\(a_n\), est égal à la somme des éléments adjacents :
\(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Par exemple, la suite [1,2,1,–1] est harmonique car 2=1+1, et 1=2+(–1) .
Considérez des séquences de longueur égale :
\(A=[a_1,a_2, ... a_n]\) et
\(B=[b_1,b_2, ... b_n]\). La distance entre ces séquences sera appelée la valeur
\(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n |\) . Par exemple,
\(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2 | ++|1–0|+|–1–0|=0+0+1+1=2 \)
À la fin du cours, le professeur a écrit au tableau une suite de n entiers
\(B=[b_1,b_2, ... b_n]\)et a demandé aux élèves de trouver une séquence harmonieuse
\(A=[a_1,a_2, ... a_n]\) telle que
\( d( A, B)\) est minimal. Pour se faciliter la tâche, le professeur vous demande d'écrire comme réponse uniquement la distance minimale souhaitée
\(d(A,B)\) .
Il est nécessaire d'écrire un programme qui, étant donné une séquence B, détermine à quelle distance minimale de la séquence B se trouve une séquence harmonique A.
Entrée
La première ligne du fichier d'entrée contient l'entier n – le nombre d'éléments dans la séquence (
\(3 \le n \le 500\)).
La deuxième ligne contient n entiers
\(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .
Mentions légales
Le fichier de sortie doit contenir un seul entier : la distance minimale possible entre la séquence dans le fichier d'entrée et une séquence harmonique.
Exemples
| # |
Entrée |
Sortie |
| 1 |
4
1 2 0 0
| 2 |