a283. TOI 2022/03 潛力組：河內塔

題目描述

三根柱子的河內塔上有 N 個大小相異的圓盤，最小的編號為 1，最大的編號為 N。起初全部圓盤由小到大疊在最左柱，目標是全部移到最右柱。

一次只能移動一個最上方的圓盤，且大圓盤不能放在小圓盤上。每次都沿著總步數最少的解法移動。對每筆詢問，請回答第 S 步移動的是幾號圓盤。

輸入格式

第一行是詢問數 T，接著 T 行各有 N、S。

• 1 ≤ T ≤ 100000
• 2 ≤ N ≤ 30
• 1 ≤ S ≤ 2^N−1

輸出格式

每筆詢問輸出一行，內容是該步移動的圓盤編號。

來源

TOI 2022 年 3 月潛力組〈河內塔〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202203/Hanoi.pdf 題意核對鏡像：https://zerojudge.tw/ShowProblem?problemid=h664