458. Poor Pigs
給你b個桶子
其中包含一個有毒的桶子
你一共有t分鐘可以進行測試
然後你可以拿去讓豬喝
喝到有毒的桶會讓豬d分鐘後死亡
正在等待中的豬不能再喝其他的桶
請問當有b個桶子 測試一次要d分鐘 測驗時間共t分鐘的情況下
回傳進行測試最少需要的豬隻數量
Input: b = 4, d = 15, t = 15
Output: 2
讓A豬喝1,2桶 B豬喝1,3桶
判斷哪一桶有毒
A豬死亡:2桶
AB豬死亡:1桶
B豬死亡:3桶
沒有豬死亡:4桶
Input: b = 4, d = 15, t = 30
Output: 2
我沒有找到這一題的正確餵法
所以我沒有解出來
這邊先講我的思路:
首先t跟d兩個可以簡化成可以測試的次數time
time = floor(t/d)
然後我們要找到怎麼在有限次數內找到最佳解法
我想到的實驗方法是類似雙蛋問題的解決方法
可是這個方法不是最佳解
稍微講一下思路就好
如果我們有5隻豬 可以測驗三次
那我們第一次可以把桶分六堆
讓每隻豬各喝其中一堆 看哪一隻豬死掉 沒死掉就是剩下一堆有毒
之後把剩下的桶分五堆 前四堆讓四隻豬測試
最後剩下三隻豬 用binary的方法讓豬混著喝 可以測試最多8桶
然後根據前面分堆
可以得到5隻豬最多測試8*5*6=240桶
然後還要判斷豬沒死掉的話那一堆可以多測的桶數
但是這不是正解 我就沒有研究下去了
網路上的正解:
先計算我們一共可以測驗的次數time
如果time是4
代表我們可以分五堆
然後我們把桶子以二維的方式排列
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
接下來第一隻豬第一次測驗喝第一欄(1 6 11 16 21)
第二隻豬第一次測驗喝第一列(1 2 3 4 5)
測驗四次之後看豬在什麼時候死掉
如果第一隻豬第三次測驗死掉
第二隻豬第四次測驗死掉
代表第18桶有毒
都沒死掉代表第25桶有毒
這個方法可以讓我們透過兩隻豬及四次測驗分辨25個桶哪個有毒
可以得到公式 (time + 1)^pig = bucket
但是我們要找的是豬的數量
所以pig = log(time+1)bucket
然後log有公式 log(A)B = logB / logA
TS code:
function poorPigs (b: number, d: number, t: number): number {
const r = Math.log(b) / Math.log(Math.floor(t / d) + 1)
return r - Math.floor(r) > 0.001 ? Math.ceil(r) : Math.floor(r)
}
我在交答案的時候被TypeScript搞了一次
因為TS沒有整數 只有浮點數
我加一加冒出一個3.00000000000004