TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

98.8% (84/85)

Submission's AC Ratio

75.5% (145/192)

Tags

Description

拼拼樂會議中心是一個N×N 的超大型可分割式會議中心。

每一個1×1 的空間都可以用隔板隔開,因此該會議中心最多可以有n2 個獨立的1×1 會議室,如要較大的會議室,則需將隔板拿掉使得二或更多個相鄰的1×1 空間可以合併使用。

圖一的會議中心最多可分隔成169 個1×1 小會議室,最少則全部合併成為一個13×13 的會議室。

每間1×1 會議室皆以其二維平面座標為編號。選定一個1×1 會議室並給予編號 (0,0),相鄰的上、下、左、右會議室編號則依序為 (0, 1), (0, -1), (-1, 0), (0, 1)。會議中心外租會議室時,必須按照下列規則,組成合乎需求的會議室。一開始先以編號為(0, 0) 的空間供租用,如果空間不足,則依序向右方、上方、左方、下方的空間合併成為較大的會議室。

每次擴充時,新加入的空間必須為正方形且該邊長必須與相鄰的擴充前會議室邊長相同,如此才能確保合併後的會議室一定是四方形。

以下圖為例,第一次擴充租用空間時,右邊編號為 (1, 0) 的會議室空間會被跟編號為 (0,0) 的會議室合併。

第二次擴充時,在 (0, 0), (1, 0) 上方的四個(2×2 正方形)小會議室會被合併進來。

第三次擴充時,在 (0,0) ~ (0, 3) 左邊的 9 個 (3×3 正方形)小會議室會被合併進來。

第四次擴充時,在 (-3,0) ~ (1,0) 下方的 25 個 (5×5 正方形)小會議室會被合併進來。

第五次擴充時,在 (0,-5) ~ (0,2) 右方的 64 個 (8×8 正方形)小會議室會被合併進來。後續的擴充則依此類推。

現在,若給定一個n 的值,請計算第n 次擴充時的正方形會議室的邊長。

Input Format

只有一個整數n, n≦45。

Output Format

請輸出第n 次擴充時的正方形會議室的邊長。

Sample Input 1

2

Sample Output 1

2

Sample Input 2

5

Sample Output 2

8

Hints

Problem Source

原TIOJ1476 / 96北市賽
建中校內培訓第五次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

No. Testdata Range Score
1 0 14
2 1 14
3 2 14
4 3 14
5 4 14
6 5 14
7 6 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7