에이다의 계산법

러브레이스 백작부인 오거스타 에이다 킹노엘은 찰스 배비지의 해석기관을 위해 쓴 프로그램으로 가장 널리 알려져 있다. 에이다는 수열과 급수를 다루는 문제를 차분법으로 푸는 방법도 설명했고, 배비지의 차분기관이 그 기법을 구현했다.

방법은 이렇다. 수열에서 인접한 두 항의 차를 모두 구하면 새 수열이 나온다. 이 수열은 원래 수열이 나타내는 함수의 도함수와 관련이 있다. 원래 수열이 일차 다항식(일차 함수)에서 나왔다면 1차 차분은 모두 같은 값, 즉 상수다. 이차 다항식에서 나왔다면 1차 차분이 일차로 변하므로, 그 새 수열의 차분인 2차 차분이 상수가 된다. 차수가 높아져도 같은 규칙이 이어져서 $n$차 다항식이면 $n$번째 차분 행이 상수다.

예를 들어 일차 다항식 $3x + 3$을 $x = 0, 1, 2, 3, 4$에서 계산하면 아래 표와 같다.

다항식 $x^2$을 $x = 3, 5, 7, 9$에서 계산하면 아래 표와 같다.

차분 행이 상수가 되면 표를 오른쪽으로 한 칸 늘려서, 최소 차수 다항식이 다음 등간격 입력에서 갖는 값을 읽어낼 수 있다.

등간격 입력 $n$개에서 계산한 다항식 값이 주어진다. 이 값들을 만드는 최소 차수 다항식의 차수와, 같은 다항식이 다음 등간격 입력에서 갖는 값을 구하라.

주어지는 다항식 값의 개수 $n$이 먼저 주어진다($2 \le n \le 10$). 이어서 등간격 입력 $n$개에서 계산한 다항식 값 $v_1, v_2, \dots, v_n$이 주어진다. 모든 $v_j$는 $-2\,000\,000 \le v_j \le 2\,000\,000$을 만족하며, 주어진 값 가운데 적어도 두 개는 서로 다르다. 수는 공백으로 구분되므로 한 줄에 모두 올 수도 있고 여러 줄에 나뉘어 올 수도 있다.

두 정수 $d$와 $v_{n+1}$을 공백 하나로 구분해 출력한다. $d$는 주어진 수열을 만드는 최소 차수 다항식의 차수이고, $v_{n+1}$은 그 다항식이 다음 등간격 입력에서 갖는 값이다. 적어도 두 값이 서로 다르므로 $d$는 1 이상 $n - 1$ 이하이고, 두 답은 모두 유일하다.