메뉴 건너뛰기

문제

00nh1 수열 축소 0  

시간메모리제출 올바른 답 비율
1초64MB
29
1
3.4%


나의 횟수나의 최근 판정시도 성공 비율
71
14.3%
수열 축소 

n개의 정수들로 이루어진 수열 \([a_1, a_2, ..., a_n]\) 이 있다. 여기에 정수 \(i\)를 주면서 '축소'라는 명령을 하면 \(a_i\) 와 \(a_{i+1}\) 이 없어지고, 대신 두 수의 차가 들어간다. 즉, 새로 들어간 수는 \(|a_i - a_{i+1}|\) 이다.

바꿔 말하면, 축소 연산 \(i\) 는

축소 \(([a_1, a_2, ... , a_n], i) = [a_1, ... , a_{i-1}, |a_i - a_{i+1}|, a_{i+2}, ... , a_n]\) 이다. 단, \(1 \leq i \leq n-1\)

예를 들어, 수열 [12, 10, 4, 3, 5]에 축소 연산들 2, 3, 2, 1을 차례대로 적용하면

축소 \(([12, 10, 4, 3, 5], 2) = [12, 6, 3, 5]\) 
축소 \(([12, 6, 3, 5], 3) = [12, 6, 2]\)
축소 \(([12, 6, 2], 2) = [12, 4]\)
축소 \(([12, 4], 1) = [8]\) 이 되므로, 마지막에 8이 남는다.

같은 수열에 축소 연산들 1, 1, 1, 1을 적용하면

축소 \(([12, 10, 4, 3, 5], 1) = [2, 4, 3, 5]\)
축소 \(([2, 4, 3, 5], 1) = [2, 3, 5]\)
축소 \(([2, 3, 5], 1) = [1, 5]\)
축소 \(([1, 5], 1) = [4]\)  가 되므로, 마지막에 4가 남는다.

입력으로 수열과 최종값이 주어질 때, \(n-1\)번의 축소 연산을 수행하여 최종값을 얻을 수 있는가를 알아내는 프로그램을 작성하시오. 최종값을 얻을 수 있는 축소 연산들이 여러 개일 경우는 그 중 하나만 출력한다.

입력

첫 줄에는 정수 \(n (1 \leq n \leq 30)\) 이 주어진다. 둘째 줄에는 최종값이 주어진다. 다음 \(n\)줄에는 \(a_1, a_2, ..., a_n\)에 해당하는 수가 한 줄에 하나씩 순서대로 주어진다. ( \(1 \leq a_i \leq 30\) )

출력

첫 줄부터 구한 축소 연산들을 한 줄에 하나씩 순서대로 출력한다. 최종값을 구할 수 없는 경우에는 첫 줄에 0을 출력한다.

예시
1입력
5
8
12
10
4
3
5
출력
2
3
2
1
2입력
4
7
12
10
4
5
출력
0
출처
2000년 한국정보올림피아드 전국 본선 고등부 1번 문제
위로