重組問題 (APCS 2025-01 中高級)

對於一個長度為 \(n\) 的整數陣列 \(a_1, a_2, \ldots, a_n\)，已知 \(a_1=0\)，定義其距離多重集為

也就是陣列中任兩個數字的絕對值差所組成的多重集合，共有 \(\frac{n(n-1)}{2}\) 個數字。

現在給定 \(\Delta(a)\) 的內容。保證至少存在一個以 \(0\) 開頭的嚴格遞增 陣列能產生這個距離多重集。請輸出所有可能陣列中字典序最小與字典序 最大的陣列。

例如 \(n=3\) 且 \(\Delta=(3,4,7)\)。最大的距離 \(7\) 必定來自最小值 \(0\) 與最大值，因此陣列最大值是 \(7\)。剩下的點可能是 \(3\) 或 \(4\)，所以可能的 陣列為 \((0,3,7)\) 與 \((0,4,7)\)。

輸入格式

第一行包含一個正整數 \(n\)。

第二行包含 \(\frac{n(n-1)}{2}\) 個正整數，表示距離多重集 \(\Delta\) 的 內容。當 \(n=1\) 時，第二行為空行。

限制

• \(1\le n\le 25\)
• \(\Delta\) 中的每個整數都介於 \(1\) 到 \(100\) 之間
• 保證至少存在一個合法陣列

輸出格式

第一行輸出能產生 \(\Delta\) 的字典序最小陣列。

第二行輸出能產生 \(\Delta\) 的字典序最大陣列。

每個陣列輸出 \(n\) 個整數，相鄰兩數以一個空白分隔。

評分說明

每一筆測試資料的執行時間限制均為 1 秒，依正確通過的測試資料筆數給分。

範例輸入 1

3
3 4 7

範例輸出 1

0 3 7
0 4 7

範例解釋 1

距離多重集 \((3,4,7)\) 可以由 \((0,3,7)\) 或 \((0,4,7)\) 產生，兩者分別是 字典序最小與最大的答案。

範例輸入 2

5
1 2 3 3 5 5 6 8 10 11

範例輸出 2

0 1 3 6 11
0 5 8 10 11

題目來源

2025 年 1 月 APCS 程式實作第 3 題： ZeroJudge q183「重組問題」。