有一群人要去上廁所，廁所有 n 間(編號為1, 2, ..., n)，有 k 個人要使用。
因為沒有人想要使用隔壁有人的廁所，因此在選擇廁所的時候會離別人越遠越好。
第一個人會選第 1 間，第 2 個人會選第 n 間，
從第 3 個人開始，會依序照下列規則選擇：
對於編號 i 的空廁所，假設左邊最近有人使用的廁所編號是 Li，右邊最近有人使用的廁所編號是 Ri
1. 選擇 min( i-Li, Ri-i ) 最大者
舉例來說，如果有兩間廁所，
前者離左邊被使用的廁所有 1 格，離右邊被使用的廁所有 100 格
後者離左邊被使用的廁所有 5 格，離右邊被使用的廁所有 8 格
則因為 min(5, 8) > min(1, 100)，所以會選擇後者。
2. 上述規則仍無法比較時，選擇 max( i-Li, Ri-i ) 最大者
舉例來說，如果有兩間廁所，
前者離左邊被使用的廁所有 5 格，離右邊被使用的廁所有 100 格
後者離左邊被使用的廁所有 5 格，離右邊被使用的廁所有 8 格
則因為 max(5, 100) > max(5, 8)，所以會選擇前者。
3. 上述規則仍無法比較時，選擇編號 i 最小者
也就是盡可能選靠左邊的廁所
假設現在有 n 間廁所(編號為1, 2, ..., n)，請問第 k 個人會選擇第幾間？
舉例來說，
當 n = 6，k = 4
使用順序依序為 1, 6, 3, 4，因此第 4 個人使用編號 4 的廁所。
當 n = 11，k = 9
使用順序依序為 1, 11, 6, 3, 8, 4, 9, 2, 5，因此第 9 個人使用編號 5 的廁所。
第一行有一個正整數 T，代表有 T 組測資（1 ≤ T ≤ 2*105）
每組測資有兩個正整數 n 和 k，
分別代表有 n 間廁所和第 k 個人（1 ≤ n ≤ 1018，1 ≤ k ≤ n）
第 k 個人所使用的廁所編號，編號由 1 開始
2 6 4 11 9
4 5
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||