Problem
Một loạt bài giảng tại Đại học Flatland dành cho việc nghiên cứu trình tự.
Giáo sư gọi một dãy số nguyên
\(a_1, a_2, ..., a_n\) điều hòa nếu mọi số ngoại trừ
\(a_1\) và
\(a_n\), bằng tổng của liền kề:
\(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Ví dụ: chuỗi [1,2,1,–1] là điều hòa vì 2=1+1 và 1=2+(–1) .
Xem xét các chuỗi có độ dài bằng nhau:
\(A=[a_1,a_2, ... a_n]\) và
\(B=[b_1,b_2, ... b_n]\). Khoảng cách giữa các chuỗi này sẽ được gọi là giá trị
\(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n |\) . Ví dụ:
\(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2 | ++|1–0|+|–1–0|=0+0+1+1=2 \)
Cuối bài giảng, giáo sư viết lên bảng một dãy n số nguyên
\(B=[b_1,b_2, ... b_n]\)và hỏi cho học sinh tìm dãy hài hòa
\(A=[a_1,a_2, ... a_n]\) sao cho
\( d( A, B)\) là nhỏ nhất. Để giúp bản thân kiểm tra dễ dàng hơn, giáo sư yêu cầu bạn chỉ viết dưới dạng câu trả lời khoảng cách tối thiểu mong muốn
\(d(A,B)\) .
Yêu cầu viết chương trình cho trước dãy B xác định khoảng cách nhỏ nhất so với dãy B là dãy điều hòa A.
Đầu vào
Dòng đầu tiên của tệp đầu vào chứa số nguyên n – số phần tử trong dãy (
\(3 \le n \le 500\)).
Dòng thứ hai chứa n số nguyên
\(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .
Dấu ấn
Tệp đầu ra phải chứa một số nguyên duy nhất: khoảng cách tối thiểu có thể từ chuỗi trong tệp đầu vào đến chuỗi điều hòa.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4
1 2 0 0
| 2 |