사진 촬영

농부 존은 사진 촬영을 위해 \(1\ldots N\)로 번호가 붙은 \(N\)마리의 소(\(2\le N\le 10^3\))를 한 줄로 세우고 있다. FJ는 원래 왼쪽에서 \(i\)번째 소가 번호 \(a_i\)인 소가 되도록 계획했고, 순열 \(a_1,a_2,\ldots,a_N\)을 종이에 적어 두었다. 그런데 안타깝게도 그 종이를 최근 농부 노즈(Nhoj)가 훔쳐 가 버렸다!

다행히 FJ가 원래 적어 두었던 순열을 복원할 가능성은 아직 남아 있다. 종이를 도난당하기 전에, 베시가 각 \(1\le i에 대해 \(b_i=a_i+a_{i+1}\)을 만족하는 수열 \(b_1,b_2,\ldots,b_{N-1}\)을 기록해 두었기 때문이다.

베시의 정보를 바탕으로, \(b\)를 만들어 낼 수 있는 순열 \(a\) 중 "사전순으로 가장 작은" 것을 FJ가 복원하도록 도와주자. 어떤 \(j\)에 대해 모든 \(i에서 \(x_i=y_i\)이고 \(x_j이면 순열 \(x\)는 순열 \(y\)보다 사전순으로 작다(다시 말해, 두 순열이 어떤 지점까지는 동일하고 그 지점에서 \(x\)가 \(y\)보다 작다). 그러한 \(a\)가 적어도 하나 존재함이 보장된다.

문제 제공: Benjamin Qi and Chris Zhang

점수 배점

• 테스트 케이스 2-4는 \(N\le 8\)을 만족한다.
• 테스트 케이스 5-10은 추가 제약이 없다.

문제 제공: Benjamin Qi and Chris Zhang

첫째 줄에 정수 \(N\)이 주어진다.

둘째 줄에 공백으로 구분된 \(N-1\)개의 정수 \(b_1,b_2,\ldots,b_{N-1}\)이 주어진다.

공백으로 구분된 \(N\)개의 정수 \(a_1,a_2,\ldots,a_{N}\)을 한 줄에 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > January > Bronze