c057: 逃出地下牢房
Tags : DP
Accepted rate : 2人/4人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-01 19:10

Content

忍者從昏睡中醒來後,發現自己身處一個類似地下牢房的狹小房間。唯一出口只有天花板的一個被堵住的開口。

忍者在地板上 發現一個巨大轉盤,上面有 1 至 100 個刻度。 忍者試著把轉盤轉到指針對準 50 之處,小房間四面突然湧進大量的水,差點把忍者嗆死。

忍者又試著把轉盤轉到指針對準 75 之處,水繼續灌進房間內。忍者把轉盤轉到指針對準 80 之處,結果這次不是水,而是刺鼻的毒氣開始漫進房間裡,

忍者只能開始憋氣,忍者努力把轉盤轉到指針對準 76 之處,天花板的開口突然框的一聲 打開,他奮力摸上濕滑的牆壁,努力攀到天花板的出口,終於逃出這個可怕的牢房。

他後來回想起,如果他轉到的刻度比76 小,房間就會灌水進來,如果他轉到的刻度比 76 大,則 是噁心的毒氣噴進房間。

在以上的敘述中,在天花板的開口打開以前,忍者每次轉動到的刻度之總和為 50+75+80=205

給定有 1~N 共 N 個刻度的轉盤(N<=1000),在天花板的開口打開以前,請問忍者每次轉動到的刻 度之「總和」最少為多少,才能「保證」他在被淹死/毒死/窒息之前猜到正確的刻度逃出房間?

 

以只有 1~3 共 3 個刻度的轉盤為例。如果忍者一開始先轉到 1,而正確刻度不是 1,必須繼續轉到 2 或是 3。忍者會優先轉到較小的刻度,因為即使猜錯,總合也比較低。因此先轉到 1 的刻度 總合是 1+2=3。如果忍者先轉到 2,而正確刻度不是 2,必須繼續轉到 1 或是 3。因為忍者能從水 或毒氣知道正確刻度比 2 大或是小,之後保證能猜對讓天花板開口打開,因此先轉到2的刻度總合是 2。如果忍者一開始先轉到 3,而正確刻度不是 3,必須繼續轉到 1 或是 2。忍者會優先轉到較小的刻度,因為即使猜錯,總合也比較低。因此先轉到 1 的刻度總合是 3+1=4。以上三個刻度 總合分別為 3、2 和 4,最小為 2,因此忍者 1~3 共 3 個刻度的轉盤時轉到刻度的總合為 2 時能保 證他猜到正確答案使開口打開。

Input

刻度數目 N,N<=1000

Output

上述所敘之轉動刻度的「總和」

Sample Input
3
Sample Output
2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint :

「保證」可以逃出房間意味著有一個策略使得不管正確刻度是哪裡都有辦法在該總和下逃出。

以N=5為例:

一開始選4,如果正確刻度(以下稱X) = 4就成功逃出。

如果X > 4,會有毒氣灌入,所以這時選5可以成功逃出。

如果X < 4,會有水灌入,這時可以選2,此時無論X是多少,總是可以在下一次逃出。

所以答案就是2+4=6

Tags:
DP
出處:
HP codewars [管理者:
810848 (路過)
]


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