B. Make Them Equal

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a sequence a1,a2,…,an consisting of n integers.

You can choose any non-negative integer D (i.e. D≥0), and for each ai you can:

add D (only once), i.?e. perform ai:=ai+D, or
subtract D (only once), i.?e. perform ai:=ai?D, or
leave the value of ai unchanged.
It is possible that after an operation the value ai becomes negative.

Your goal is to choose such minimum non-negative integer D and perform changes in such a way, that all ai are equal (i.e. a1=a2=?=an).

Print the required D or, if it is impossible to choose such value D, print -1.

For example, for array [2,8] the value D=3 is minimum possible because you can obtain the array [5,5] if you will add D to 2 and subtract D from 8. And for array [1,4,7,7] the value D=3 is also minimum possible. You can add it to 1 and subtract it from 7 and obtain the array [4,4,4,4].

Input

The first line of the input contains one integer n (1≤n≤100) — the number of elements in a.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤100) — the sequence a.

Output

Print one integer — the minimum non-negative integer value D such that if you add this value to some ai, subtract this value from some ai and leave some ai without changes, all obtained values become equal.

If it is impossible to choose such value D, print -1.

Examples

input
6
1 4 4 7 4 1
output
3
input
5
2 2 5 2 5
output
3
input
4
1 3 3 7
output
-1
input
2
2 8
output
3

思路

找出一個(gè)數(shù)能使所有給出的數(shù)中的一些數(shù)通過加/減去這個(gè)數(shù)全部變成相等的數(shù)，給出的數(shù)中有一些重復(fù)的，需要去重，然后為了好看，可以進(jìn)行排序，排序+去重=set。

然后，如果集合中的數(shù)超過三個(gè)，那么問題肯定無解，比如1，2，3，4，不可能找到一個(gè)數(shù)使這四個(gè)數(shù)經(jīng)過一些變換之后相等，所以超過三個(gè)數(shù)的集合直接輸出-1；

如果集合中有三個(gè)數(shù)，那么肯定是第一個(gè)數(shù)和第三個(gè)數(shù)經(jīng)過加上一個(gè)數(shù)和減去一個(gè)數(shù)變成中間的數(shù)，如果第二個(gè)數(shù)減去第一個(gè)數(shù)等于第三個(gè)數(shù)減去第二個(gè)數(shù)，那么這個(gè)差就是結(jié)果，如果不等，說明無解；

如果集合中有兩個(gè)數(shù)，那么差就是第二個(gè)數(shù)減去第一個(gè)數(shù)，如果這個(gè)數(shù)是奇數(shù)，直接輸出，如果是偶數(shù)，說明第一個(gè)數(shù)加上這個(gè)差的一半等于第二個(gè)數(shù)減去這個(gè)差的一半；

如果集合中有一個(gè)數(shù)，則結(jié)果為0.

Code

#include <iostream> #include <set> using namespace std; int main() {set<int> num;int n,temp=0,s[107],p[107];while (~scanf("%d",&n)){num.clear();for (int i = 0; i < n; ++i) {cin>>s[i];num.insert(s[i]);}set<int>::iterator it;for (it=num.begin();it!=num.end();it++)p[temp++]=*it;switch (temp){case 1:cout<<'0'<<endl;break;case 2:if ((p[1]-p[0])%2!=0){cout<<p[1]-p[0]<<endl;break;}else{cout<<(p[1]-p[0])/2<<endl;break;}case 3:if (p[1]-p[0]==p[2]-p[1]){cout<<p[1]-p[0]<<endl;break;}else{cout<<"-1"<<endl;break;}default:cout<<"-1"<<endl;break;}}return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #552 (Div. 3) —— B. Make Them Equal的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。