차분표를 이용한 수열 외삽

수열의 값을 외삽(extrapolation)하는 아주 오래된 기법 중 하나는 차분표(difference table)를 이용한다. 예를 들어 네 개의 값 $3, 6, 10, 15$ 에 대한 차분표는 다음과 같이 나타낼 수 있다.

원래 수열은 표의 첫 번째 열에 놓인다. 두 번째 열의 각 항목은 첫 번째 열에서 인접한 두 항목의 차이며, 이를 1차 차분이라 한다. 세 번째 열의 각 항목은 두 번째 열에서 인접한 두 항목의 차이(2차 차분)이고, 이런 식으로 계속된다. 마지막 열에는 항상 값이 정확히 하나만 남는다. 수열의 값이 $n$ 개이면 완성된 차분표는 $n$ 개의 열을 가지며, $n$ 번째 열의 유일한 값이 $(n-1)$차 차분이다.

외삽을 하기 위해 우리는 $(n-1)$차 차분이 일정하다고 가정한다(그렇지 않다고 볼 근거가 자료에 없기 때문이다). 이 가정 아래에서 $(n-2)$차 차분 열의 다음 항목, 이어서 $(n-3)$차 차분 열의 다음 항목을 차례로 계산해 나가면, 마침내 첫 번째 열의 다음 항목, 즉 수열의 다음 값을 얻는다. 아래 표는 예시를 확장하기 위해 네 개의 항목(상자로 표시)을 추가하여 다음 값 $21$ 을 구한 것이다. $(n-1)$차 차분이 일정하다는 가정을 유지하면 이 과정을 원하는 만큼 계속할 수 있다.

입력은 여러 개의 외삽 요청으로 이루어진다. 각 요청은 먼저 정수 $n$ 으로 시작하며, 이는 확장할 수열에 들어 있는 값의 개수다. $n$ 이 $0$ 이면 프로그램을 종료한다. $n$ 이 $0$ 이 아니면 $n$ 은 최대 $10$ 이고, 뒤이어 수열의 주어진 원소 $n$ 개(정수)가 온다. 각 요청의 마지막 값은 수행할 외삽 횟수 $k$($1$ 이상)이며, 이는 차분표의 각 열에 항목을 $k$ 개씩 추가한다는 뜻이다. 주어진 값들에는 $1$ 부터 $n$ 까지 번호를 매긴다.

토큰은 임의의 공백으로 구분될 수 있다.

각 요청에 대해 원래 수열을 $k$ 번 외삽하여 $(n+k)$ 번째 값을 구하라. 요청마다 정확히 한 줄씩, Term X of the sequence is Y 형식으로 출력한다. 여기서 X 는 $n+k$, Y 는 외삽으로 얻은 값이다.

힌트: $k$ 의 상한이 주어지지 않으므로, 완전한 차분표를 메모리에 모두 담지 못할 수 있다.