ZeroJudge a532: 奇特的數列

有一個數列的前十項：0、1、8、11、69、88、96、101、111、181，這個數列是在一次考古研究中發現，考古學家想要知道這個數列的後續發展，或許能預測人類的未來。你的任務是寫一支程式求得這個數列的任一項數值。

輸入：每行一個十進位正整數 N（0 < N ≤ 1000000），以 N = 0 代表輸入結束。

(試圖非常正式地)分析

正當我在仔細尋找數列前後項的數學關係時， PCC 告訴我這題的規律是 ambigram，也就是上下顛倒後和本來一樣的數。深夜裡經過幾次隨意 (naive) 地推論之後，挫折的我決定用正經的方式思考問題。

於是我們可以寫出以下定義：令這個數列中的所有數所成的集合為 S，且對於數字所成的字串 S，int(S) 表示其數值的形式，

V_1 = { '0', '1', '8' }
V_2 = { '11', '69', '88', '96' }
X ∈ V_1 → int(X) ∈ S
X ∈ V_2 → int(X) ∈ S
int(X) ∈ S → int('6' X '9') ∈ S && int('9' X '6') ∈ S
int(X) ∈ S → int('1' X '1') ∈ S && int('8' X '8') ∈ S

除了這樣定義的元素，其他的元素都不屬於 S。仔細端詳一下，確定這個定義沒有問題以後，接著就是幫這個集合內的數字們排序。若 S 為字串，令 len(S) 為其長度，

很顯然地有這些性質，

X ∈ V_1 → len(X) = 1
X ∈ V_2 → len(X) = 2
len(X Y) = len(X) + len(Y)

並且我們可以藉此明確地定義大小關係：

len(X) < len(Y) → int(X) < int(Y)

你可能會忍不住想到 int(X) ∈ S → int('1' X) < int('6' X) < int('8' X) < int('9' X)，但形如 '1' X 等字串，其數值形式不一定是 S 的元素，這可以依照需要改成以下：

int(X) ∈ S → int('1' X '1') < int('6' X '9') < int('8' X '8') < int('9' X '6')

於是我們可以終於幫 S 中的數排列大小關係，並且據此填出數列的後續項。

長度為 1 的元素有 0, 1, 8
長度為 2 的元素有 11, 69, 88, 96 (因為規則裡並沒有辦法用兩個長度為 1 的元素構造出長度為 2 的元素)
再來比較不這麼顯然一些，我們並沒有明確定義長度為 3 的元素，而是用上面的性質，構造出長度為 1 + 2 的元素
於是長度為 3 的元素共計有 101, 111, 181, 609, 619,689, 808, 818, 888, 906, 916, 986 這 12 (= 3 * 4) 種
長度為 4 的元素共計有 16 (= 4 * 4) 種

以上這些列舉的元素根據 len 的定義，都是嚴格遞增的，因此我們毫無遺漏地舉出了數列的前幾項。可以用歸納法 (induction) 證明，長度為 2n (> 2) 的元素共有 4 ^ n 個，長度為 2n - 1 的元素共有 3 * 4 ^ (n - 1) 個。並且若將這些數字依據最高位、最低位兩個字元分類，可以分為 4 類，且每類的元素一樣多。

更進一步地，
長度不大於 2n (> 2) 的元素有 3 + 4 + 3 * 4 ^ 1 + 4 ^ 2 + ... + 4 ^ n (= 7 * (4 ^ n - 1) / 3) 個；
長度不大於 2n - 1 的元素有 (7 * (4 ^ n - 1) / 3) - 4 ^ n (= (4 ^ (n + 1) - 7) / 3) 個；
也可以說是數列的前多少項是由長度為 n 的字串組成。

梳理一下上面的過程，對於每個整數 n，我們可以先看看這一項的長度，判斷這個數字的最高位是幾，再一步一步遞迴生成其他項。

複雜度分析

設 N 為欲求的項數，若能用適當的方法取 log2，可以用 O(1) 時間知道一個數字的長度 L，只需要逐次確定每個位數，這樣需要進行 L/2 次，又 L ~ log_4(N)，可知時間複雜度為 O(log N)。

題目說 N ≤ 1000000，於是根據上面的分析，所要求數列第 N 項，其字串形式的長度上界，以其中一種方式 (2n) 粗略估計約為 log_4(1e6 * 3 / 7) + 1，約為 10.35，因此其字串形式長度至多為 floor(2 * 10.35)，即 20。

Sample Code (WIP)