Problem
Allo studio delle successioni è dedicato un ciclo di lezioni all'Università di Flatlandia.
Il professore chiama una sequenza di numeri interi
\(a_1, a_2, ..., a_n\) armoniosa se ogni numero tranne
\(a_1\) e
\(a_n\), è uguale alla somma di adiacente:
\(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Ad esempio, la sequenza [1,2,1,–1] è armonica perché 2=1+1 e 1=2+(–1) .
Considera sequenze di uguale lunghezza:
\(A=[a_1,a_2, ... a_n]\) e
\(B=[b_1,b_2, ... b_n]\). La distanza tra queste sequenze sarà chiamata valore
\(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n |\) . Ad esempio,
\(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2 | ++|1–0|+|–1–0|=0+0+1+1=2 \)
Al termine della lezione, il professore ha scritto alla lavagna una sequenza di n numeri interi
\(B=[b_1,b_2, ... b_n]\) e ha chiesto gli studenti a trovare una sequenza armonica
\(A=[a_1,a_2, ... a_n]\) tale che
\( d( A, B)\) è minimo. Per facilitarne la verifica, il professore ti chiede di scrivere come risposta solo la distanza minima desiderata
\(d(A,B)\) .
Occorre scrivere un programma che, data una sequenza B, determini a quale minima distanza dalla sequenza B esiste una sequenza armonica A.
Inserimento
La prima riga del file di input contiene il numero intero n – il numero di elementi nella sequenza (
\(3 \le n \le 500\)).
La seconda riga contiene n numeri interi
\(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .
Impressum
Il file di output deve contenere un singolo numero intero: la distanza minima possibile dalla sequenza nel file di input a una sequenza armonica.
Esempi
| # |
Input |
Uscita |
| 1 |
4
1 2 0 0
| 2 |