有一棵非常有趣的樹,它長得像下面這個樣子:
這棵樹很湊巧地,每一個分支點都恰好分出兩條樹枝,而這兩條樹枝形成一個 $90$ 度的夾角,並與原本的主幹呈 $135$ 度的角度。
我們可以將樹上的每一個分支點編一個號碼,而編號的方式是由內而外、順時針繞一圈依序編號而成。此外,上圖是一個層數為 $4$ 的樹(從樹根 $1$ 走到任何一樹梢恰好都要經過 $4$ 根樹枝。)當然可以有層數更多的樹。
現在我們把這棵樹畫在平面上,並賦予它們座標,規定樹根 $1$ 所在的位置座標為 $(0,0)$。樹枝只有四種方向:與座標軸平行、垂直或呈 $45$ 度夾角。而且同一層樹枝連接兩個分支點的座標值,其 $X$ 和 $Y$ 座標改變量都是 $0$ 或$2^ {k-1}$,其中 $k$ 為由外而內樹枝所在層數。
依照這樣的規則,給你這棵樹的層數,以及某一個分支點的編號,請問這個分支點所在的座標為何?
輸入包含兩個數字:$n$ 以及 $m$,其中 $n$ 代表層數,$m$ 代表欲求座標的分支點編號。
你可以假設所有輸入都是合乎規定的。也就是說,分支點 $m$ 一定會在層數為 $n$ 的樹上。
答案不會超過 32bit-signed integer 的範圍。
請輸出兩個數字,分別為分支點 $m$ 的 $X$ 座標和 $Y$ 座標。
原TIOJ1570 / 97建中校內資訊能力競賽(prob1)
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 |