UACC 1 P5 - A Lab Report

View as PDF

Submit solution


Points: 10
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

After completing his physics lab, Lucas is tasked with creating a graph to illustrate his collected data. Lucas has gathered an array of N data points, A1,A2,,AN, that are evenly spaced along the x-axis. Based on his research, Lucas knows that the data should be linear, with equal differences between adjacent data points. As a perfectionist, Lucas wants to create a graph that depicts this linear relationship, but he feels guilty about modifying the data too much. He has decided that he will only shift a group of contiguous data points all up or all down by 1 in a single operation. What is the minimum number of operations Lucas will need to perform to make his data linear?

Constraints

1N106

109Ai109

Input Specification

The first line contains N.

The next line contains N space-separated integers, A1,A2,,AN.

Output Specification

Output the minimum number of operations needed.

Sample Input 1

Copy
5
1 2 4 6 10

Sample Output 1

Copy
2

Explanation for Sample Output 1

First, increase the subarray [2,4,6] by 1. The data becomes [1,3,5,7,10].

Next, decrease the subarray [10] by 1. The data becomes [1,3,5,7,9].

It can be proven that 2 is the minimum number of operations needed.

Sample Input 2

Copy
5
-2 -1 1 6 9

Sample Output 2

Copy
3

Explanation for Sample Output 2

First, increase the subarray [1,1] by 1. The data becomes [2,0,2,6,9].

Next, increase the subarray [0,2] by 1. The data becomes [2,1,3,6,9].

Finally, decrease the subarray [2,1] by 1. The data is now [3,0,3,6,9].

It can be proven that 3 is the minimum number of operations needed.


Comments

There are no comments at the moment.