TopCoder

i_am_noob
施~~廣~~霖~~

User's AC Ratio

90.4% (75/83)

Submission's AC Ratio

42.0% (124/295)

Tags

Description

在大陸人把冰塊排進他$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$的盒子就可以透過不斷模仿這個加倍的規律編號了!

然而,因為大陸人很懶,所以他決定要你幫他把冰塊的編號算出來。

Input Format

輸入只有一個非負整數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

Output Format

請輸出 2N 行,每行 2N 個數字,代表大陸人對每顆冰塊的編號。

Sample Input 1

2

Sample Output 1

0 1 14 15
3 2 13 12
4 7 8 11
5 6 9 10

Hints

Problem Source

Problem Set by Yihda Yol / edisonhello
建國中學106學年度校隊選拔:初試pC

Subtasks

No. Testdata Range Score
1 0~1 11
2 0~3 35
3 0~6 25
4 0~11 29

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1 2 3 4
1 1000 131072 262144 1 2 3 4
2 1000 131072 262144 2 3 4
3 1000 131072 262144 2 3 4
4 1000 131072 262144 3 4
5 1000 131072 262144 3 4
6 1000 131072 262144 3 4
7 1000 131072 262144 4
8 1000 131072 262144 4
9 1000 131072 262144 4
10 1000 131072 262144 4
11 1000 131072 262144 4