• \(a_1 = 0\) 和 \(a_n = \max(\Delta)\) 已知（題目的例子就講了）。
• 把已確定的數兩兩的差從 \(\Delta\) 中移除。想想看：剩下的差值中最大的那一個，一定是「誰減誰」？可能的情況只有兩種——這就是整題的鑰匙。

觀察（1）：\(a_n\) 就是 \(\Delta\) 的最大值

陣列遞增且 \(a_1 = 0\)，所以最大的差就是 \(a_n - a_1 = a_n\)（題目敘述的例子已經把這件事講給你了）。頭尾兩個數直接確定，剩下至多 \(23\) 個數待決定。

觀察（2）：剩下的最大差值，只有兩種可能的身分

假設目前「兩端」都已經決定了一段：\(a_1, \ldots, a_{L-1}\) 與 \(a_{R+1}, \ldots, a_n\) 都已知（一開始 \(L = 2\)、\(R = n - 1\)），並且把這些已知數兩兩的差都從 \(\Delta\) 中移除了。令剩下的差值中最大的是 \(y\)。

\(y\) 是某兩個數的差 \(a_j - a_i\)（\(i < j\)），其中至少一個索引落在還沒決定的區間 \([L, R]\) 裡。因為陣列遞增，要讓差最大，另一端要嘛取到最小的 \(a_1 = 0\)、要嘛取到最大的 \(a_n\)。所以 \(y\) 只有兩種可能的身分：

1. \(y = a_n - a_L\)，也就是 \(a_L = a_n - y\)（配對「最左邊還沒決定的位置」和 \(a_n\)）；
2. \(y = a_R - a_1\)，也就是 \(a_R = y\)（配對 \(a_1\) 和「最右邊還沒決定的位置」）。

為什麼不可能是更中間的組合？若 \(y = a_j - a_i\) 而 \(i > 1\) 且 \(j < n\)，那 \(a_j - a_1 > y\) 也是一個還沒配對的差值，跟「\(y\) 是剩下的最大值」矛盾。同理把 \(i\) 換成 \(1\) 之後，若 \(j\) 不是還沒決定的位置中最右的 \(R\)，那 \(a_R - a_1\) 會更大，一樣矛盾。

用範例 2 走一遍

\(n = 5\)、\(\Delta = \{1, 2, 3, 3, 5, 5, 6, 8, 10, 11\}\)：

• 觀察（1）：\(a_5 = 11\)，移除差值 \(11\)，剩 \(\{1, 2, 3, 3, 5, 5, 6, 8, 10\}\)。
• 剩下最大 \(y = 10\)：要嘛 \(a_2 = 11 - 10 = 1\)，要嘛 \(a_4 = 10\)。
• 先試 \(a_2 = 1\)：移除 \(|1 - 0| = 1\)、\(|11 - 1| = 10\)，剩 \(\{2, 3, 3, 5, 5, 6, 8\}\)。
  • 剩下最大 \(y = 8\)：要嘛 \(a_3 = 11 - 8 = 3\)，要嘛 \(a_4 = 8\)。
  • 先試 \(a_3 = 3\)：移除 \(|3 - 0| = 3\)、\(|3 - 1| = 2\)、\(|11 - 3| = 8\)，剩 \(\{3, 5, 5, 6\}\)。
    • 剩下最大 \(y = 6\)：要嘛 \(a_4 = 11 - 6 = 5\)，要嘛 \(a_4 = 6\)。
    • 試 \(a_4 = 5\)：需要移除 \(|5 - 1| = 4\)，但剩下的差值裡沒有 \(4\)——失敗，回溯。
    • 試 \(a_4 = 6\)：需要移除 \(6, 5, 3, 5\)，剛好全部用完——得到解 \((0, 1, 3, 6, 11)\)。
• 把其餘分支也走完，整題只會再找到一個解 \((0, 5, 8, 10, 11)\)。

兩個解取字典序最小、最大，正是範例答案的兩行。

整理成演算法

用遞迴枚舉從兩端往中間填：狀態是「位置 \([L, R]\) 還沒決定」。每一步找出剩餘最大差值 \(y\)，只有兩個分支（\(a_L = a_n - y\) 或 \(a_R = y\)）；放一個數進去時，把它和所有已決定位置的差從 \(\Delta\) 扣掉，任何一個差不夠扣就代表這條路不合法——還原後回溯。\(L > R\) 時整個陣列決定完成，拿去更新「目前字典序最小」與「目前字典序最大」。

每一步兩個分支、大約 \(n - 2\) 步，所以至多枚舉約 \(2^{23}\) 種情形；但「差值扣不動就剪枝」剪得非常兇，絕大多數分支很早就死掉，實測遠遠跑不滿。用 cnt[1..100] 陣列記各差值剩幾個，每次放數 \(O(n)\) 檢查、找最大值 \(O(C)\)（\(C = 100\) 是值域），整體是 \(O(2^n \times C)\) 等級的上界；改用 STL 的 multiset 可做到 \(O(2^n \times n \log n)\)，本題範圍不需要。

順帶一提：解不只一個很正常

若 \((a_1, \ldots, a_n)\) 是解，把它「鏡像」過來——\(b_i = a_n - a_{n+1-i}\)——任兩元素的差不變，所以也是解。範例 2 的兩個解 \((0,1,3,6,11)\) 與 \((0,5,8,10,11)\) 就互為鏡像。這也是為什麼題目要你輸出「最小」和「最大」兩個。

把一個解的差分數列（相鄰兩項的差）寫出來，會發現一件事：

