題目連結：
題目大意：
現在有一數列 a，其 an = an-1 + inv(an-1)（n > 1） 且 a1 = 123。其中數列每一項 ai 為一個只會出現 1 、 2 、 3 這三個數字的數字串，而 inv(s) 則代表著將數字 s 中每個位數 x 替換為 4 - x。例如 inv(1123) = 3321。
可以看到數列 a 前三項為
a1 = 123、
a2 = 123321、
a3 = 123321321123
現在輸入第一列給定一正整數 T（T ≦ 100），代表有 T 筆測試資料，每筆佔一列。每列給定一正整數 K（1 ≦ K ≦ 10 ^ 9），試問 apcsh 從左數的第 K 個數字為何？其中 pcsh = 10 ^ 2015。
範例輸入：
3
4
5
10
範例輸出：
3
2
1
解題思維：
根據定義，每一項 ai（除了 a1）的長度將是前一項 ai-1 長度的兩倍，且 ai-1 將會是 ai 的前綴。因此每個 ai（除了 a1）可以分成左右半部。
假設對於給定的 K 值，所求為 F(K)。而此時我們來觀察範例輸入的 K = 10 之例子：
可以看到其位於 a3（其長度為 12）的右半側，等同於 a2 從右側數來第 4 個位數（即 K = 4）替換後的數值，即 F(10) = 4 - F(4)。
而 K = 4 位於 a2 的右半側，所以等價於替換後的 a1 之從左數來第 1 個位數（K = 1），即 F(4) = 4 - F(1)。
最後因為 F(1) = 1，所以 F(4) = 3，也因此推得 F(10) = 1。
而其他的 K 值也可以按照類似以上的步驟來求得所求。
因此我們先計算出 a1 ～ a30（雖然 apcsh 這個項次非常地長，但是由於 K 只會到 10 ^ 9，所以 a30 就夠用了）每個項次的長度並建成一個表格可供查詢。然後對每個給定的 K 值從 a1 開始去找第一個 ai 其長度 ≧ K 者（除非 K ≦ 3，此時可以直接得出答案），而答案會是 4 - F(K - |ai| ÷ 2)，其中 |ai| 為 ai 之長度。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
