梅林的母親買了一樣新玩具給梅林的妹妹,那是一副有三根柱子的河內塔。 梅林的妹妹收到玩具後雙手飛快的移動圓盤,不過聰明的妹妹沒一會兒就玩膩了, 把玩完的河內塔丟到一邊,於是梅林也想來試試看這個玩具。
河內塔由三根柱子和數個大小相異的圓盤構成。一開始所有圓盤由小到大堆 疊套在最左邊的柱子上,我們稱此時擺在最上方、最小的那個圓盤為 1 號圓盤, 1 號圓盤下方的一個圓盤為 2 號圓盤,依此類推。遊戲的目標是要把所有的圓盤都移動到最右邊的柱子上,但是要遵守兩個規則:(1)一次只能移動一個圓盤疊到 其中一根柱子最上方,以及(2)大的圓盤不可以疊在小的圓盤上方。
舉例來說,如果今天只有 2 個圓盤,那麼我們可以依照下面的方式,移動三 步來達成目標:第一步先把 1 號圓盤移到中間的柱子,第二步把 2 號圓盤移到右 邊的柱子,第三步再把剛剛移到中間的 1 號圓盤移到右邊的柱子疊在 2 號圓盤上 方,所以前三步的移動圓盤號碼分別是 1、2、1。
因為梅林沒有妹妹那麼聰明,所以他總是一直在跟別人要提示詢問現在應 該要移動哪一個圓盤。雖然他會一直詢問提示,但在詢問提示前他總是用最佳的方式在移動圓盤。
第一行有一個整數 T (1 ≤ T ≤ 100000) 代表詢問的數量。 接下來的 T 行每一行包含兩個整數 N (2 ≤ N ≤ 30)、S (1≤ S ≤ 2^N -1),代表該 筆詢問為 N 個圓盤的河內塔遊戲第 S 步應該移動幾號圓盤。
第一組(10 分):S 為奇數。
第二組(10 分):S ≤ 15。
第三組(35 分):T ≤ 100 且 N ≤ 15。
第四組(15 分):N ≤ 15。
第五組(30 分):限制如輸入格式。
請輸出 T 行,每一行有一個整數代表該筆詢問的答案。
4 3 6 5 16 9 331 18 98304
2 5 1 16
ID | User | Problem | Subject | Hit | Post Date |
32357 | suen333robot ... (Hello World) | h664 | 781 | 2022-10-02 13:24 | |
29877 | jeremydinger ... (164253) | h664 | 848 | 2022-04-08 08:12 |