시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 1024 MB 76 18 18 40.909%

문제

먼 옛날, 용산구 선린마을에는 수직선 위에 집 $N$채가 자리하고 있었다.

왼쪽으로부터 순서대로 각 집의 위치는 $P_1, \cdots, P_N$이었고, 가장 왼쪽에 있는 집의 위치 $P_1$은 $0$이었다.

어느 날 정휘는 선린마을에 있는 서로 다른 두 집 사이의 거리를 모두 측정했다.

즉, 모든 $1 \le i < j \le N$에 대해, $i$번째 집과 $j$번째 집의 거리인 $P_j - P_i$를 측정했다.

예를 들어, 4개의 집의 위치가 각각 $0, 1, 3, 4$에 있었다면, 정휘는 집들 사이의 거리인 $1-0=1$, $3-0=3$, $3-1=2$, $4-0=4$, $4-1=3$, $4-3=1$을 각각 측정했다.

그리고 정휘는 결과들을 정렬해서 6개의 수 $1, 1, 2, 3, 3, 4$를 기록해두었다.

하지만 오늘, 여러분이 천하제일 코딩대회를 치는 사이, 극단 원리주의 민초파 김준원이 선린마을의 집들을 모두 파괴했다.

여러분은 정휘가 기록해놓은 $N(N-1)/2$개의 수를 이용해 선린마을의 집을 복원해야 한다.

입력

첫째 줄에 선린마을에 있던 집의 개수 $N$이 주어진다.

둘째 줄에 정휘가 측정한 $N(N-1)/2$ 개의 거리를 오름차순으로 정렬한 결과 $D_1, D_2, \cdots , D_{N(N-1)/2}$가 공백으로 구분되어 주어진다.

출력

입력을 토대로 복원한 선린마을의 집들의 위치를 나타내는 $N$개의 정수 $P_1, P_2, \cdots , P_N$을 공백으로 구분해 출력하라.

여러분이 복원한 집들의 위치가,

  • $P_1 = 0$
  • $P_1 < P_2 < \cdots < P_N$
  • 모든 $1 \le i < j \le N$에 대해 $P_j - P_i$의 값들을 모은 $N(N-1)/2$개의 수들을 오름차순으로 정렬하면, 입력으로 주어진 $D_1, \cdots , D_{N(N-1)/2}$과 같다.

를 모두 만족하면 정답으로 인정된다.

제한

  • $2 \leq N \leq 20$
  • $1 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N(N-1)/2$)
  • $D_i \le D_{i+1}$ ($1 \le i < N(N-1)/2$). 즉, $D_1, \cdots, D_{N(N-1)/2}$는 오름차순으로 정렬되어 있다.
  • 조건을 만족하도록 집들의 위치를 복원할 수 있다.

예제 입력 1

2
2

예제 출력 1

0 2

예제 입력 2

3
1 2 3

예제 출력 2

0 1 3

용산구에 있는 세 집의 위치가 각각 $P_1 = 0$, $P_2 = 1$, $P_3 = 3$이었다면, 집들 사이의 거리들은

  • $P_2 - P_1 = 1 - 0 = 1$
  • $P_3 - P_2 = 3 - 1 = 2$
  • $P_3 - P_1 = 3 - 0 = 3$

으로 정휘의 기록인 $1, 2, 3$과 잘 맞아떨어진다.

마찬가지로, 세 집의 위치가 각각 $P_1 = 0$, $P_2 = 2$, $P_3 = 3$일 경우에도 집들 사이의 거리들이 정휘의 기록과 잘 맞아떨어지므로, 0 2 3을 출력해도 정답으로 인정된다.

출처

High School > 선린인터넷고등학교 > 제5회 천하제일 코딩대회 본선 J번