18323번 - Photoshoot
농부 John은 사진 촬영을 위해 번호가 1부터 N까지 매겨진 N마리의 소를 한 줄로 세우고 있다.
존은 처음에 왼쪽에서 $i$번째 위치에 올 소의 번호를 $a_i$라고 정하고, 순열 $a_1, a_2, \ldots, a_N$ 을 종이에 적어 두었다.
하지만 불행히도, 그 종이는 최근 농부 Nhoj에게 도난당했다.
다행히도, 종이가 도난당하기 전에 Bessie가 다음 정보를 기록해 두었다.
길이가 $N-1$인 수열 $b_1, b_2, \ldots, b_{N-1}$ 이 있으며, 각 원소는 $b_i = a_i + a_{i+1} (1 \leq i < N)$ 을 만족한다.
Bessie가 기록한 정보만을 이용하여,이 조건을 만족하는 순열 $a$ 중에서 사전순으로 가장 작은 순열을 복원하라.
- 두 순열 $x$ 와 $y$ 가 있을 때, 어떤 위치 $j$가 존재하여 모든 $i<j$ 에 대해 $x_i = y_i$ 이고 $x_j < y_j$ 라면 $x$ 는 $y$ 보다 사전순으로 작다고 한다.
첫 줄에 정수 $N$ 이 주어진다.
두 번째 줄에 $N-1$ 개의 정수 $b_1, b_2, \ldots, b_{N-1}$ 가 공백으로 구분되어 주어진다.
조건을 만족하는 사전순으로 가장 작은 순열 $a_1, a_2, \dots, a_N$ 을 한 줄에 공백으로 구분하여 출력한다.
- $2 \leq N \leq 1000$
- 조건을 만족하는 순열 $a$ 는 적어도 하나 이상 존재함이 보장된다.
댓글을 작성하려면 로그인해야 합니다.
jtw7913 10달 전 1
문제
농부 John은 사진 촬영을 위해 번호가 1부터 N까지 매겨진 N마리의 소를 한 줄로 세우고 있다.
존은 처음에 왼쪽에서 $i$번째 위치에 올 소의 번호를 $a_i$라고 정하고, 순열 $a_1, a_2, \ldots, a_N$ 을 종이에 적어 두었다.
하지만 불행히도, 그 종이는 최근 농부 Nhoj에게 도난당했다.
다행히도, 종이가 도난당하기 전에 Bessie가 다음 정보를 기록해 두었다.
길이가 $N-1$인 수열 $b_1, b_2, \ldots, b_{N-1}$ 이 있으며, 각 원소는 $b_i = a_i + a_{i+1} (1 \leq i < N)$ 을 만족한다.
Bessie가 기록한 정보만을 이용하여,
이 조건을 만족하는 순열 $a$ 중에서 사전순으로 가장 작은 순열을 복원하라.
- 두 순열 $x$ 와 $y$ 가 있을 때, 어떤 위치 $j$가 존재하여 모든 $i<j$ 에 대해 $x_i = y_i$ 이고 $x_j < y_j$ 라면 $x$ 는 $y$ 보다 사전순으로 작다고 한다.
입력
첫 줄에 정수 $N$ 이 주어진다.
두 번째 줄에 $N-1$ 개의 정수 $b_1, b_2, \ldots, b_{N-1}$ 가 공백으로 구분되어 주어진다.
출력
조건을 만족하는 사전순으로 가장 작은 순열 $a_1, a_2, \dots, a_N$ 을 한 줄에 공백으로 구분하여 출력한다.
제한
- $2 \leq N \leq 1000$
- 조건을 만족하는 순열 $a$ 는 적어도 하나 이상 존재함이 보장된다.