e916: pD. 廁所的選擇
Tags :
Accepted rate : 5人/9人 ( 56% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-03-13 14:12

Content

有一群人要去上廁所,廁所有 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 的廁所。

Input

第一行有一個正整數 T,代表有 T 組測資(1 ≤ T ≤ 2*105)

每組測資有兩個正整數 n 和 k,
分別代表有 n 間廁所和第 k 個人(1 ≤ n ≤ 1018,1 ≤ k  ≤ n)

Output

第 k 個人所使用的廁所編號,編號由 1 開始

Sample Input #1
2
6 4
11 9
Sample Output #1
4
5
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (3%): 1.0s , <1K
公開 測資點#1 (3%): 1.0s , <1K
公開 測資點#2 (3%): 1.0s , <1K
公開 測資點#3 (3%): 1.0s , <1K
公開 測資點#4 (3%): 1.0s , <1K
公開 測資點#5 (3%): 1.0s , <1K
公開 測資點#6 (3%): 1.0s , <1K
公開 測資點#7 (3%): 1.0s , <1K
公開 測資點#8 (3%): 1.0s , <1K
公開 測資點#9 (3%): 1.0s , <1K
公開 測資點#10 (3%): 1.0s , <1K
公開 測資點#11 (3%): 1.0s , <1K
公開 測資點#12 (3%): 1.0s , <1K
公開 測資點#13 (3%): 1.0s , <1K
公開 測資點#14 (3%): 1.0s , <1K
公開 測資點#15 (3%): 1.0s , <1K
公開 測資點#16 (3%): 1.0s , <1K
公開 測資點#17 (3%): 1.0s , <1K
公開 測資點#18 (3%): 1.0s , <1K
公開 測資點#19 (3%): 1.0s , <1K
公開 測資點#20 (4%): 8.0s , <1K
公開 測資點#21 (4%): 8.0s , <1K
公開 測資點#22 (4%): 8.0s , <1K
公開 測資點#23 (4%): 10.0s , <1M
公開 測資點#24 (4%): 8.0s , <1K
公開 測資點#25 (4%): 8.0s , <1K
公開 測資點#26 (4%): 8.0s , <1K
公開 測資點#27 (4%): 8.0s , <1K
公開 測資點#28 (4%): 8.0s , <1K
公開 測資點#29 (4%): 6.0s , <1K
Hint :
Tags:
出處:
2019大學學測推甄申請二階 [管理者:
mushroom.cs9... (mushroom)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」