#44303: 數學好玩好玩欸


Ixcy (Ixcy)

學校 : 國立宜蘭高級中學
編號 : 290988
來源 : [36.229.217.38]
最後登入時間 :
2025-01-08 21:43:30
f447. 12918 - Lucky Thief -- UVA12918 | From: [36.229.241.123] | 發表日期 : 2024-11-22 21:55

根據題意,每個鑰匙能與其中一個且唯一一個門配對
所以以下為了方便,我們為小偷制定一個方法:

從第一扇門開始往下測試直到對應到正確的門

如果開到倒數第二扇門仍未成功,那麼同意最後一扇門是正確的。

接著以第一行測資(4,6)為例:
1234
004321
可得知最糟糕的情況需要5+4+3+2次
根據n m便可推得需要(((m-1)+(m-n))*n)/2次

話說回來
題目的意思應該是指同一把鑰匙不試同一扇門
最多需要多少次吧
不然最少次數不就是n嗎

 
ZeroJudge Forum