字典序最大的解的差分數列，恰好是字典序最小的解的差分數列的 reverse——換句話說，字典序最大的解就是字典序最小的解的鏡像 \(b_i = a_n - a_{n+1-i}\)。

用範例 2 驗證：字典序最小 \((0, 1, 3, 6, 11)\) 的差分是 \((1, 2, 3, 5)\)；reverse 成 \((5, 3, 2, 1)\) 疊回去得 \((0, 5, 8, 10, 11)\)，正是字典序最大的解。（本題全部測資的答案也都符合這個性質。）

有了這個性質，程式可以在找到第一組解時（依參考程式碼「先試 \(a_L\) 分支」的順序，第一組找到的一定是字典序最小的解）直接輸出它和它的鏡像然後結束，幾乎不存在能把它卡到 worst case 的測資。

但要小心：這個性質看起來直覺、證明其實很難（dreamoon 老師的解說筆記裡收錄了皮皮提供的反證法證明，有興趣可以去讀）。如果只是「感覺是對的」就拿來用，總有一天會吃虧——要嘛把證明想清楚，要嘛就像下面的參考程式碼一樣，把所有解都枚舉出來取最小最大，完全不依賴這個性質，反正剪枝後速度綽綽有餘。

1. 貪心假解：這題沒有已知的多項式解法，任何「逐項直接決定、不回溯」的貪心一定存在反例。\(n \le 25\) 就是在告訴你用搜索。
2. 以為同一個 \(\Delta\) 至多對應 2 個解（一個解＋它的鏡像）：錯。最小反例在 \(n = 6\)：\((0,1,2,6,8,11)\)、\((0,1,6,7,9,11)\)、\((0,2,4,5,10,11)\)、\((0,3,5,9,10,11)\) 這四個陣列的差值多重集完全相同（而且可以驗證這個 \(\Delta\) 恰好就只有這四個解）。所以「找到一組解和它的鏡像就收工」有機會拿到的不是答案。
3. 差值沒當多重集處理：同一個數值可能出現很多次，要用計數（cnt 陣列或 multiset）來扣，不能用 set；扣失敗時記得把已經扣掉的部分還原再回溯。
4. \(n = 1\) 邊界：\(\Delta\) 是空的（輸入第二行是空行），直接輸出兩行 0。
5. 輸出要兩行：就算解唯一（最小＝最大是同一個陣列），也要印兩次。

思路同上：cnt[] 記各差值剩幾個、dfs(left, right) 表示位置 \([L, R]\) 還沒決定，每步依觀察（2）只試兩個分支。把找到的所有解都拿去更新 best_min／best_max，不依賴進階觀察。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAX_V = 100;
int n;
int cnt[MAX_V + 1];                  // cnt[x] = 差值 x 還剩幾個沒被配對
vector<int> now_arr, best_min, best_max;

// 還沒被配對的差值中最大的那個
int find_max() {
    for (int v = MAX_V; v >= 1; v--) {
        if (cnt[v] > 0) {
            return v;
        }
    }
    return -1;
}

// 嘗試把數值 v 放進陣列：v 與所有已決定位置的差都要從 cnt 扣掉。
// 位置 [left, right] 還沒決定，其餘位置都已決定。
// 有任何一個差扣不動（變成負的）就回傳 false。
bool place(int v, int left, int right) {
    bool ok = true;
    for (int i = 0; i < left; i++) {
        if (--cnt[abs(now_arr[i] - v)] < 0) ok = false;
    }
    for (int i = right + 1; i < n; i++) {
        if (--cnt[abs(now_arr[i] - v)] < 0) ok = false;
    }
    return ok;
}

// 把 place 扣掉的差值全部加回來（回溯用；不論 place 成功與否都要呼叫）
void unplace(int v, int left, int right) {
    for (int i = 0; i < left; i++) cnt[abs(now_arr[i] - v)]++;
    for (int i = right + 1; i < n; i++) cnt[abs(now_arr[i] - v)]++;
}

void dfs(int left, int right) {
    if (left > right) {              // 整個陣列決定完成：更新答案
        best_min = min(best_min, now_arr);
        best_max = max(best_max, now_arr);
        return;
    }
    int y = find_max();              // 觀察 (2)：y 只有兩種可能的身分

    now_arr[left] = now_arr[n - 1] - y;    // 分支一：y = a_n - a_L
    if (place(now_arr[left], left, right)) {
        dfs(left + 1, right);
    }
    unplace(now_arr[left], left, right);

    now_arr[right] = y;                    // 分支二：y = a_R - a_1
    if (place(now_arr[right], left, right)) {
        dfs(left, right - 1);
    }
    unplace(now_arr[right], left, right);
}

int main() {
    cin >> n;
    if (n == 1) {                    // 邊界：Delta 是空的
        cout << 0 << endl << 0 << endl;
        return 0;
    }
    for (int i = 0; i < n * (n - 1) / 2; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    now_arr.assign(n, 0);
    best_min.assign(n, MAX_V + 1);   // 初始化成「比任何合法解都大」
    best_max.assign(n, -1);          // 初始化成「比任何合法解都小」

    now_arr[n - 1] = find_max();     // 觀察 (1)：a_n = 最大差值
    cnt[now_arr[n - 1]]--;
    dfs(1, n - 2);                   // a_1 = 0 與 a_n 已定，遞迴枚舉中間

    for (int i = 0; i < n; i++) cout << best_min[i] << (i + 1 < n ? ' ' : '\n');
    for (int i = 0; i < n; i++) cout << best_max[i] << (i + 1 < n ? ' ' : '\n');
    return 0;
}