TopCoder

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

86.2% (25/29)

Tags

Description

有一棵非常有趣的樹,它長得像下面這個樣子:

這棵樹很湊巧地,每一個分支點都恰好分出兩條樹枝,而這兩條樹枝形成一個 $90$ 度的夾角,並與原本的主幹呈 $135$ 度的角度。

我們可以將樹上的每一個分支點編一個號碼,而編號的方式是由內而外、順時針繞一圈依序編號而成。此外,上圖是一個層數為 $4$ 的樹(從樹根 $1$ 走到任何一樹梢恰好都要經過 $4$ 根樹枝。)當然可以有層數更多的樹。

現在我們把這棵樹畫在平面上,並賦予它們座標,規定樹根 $1$ 所在的位置座標為 $(0,0)$。樹枝只有四種方向:與座標軸平行、垂直或呈 $45$ 度夾角。而且同一層樹枝連接兩個分支點的座標值,其 $X$ 和 $Y$ 座標改變量都是 $0$ 或$2^ {k-1}$,其中 $k$ 為由外而內樹枝所在層數。

依照這樣的規則,給你這棵樹的層數,以及某一個分支點的編號,請問這個分支點所在的座標為何?

Input Format

輸入包含兩個數字:$n$ 以及 $m$,其中 $n$ 代表層數,$m$ 代表欲求座標的分支點編號。
你可以假設所有輸入都是合乎規定的。也就是說,分支點 $m$ 一定會在層數為 $n$ 的樹上。

答案不會超過 32bit-signed integer 的範圍。

Output Format

請輸出兩個數字,分別為分支點 $m$ 的 $X$ 座標和 $Y$ 座標。

Sample Input 1

範例輸入1
4 6

範例輸入2
30 1

Sample Output 1

範例輸出1
-4 14

範例輸出2
0 0

Hints

Problem Source

原TIOJ1570 / 97建中校內資訊能力競賽(prob1)

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

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
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10