→ PyTorch: 大師 01/07 22:44
推 ririoshi: 大師 01/07 22:45
※ 編輯: SecondRun (118.241.148.203 日本), 01/07/2023 22:48:47
推 Che31128: 大師 01/07 23:00
458. 可憐的豬
給定b個水桶，其中一桶有毒
給定md為吃下毒到毒發作所需時間
你可以用以下步驟找到哪桶是毒
1.餵豬，每次實驗中一桶水桶可以餵很多豬，一隻豬也可以吃很多水桶
2.等待一段時間
3.看哪隻豬死了就可以縮小毒桶的範圍
給定mt為找到毒桶的時間限制
試問你最少需要多少隻豬才能把毒桶找出來?
ex. 自己看
https://i.imgur.com/Hfhnl7B.png
思考
如果我只有一隻豬
就只能一桶一桶試，最多b-1輪實驗可以找出來
(總共b桶且一定有一桶有毒
那麼前面b-1桶都沒死可以直接得到第b桶是有毒的結論)
而如果我有兩隻豬
那就可以把水桶排成一個二維陣列，一隻豬每次一列，一隻豬每次一排
然後就像是一隻豬的case一樣可以特定出哪一列哪一排得出答案
而三隻豬的情況
可以把水桶排成三維陣列，每隻豬分別對應一個dimension
依此類推
可以得到 (round+1)^pigs >= buckets 時，可以找出毒桶
取ln => ln((round+1)^pigs) >= ln(buckets)
=> pigs >= ln(buckets)/ln(round+1)
C#
https://i.imgur.com/jGjEKYw.png
結果錯了
打log出來發現
畢竟ln是無理數，拿來除會因為精度問題會有微小的誤差
這時再取ceiling就爆開了
C#
https://i.imgur.com/qOSj87C.png
這種情況不整理式子，讓變數都保持在int的情況去運算會更好
--
(づ′・ω・）づ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.241.148.203 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673102662.A.C88.html