原問題
用三個異於零的相異數字共可組成六個不同的三位數，將此六個不同的三位數由小到大排序後第五個三位數扣掉第三個三位數再扣掉第一個三位數的結果為 246，試問最小的那個三位數是多少？
範例輸入
246
範例輸出
249
說明
2, 4, 9 這三個數字可組合成 249, 294, 429, 492, 924, 942
924 - 429 - 249 = 246
(from 奇摩知識+)
解答
假設最小的數為 $[abc]$ (中括號內代表連續位數)
這就代表三位數 $[abc]$ 中，$1 \leq{a} < b < c \leq{9}$
將所有組合可能由小到大排出來：
接著做運算：
$$\begin{aligned} & [cab] - [bac] - [abc] \\ = & 100 (c - b - a) + 10 (a - a - b) + (b - c - c) \\ = & 100 (c - b - a) + ( (-9) b + (-2) c) \\ = & 100 (c - (a + b)) - (9 b + 2 c) \end{aligned}$$從上面的形式可以推論出，後來的結果是由一個百位數減去一個數字
但是有可能會產生以下疑問
例如輸入 246
246 有可能是 300 - 54
又有可能是 400 - 154 = 500 - 254 = … 等等情況
如何判斷？
我們先看看 $(9 b + 2 c)$ 的值
因為 $1 \leq{a} < b < c \leq{9}$ 的關係
所以三個數最小為 $a = 1 < b = 2 < c = 3$
最大的可能為 $a = 7 < b = 8 < c = 9$
所以 $9\times{2}+2\times{3}\leq{9b+2c}\leq{9\times{8}+2\times{9}}$
$24\leq{9b+2c}\leq{90}$ 所以 254 拆解的組合一定為 300 - 54
得聯立方程式：
$$c - (a + b) = 3 \\
9 b + 2 c = 54$$
將上式帶入下式：
$$9 b + 2 (3 + (a + b)) = 54 \\
2 a + 11 b + 6 = 54 \\
2 a + 11 b = 48$$
窮舉 a 和 b 可得 $a = 2, b = 4, c = 3 + (2 + 4) = 9$
接著來看出來的數值範圍
如果要讓數值最小
首先要讓 $100 (c - (a + b))$ 盡可能地小，所以選 $a = 7, b = 8, c = 9$
$c - (a + b) = 9 - (7 + 8) = -6$
出來的數值為 $100\cdot{(-6)}-(9\cdot{8}+2\cdot{9})=-690$
反之如果要讓數值最大
則選 $a = 1, b = 2, c = 9$
$c - (a + b) = 9 - (1 + 2) = 6$
$100\cdot{6}-(9\cdot{2}+2\cdot{9}) = 600 - 36 = 564$
數值介於 $-690\leq{100}\cdot{(c - (a + b))}-(9b + 2c)\leq{564}$
因此樓上的 OOOOO 大第二段的 code 只適合在正值
(第3行 first_digit = num/100+1;
當數值在負值時 ex. first_digit = (-690)/100 + 1 = -5)
而所有出來數值數量，正好是 1 ~ 9 九個數字取 3 個做不重複組合
為 $C(9, 3) = (9\cdot{8}\cdot{7}) / (3\cdot{2}) = 84$ 種
因此一開始先用三層迴圈將結果預處理儲存起來
也是不錯的選擇
最後再考慮同一個數值，會不會來自兩種組合？
假設兩個不同的數字
$[abc] \neq{[a'b'c']} (1 \leq{a} < b < c \leq{9}, 1 \leq{a'} < b' < c' \leq{9})$
但是出來的結果卻是相同
$100 (c - (a + b)) - (9 b + 2 c) = 100 (c' - (a' + b')) - (9 b' + 2 c')$
剛才也討論過，出來的數值只有一種分解
因此
$$100 (c - (a + b)) = 100 (c' - (a' + b')) \\
9 b + 2 c = 9 b' + 2 c'$$
整理出 $c' = c - (a + b) + (a' + b')$ 代入下式
$$9 b + 2 c = 9 b' + 2 (c - (a + b) + (a' + b')) \\
9 b + 2 (a + b) = 9 b' + 2 (a' + b') \\
2 a + 11 b = 2 a' + 11 b' \\
2 (a - a') = 11 (b - b')$$
比較左右式的奇偶性，可知 a - a’ 為 11 的倍數，但因 $1 \leq{a , a'}\leq{7}$
唯一的組合 $a - a' = 0 \rightarrow{} a = a'$
回來看 $2 (a - a') = 11 (b - b')$
$2 (a - a') = 2 * 0 = 0$ 因此 $b - b' = 0 \rightarrow{} b = b'$
再回去看 $100 (c - (a + b)) = 100 (c' - (a' + b'))$
整理得 $c - c' = (a + b) - (a' + b') = (a - a') + (b - b') = 0 \rightarrow{} c = c'$
所以得到結論：$a = a', b = b', c = c'$
這意味著三位數 $[abc] = [a'b'c'] \rightarrow{}$與原假設矛盾
因此一個數值只會得到最多唯一一組解 (只有其中 84 組有解，其他都無解)
換句話說，不同的 $a, b, c$ 值會得到 84 個不同的數