고속도로 위의 마을

시간 제한1초메모리 제한128 MB

요약

일직선 위에 있는 N개 마을의 모든 쌍의 거리 집합이 주어질 때, 그 거리 집합을 정확히 만들어내는 인접 마을 간 거리들을 모두 찾습니다.

난이도: 보통10점 중 7점
유형: 백트래킹, 조합론, 완전 탐색
정답자: 아직 제출이 없습니다

문제

곧게 뻗은 고속도로 위에 여러 개의 마을이 일렬로 놓여 있다. 이 고속도로에는 분기점이 없어서 모든 마을은 한 직선 위에 순서대로 자리 잡는다.

이웃한 마을 사이의 거리를 모두 알고 있으면, 그 값들을 이용해 임의의 두 마을 사이의 거리도 계산할 수 있다. 예를 들어 마을 다섯 개 A, B, C, D, E가 순서대로 놓여 있고 이웃한 마을 사이의 거리가 주어지면, 이로부터 모든 마을 쌍 사이의 거리표(총 $N(N-1)/2$ 개)를 만들 수 있다.

이제 반대로, 모든 마을 쌍 사이의 거리 $N(N-1)/2$ 개가 모두 주어졌을 때 마을들이 놓인 순서를 정하고 이웃한 두 마을 사이의 거리( $N-1$ 개)를 복원하는 프로그램을 작성하라. 같은 거리 집합을 만들어 내는 배치가 여러 가지일 수 있으며, 이 경우 가능한 모든 배치를 찾아야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 마을의 수 $N$ ( $2 \le N \le 20$ )이 주어진다. 그 다음에는 모든 마을 쌍 사이의 거리 $N(N-1)/2$ 개의 정수가 공백이나 줄바꿈으로 구분되어 내림차순(값이 큰 것부터 작은 것 순, 같은 값이 이어질 수 있음)으로 주어진다. 각 거리는 $1$ 이상 $400$ 이하의 자연수이며, 가장 큰 거리 값은 가장 왼쪽 마을과 가장 오른쪽 마을 사이의 거리이다.

마지막 줄에는 $0$ 이 하나 주어지며, 이는 입력의 끝을 뜻한다.

출력

각 테스트 케이스마다 이웃한 마을 사이의 거리 $N-1$ 개를 공백으로 구분하여 출력한다. 정답이 여러 가지이면, 각 정답을 거리들의 수열로 보고 사전순으로 정렬하여 한 줄에 하나씩 모두 출력한다. 가능한 정답이 하나도 없으면 아무것도 출력하지 않는다. 한 테스트 케이스의 정답을 모두 출력한 뒤에는 -----을 한 줄에 출력한다.

예제5

예제 1

입력

2
1
3
5 3 2
3
6 3 2
5
9 8 7 6 6 4 3 2 2 1
6
9 8 8 7 6 6 5 5 3 3 3 2 2 1 1
6
11 10 9 8 7 6 6 5 5 4 3 2 2 1 1
7
72 65 55 51 48 45 40 38 34 32 27 25 24 23 21 17 14 13 11 10 7
20
190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171
170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151
150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131
130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111
110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91
90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71
70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51
50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
10 9 8 7 6 5 4 3 2 1
19
60 59 58 56 53 52 51 50 48 48 47 46 45 45 44 43 43 42 42 41 41 40 40 40
40 40 40 40 39 39 39 38 38 38 37 37 36 36 35 35 34 33 33 32 32 32 31 31
30 30 30 29 28 28 28 28 27 27 26 26 25 25 25 25 24 24 23 23 23 23 22 22
22 22 21 21 21 21 20 20 20 20 20 20 20 20 20 20 20 20 20 19 19 19 19 19
18 18 18 18 18 17 17 17 17 16 16 16 15 15 15 15 14 14 13 13 13 12 12 12
12 12 11 11 11 10 10 10 10 10 9 9 8 8 8 8 8 8 7 7 7 6 6 6 5 5 5 5 5 5 4
4 4 3 3 3 3 3 3 2 2 2 2 2 2 1 1 1 1 1 1
0

예상 출력

1
-----
2 3
3 2
-----
-----
1 2 4 2
2 4 2 1
-----
1 2 3 2 1
-----
1 1 4 2 3
1 5 1 2 2
2 2 1 5 1
3 2 4 1 1
-----
7 14 11 13 10 17
17 10 13 11 14 7
-----
-----
1 1 2 3 5 8 1 1 2 3 5 8 1 1 2 3 5 8
8 5 3 2 1 1 8 5 3 2 1 1 8 5 3 2 1 1
-----

예제 2
입력
```
2
5
0
```
예상 출력
```
5
-----
```
예제 3
입력
```
3
10 4 3
0
```
예상 출력
```
-----
```
예제 4
입력
```
4
9 7 5 4 3 2
0
```
예상 출력
```
2 3 4
4 3 2
-----
```
예제 5
입력
```
4
7 4 4 3 3 1
0
```
예상 출력
```
3 1 3
-----
```