합 s , 차 d 는 아래와 같이 정의된다.
s(i) = a(2*i-1) + a(2*i) // 인접한 수의 합 d(i) = a(2*i-1) - a(2*i) // 인접한 앞수 - 뒤수2^n 개의 데이터가 주어질 때 , 반 씩 줄여가면서 처리된 s[i] , d[i] 순으로 표시한다.
| n = 8 |
5 2 3 2 5 7 9 6
|
| n = 4 |
7 5 12 15 3 1 -2 3
|
| n = 2 |
12 27 2 -3 3 1 -2 3
|
| n = 1 |
39 -15 2 -3 3 1 -2 3
|
처리된 결과가 주어질 때 , 원 데이터를 구하는게 문제이다.
입력의 첫 수는 데이터 수이다. 데이터 수는 2 의 거듭제곱 형태이고 256 을 넘지 않는다.
입력 8 39 -15 2 -3 3 1 -2 3 출력 5 2 3 2 5 7 9 6 입력 4 10 -4 -1 -1 출력 1 2 3 4
출처:Rocky Mountain 2007