h664: 河內塔 (Hanoi)
Tags :
Accepted rate : 22人/27人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-02 15:12

Content

梅林的母親買了一樣新玩具給梅林的妹妹,那是一副有三根柱子的河內塔。 梅林的妹妹收到玩具後雙手飛快的移動圓盤,不過聰明的妹妹沒一會兒就玩膩了, 把玩完的河內塔丟到一邊,於是梅林也想來試試看這個玩具。

河內塔由三根柱子和數個大小相異的圓盤構成。一開始所有圓盤由小到大堆 疊套在最左邊的柱子上,我們稱此時擺在最上方、最小的那個圓盤為 1 號圓盤, 1 號圓盤下方的一個圓盤為 2 號圓盤,依此類推。遊戲的目標是要把所有的圓盤都移動到最右邊的柱子上,但是要遵守兩個規則:(1)一次只能移動一個圓盤疊到 其中一根柱子最上方,以及(2)大的圓盤不可以疊在小的圓盤上方。

舉例來說,如果今天只有 2 個圓盤,那麼我們可以依照下面的方式,移動三 步來達成目標:第一步先把 1 號圓盤移到中間的柱子,第二步把 2 號圓盤移到右 邊的柱子,第三步再把剛剛移到中間的 1 號圓盤移到右邊的柱子疊在 2 號圓盤上 方,所以前三步的移動圓盤號碼分別是 1、2、1。

因為梅林沒有妹妹那麼聰明,所以他總是一直在跟別人要提示詢問現在應 該要移動哪一個圓盤。雖然他會一直詢問提示,但在詢問提示前他總是用最佳的方式在移動圓盤。

Input

第一行有一個整數 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 分):限制如輸入格式。

Output

請輸出 T 行,每一行有一個整數代表該筆詢問的答案。

Sample Input #1
4
3 6
5 16
9 331
18 98304
Sample Output #1
2
5
1
16
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.0s , <10M
不公開 測資點#1 (10%): 1.0s , <1M
不公開 測資點#2 (35%): 1.0s , <1K
不公開 測資點#3 (15%): 1.0s , <1M
不公開 測資點#4 (25%): 1.0s , <1M
不公開 測資點#5 (1%): 1.0s , <10M
不公開 測資點#6 (1%): 1.0s , <10M
不公開 測資點#7 (1%): 1.0s , <10M
不公開 測資點#8 (1%): 1.0s , <10M
不公開 測資點#9 (1%): 1.0s , <10M
Hint :
Tags:
出處:
TOI練習賽202203潛力組第3題 [管理者:
linlincaleb@... (臨末之頌)
]


ID User Problem Subject Hit Post Date
29877
jeremydinger... (布丁pudding164253)
h664
思路
129 2022-04-08 08:12