수열 축소 |
---|
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]\) 같은 수열에 축소 연산들 1, 1, 1, 1을 적용하면 축소 \(([12, 10, 4, 3, 5], 1) = [2, 4, 3, 5]\) 입력으로 수열과 최종값이 주어질 때, \(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번 문제 |