「沒想到你就是那傳聞中擁有無限多間房間的希爾伯特啊!」兩人邊在暴風雨中小心翼翼又快速地前進,小向邊驚訝道。
「唉呀,我怎麼變那麼有名啦。」
「難怪在這暴風雨中你的旅館還有空位。」
「話別說的那麼簡單。你知道你一個人入住就要讓無限多個人搬家嗎?要不是看在剛剛你巧妙地解開了我的謎題,我可不想幹這種麻煩事。」話中夾雜了些許的抱怨口氣。
「也對……真是不好意思,辛苦你了。」小向帶著一點歉意答話。
「啊…其實也沒什麼啦。這個壞天氣…相信大家都會體諒的。」
說著說著,兩人走到了旅館。當然,希爾伯特成功地「挪」出了空房給小向。
「好好休息吧。然後……看看天氣轉晴之後…怎麼說呢…」
「?」
「我或許可以教你一些『把戲』。」
身為見習魔法少女,小向當然是能學則學。開心地答應了之後小向就回到了他的房間。
「!!!」地面突然開始搖晃,在暴風雨終於減弱的半夜裡睡著正香甜的小向被驚醒。衝出門外的小向發現她住的$N$號房以前的$N$個房間(編號0到$N-1$)的位置已被重新排列。「轟!」編號0到$N-2$的房間突然間各伸出一個橋,「咚!」地接到了編號1到$N-1$的某個房間。這種能操控大地的魔法到底是哪個大魔法師使出來的…儘管這是小向第一個想法,但是眼前的慘況可不容許她把腦子用在其它地方。想到了希爾伯特也住在裡面的某間房間的她,第一個想法就是儘快衝過去找希爾伯特。
冷靜下來以後,小向仔細觀察了目前的情勢。編號0到$N-1$的房間位置已被重排,由左而右的房間編號分別是$a_0,a_1,\dots,a_{N-1}$。而對於第$i$個位置,編號$a_i<N-1$的房間,如果在他左(右)側編號比他大的房子有$L(R)$棟且編號由小排到大是$b_0,b_1,\dots,b_{L-1}(c_0,c_1,\dots,c_{R-1})$,那麼他所伸出的橋梁連結的房間的編號就是$\min(b_{(L-1)/2},c_{(R-1)/2})$(這裡的除法無條件捨去,且如果$L(R)=0$,那麼$b_{(L-1)/2}(c_{(R-1)/2})=\infty$)。然而知道這些並沒有任何幫助。
「小向,聽得見嗎?」突然聲音在小向腦袋裡迴蕩。這是被稱為「念話」的一種魔法,能透由心念和其它人溝通。
「我是希爾伯特,我被困在房間裡了。雖然我不太清楚我在哪間房間裡,不過我可以確定我的房間周圍的橋梁不會比其它任何一間房間少。快…」
聲音就中止了。
「可惡…要是我的瞬間移動只要指定『人』而不用指定『目的地』就好了…」小向氣憤道。
不過,當務之急即是找到希爾伯特的所在地並瞬間移動過去。
第一行有一個正整數$2\leq N\leq 10^ 6$,代表被重排的房間個數。
之後一行有相異的$N$個整數$0\leq a_i<N$,代表重排後房間由左至右的編號。
子任務(測資) | 額外限制 | 分數 |
1 (0~2) | 房間沒有被重排 | 8 |
2 (3~7) | $N\leq 10^ 4$ | 16 |
3 (8~12) | $N\leq 10^ 5$ | 32 |
4 (13~17) | 無 | 44 |
輸出一個正整數,代表房間周圍的橋梁數的最大值。
編號0的房間伸出的橋梁連結到了編號$\min(\infty, 2)=2$的房間。
編號1的房間伸出的橋梁連結到了編號$\min(3, \infty)=3$的房間。
編號2的房間伸出的橋梁連結到了編號$\min(3, 4)=3$的房間。
編號3的房間伸出的橋梁連結到了編號$\min(\infty, 4)=4$的房間。
編號4的房間沒有伸出橋梁。
因此編號0的房間周圍有1座橋梁,編號1的房間周圍有1座橋梁,編號2的房間周圍有2座橋梁,編號3的房間周圍有3座橋梁,編號4的房間周圍有1座橋梁。
Problem Set / Description by Paupière
No. | Testdata Range | Score |
---|---|---|
1 | 0~2 | 8 |
2 | 3~7 | 16 |
3 | 8~12 | 32 |
4 | 13~17 | 44 |