등차수열
시간 제한2초메모리 제한128 MB
수열 S와 초항 A0가 주어질 때, 모든 i에서 floor(A0+(i+1)d)가 S_i와 일치하도록 하는 최소 공차 d(d≥0)를 구합니다.
문제
등차수열은 연속한 두 항의 차이가 항상 같은 수열이다. 예를 들어 3 5 7 9 11 13은 공차가 2인 등차수열이다. 이 문제에서 실수 수열 A는 A_i = A_0 + i*d로 정의된다.
길이 N의 수열 S가 주어진다. 모든 0 <= i < N에 대해 S_i = floor(A_{i+1})이어야 하며, S는 감소하지 않는 수열이다. 여기서 floor(x)는 x보다 작거나 같은 정수 중 가장 큰 값이다. 예를 들어 floor(3.4) = 3, floor(0.6) = 0, floor(-1.2) = -2, floor(-0.6) = -1이다.
조건을 만족하는 d 중 가장 작은 값을 구하라. d는 0 이상이어야 한다.
입력
첫째 줄에 S의 길이 N과 초기값 A_0가 주어진다. 둘째 줄에는 S_0부터 S_{N-1}까지 N개의 정수가 주어진다. N = 0이면 둘째 줄은 주어지지 않는다.
N은 0 이상 50 이하의 정수이고, A_0와 S의 모든 원소의 절댓값은 10^6 이하이다.
출력
가능한 d의 최솟값을 출력한다. 정답과의 절대 오차 또는 상대 오차가 10^{-9} 이하이면 정답으로 인정된다. 만족하는 d가 없으면 -1을 출력한다.