h664.
河內塔 (Hanoi)
內容
梅林的母親買了一樣新玩具給梅林的妹妹，那是一副有三根柱子的河內塔。 梅林的妹妹收到玩具後雙手飛快的移動圓盤，不過聰明的妹妹沒一會兒就玩膩了， 把玩完的河內塔丟到一邊，於是梅林也想來試試看這個玩具。
河內塔由三根柱子和數個大小相異的圓盤構成。一開始所有圓盤由小到大堆 疊套在最左邊的柱子上，我們稱此時擺在最上方、最小的那個圓盤為 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 行，每一行有一個整數代表該筆詢問的答案。
範例輸入
#1
4 3 6 5 16 9 331 18 98304
範例輸出
#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
不公開 測資點#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
提示 ：
標籤:
出處:
TOI練習賽202203潛力組第3題
[管理者：
linlincaleb@
...
(臨末之頌)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 32357 |
|
h664 | 768 | 2022-10-02 13:24 | |
| 29877 |
|
h664 | 839 | 2022-04-08 08:12 |