CSES 3159 - Replace with Difference

給你一個包含 \(n\) 個整數的陣列。你要對這個陣列做 \(n-1\) 次操作。

一次操作中，你會從陣列裡選兩個數 \(a\) 和 \(b\)，把它們兩個都從陣列裡刪掉，再把 \(|a - b|\) 放進陣列。

你的任務是找出一組操作序列，使陣列最後剩下的那個數是 \(0\)。

輸入格式

第一行有一個整數 \(n\)：陣列的長度。

下一行有 \(n\) 個整數 \(x_1, x_2,\dots, x_n\)：陣列的內容。

輸出格式

輸出 \(n-1\) 行，每行有兩個整數 \(a\) 和 \(b\)：每次操作所選的兩個數。任何一組合法答案皆可。

若無解，只輸出 \(-1\)。

範例輸入 1

5
2 7 4 12 1

範例輸出 1

2 12
7 10
4 1
3 3

說明：陣列的變化如下：

• \([2, 7, 4, 12, 1] \rightarrow\) 移除 \(2\) 和 \(12\)，加入 \(10\)

• \([7, 4, 1, 10] \rightarrow\) 移除 \(7\) 和 \(10\)，加入 \(3\)

• \([4, 1, 3] \rightarrow\) 移除 \(4\) 和 \(1\)，加入 \(3\)

• \([3, 3] \rightarrow\) 移除 \(3\) 和 \(3\)，加入 \(0\)

• \([0]\)：最後的陣列

限制

• \(2 \le n \le 1000\)
• \(1 \le x_i \le 1000\)

題目來源

CSES - Replace with Difference

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。