Problem
Uma série de palestras na Universidade de Flatland é dedicada ao estudo de sequências.
O professor chama uma sequência de números inteiros
\(a_1, a_2, ..., a_n\) harmonioso se todos os números exceto
\(a_1\) e
\(a_n\), é igual à soma de adjacentes:
\(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Por exemplo, a sequência [1,2,1,–1] é harmônica porque 2=1+1 e 1=2+(–1) .
Considere sequências de igual comprimento:
\(A=[a_1,a_2, ... a_n]\) e
\(B=[b_1,b_2, ... b_n]\). A distância entre essas sequências será chamada de valor
\(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n |\) . Por exemplo,
\(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2 | ++|1–0|+|–1–0|=0+0+1+1=2 \)
Ao final da aula, o professor escreveu na lousa uma sequência de n inteiros
\(B=[b_1,b_2, ... b_n]\)e perguntou os alunos a encontrar uma sequência harmoniosa
\(A=[a_1,a_2, ... a_n]\) tal que
\( d( A, B)\) é mínimo. Para facilitar a verificação, o professor pede que você escreva como resposta apenas a distância mínima desejada
\(d(A,B)\) .
É necessário escrever um programa que, dada uma sequência B, determine a que distância mínima da sequência B existe uma sequência harmônica A.
Entrada
A primeira linha do arquivo de entrada contém o inteiro n – o número de elementos na sequência (
\(3 \le n \le 500\)).
A segunda linha contém n inteiros
\(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .
Impressão
O arquivo de saída deve conter um único inteiro: a distância mínima possível da sequência no arquivo de entrada para uma sequência harmônica.
Exemplos
| # |
Entrada |
Saída |
| 1 |
4
1 2 0 0
| 2 |