在大陸人把冰塊排進他$2^ N\times 2^ N$的盒子之後,他決定把每顆在盒子裡的冰塊都做個編號,從0編號到$2^ {2N}-1$。
然而,身為全世界唯一地大陸人,他不想像普通人一樣老老實實的從上到下、從左到右,或是用S型的方式把冰塊編號。他還希望,編號相鄰的冰塊在冰塊盒上也要相鄰,以方便他找冰塊。
在思考該怎麼將他的冰塊編號的時候,他看著他$2\times 2$的迷你冰塊盒,腦袋浮現了一個靈感。
他在冰塊盒上畫出了這樣的一條線:
從左上到右上,他決定幫冰塊按照這條線經過的順序編號。
決定了這個小盒子的編號順序之後,他拿了四個畫好線的$2\times 2$的冰塊盒,再拼成大一點的$4\times 4$冰塊盒。這時,他發現:只要把左上方的$2\times 2$冰塊盒逆時針轉90度、右上方的$2\times 2$冰塊盒順時針轉90度,下面兩個$2\times 2$方向保持不變,再按照原本$2\times 2$的順序(左上、左下、右下、右上)把線全部串起來,那麼編號就連續了!如下圖:
更棒的是,既然$2\times 2$的編號可以變成$4\times 4$的編號,那麼表示他$2^ N\times 2^ N$的盒子就可以透過不斷模仿這個加倍的規律編號了!
然而,因為大陸人很懶,所以他決定要你幫他把冰塊的編號算出來。
輸入只有一個非負整數N,代表冰塊盒的大小是2N 。
子任務(測資) | 額外限制 | 分數 |
1 (0~1) | $N\leq1$ | 11 |
2 (0~3) | $N\leq 3$ | 35 |
3 (0~6) | $N\leq 6$ | 25 |
4 (0~11) | $N\leq 11$ | 29 |
請輸出 2N 行,每行 2N 個數字,代表大陸人對每顆冰塊的編號。
Problem Set by Yihda Yol / edisonhello
建國中學106學年度校隊選拔:初試pC
No. | Testdata Range | Score |
---|---|---|
1 | 0~1 | 11 |
2 | 0~3 | 35 |
3 | 0~6 | 25 |
4 | 0~11 | 29 |