有一棵非常有趣的樹,它長得像下面這個樣子:
這棵樹很湊巧地,每一個分支點都恰好分出兩條樹枝,而這兩條樹枝形成一個90度的夾角,並與原本的主幹呈135度的角度。
我們可以將樹上的每一個分支點編一個號碼,而編號的方式是由內而外、順時針繞一圈依序編號而成。此外,上圖是一個層數為4的樹(從樹根1走到任何一樹梢恰好都要經過4根樹枝。)當然可以有層數更多的樹。
現在我們把這棵樹畫在平面上,並賦予它們座標,規定樹根1所在的位置座標為(0,0)。樹枝只有四種方向:與座標軸平行、垂直或呈45度夾角。而且同一層樹枝連接兩個分支點的座標值,其X和Y座標改變量都是0或2k-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 |