題目連結：
題目意譯：
現在有 buckets 桶的液體，其中恰好一桶是有毒。為了分辨哪一桶是有毒的，你需要餵某些（可憐的）豬一些液體來看它們會不會蹺辮子。不幸的是，你只有 minutesToTest 分鐘可以決定哪一桶是有毒的。
你可以根據以下步驟來餵食這些豬：
選出幾頭活著的豬來餵食；
對於每一頭豬，選擇要餵牠哪幾桶的液體。她將會同時吃下所有選擇出來的液體，而且不會花費任何時間。每一頭豬可以被餵予任何數量的桶子裡之液體，而任何桶子裡的液體可以餵給任何數量的豬。（譯者注：更精確地描述，每桶液體可以不必餵給任何一頭豬；而每隻豬可以不被餵食任何液體。）
等待 minutesToDie 分鐘。這段期間不得餵養任何豬；
經過 minutesToDie 分鐘後，任何有被餵到有毒的那一桶的豬將會死亡，而其他豬將會存活；
重複以上步驟直到你耗完所有時間。
給定 buckets 、 minutesToDie 和 minutesToTest，回傳要在給定的時間內，辨別哪一桶液體有毒最少所需豬隻之數量。
限制：
1 ≦ buckets ≦ 1000
1 ≦ minutesToDie ≦ minutesToTest ≦ 100
範例測資：
範例 1：
輸入： buckets = 4, minutesToDie = 15, minutesToTest = 15
輸出： 2
解釋： 如下，我們可以決定出有毒的液體桶：
時間點 0，餵第一隻豬 1 號和 2 號桶，然後餵第二隻豬 2 號和 3 號桶。
時間點 15，現在有 4 種可能的結果：
- 如果只有第一隻豬死蹺翹，則 1 號桶一定有毒。
- 如果只有第二隻豬死蹺翹，則 3 號桶一定有毒。
- 如果兩隻豬都死蹺翹，則 2 號桶一定有毒。
- 如果兩隻豬沒有死蹺翹，則 4 號桶一定有毒。
範例 2：
輸入： buckets = 4, minutesToDie = 15, minutesToTest = 30
輸出： 2
解釋： 如下，我們可以決定出有毒的液體桶：
解釋： 如下，我們可以決定出有毒的液體桶：
時間點 0，餵第一隻豬 1 號桶，然後餵第二隻豬 2 號桶。
時間點 15，現在有 2 種可能的結果：
- 如果某一隻豬死蹺翹，則餵給那隻豬的那一桶液體一定有毒。
- 如果沒有任何一隻豬死蹺翹，則餵第一隻豬 3 號桶，然後餵第二隻豬 4 號桶。
時間點 30，其中某一隻豬一定會死蹺翹，而有毒的就是餵給死掉的那隻的那一桶液體。
解題思維：
首先只看一隻豬最多可以經歷多少種可能性：
已知我們將執行 T 輪的餵食測試，其中 T = 「minutesToTest ÷ minutesToDie 取整數」。則單一一隻豬可能在第一輪死亡、也可能在第二輪死亡、……、或是第 T 輪死亡，又或是幸運通過了 T 輪測試都沒有死亡。因此總計 T + 1 種可能性。
因此我們可以看到一隻豬可以決定出最多 T + 1 桶的液體哪一桶有毒——即依序編號，並依序餵食，然後看該豬隻在哪輪死亡；而如果活過每一輪則可以知道是沒有被餵食的那一桶有毒。
那我們加入另一隻豬呢？可以決定出的最多桶數是 (T + 1) + (T + 1) 嗎？不，是 (T + 1) × (T + 1) 才對。而有 p 隻豬的話，則最多桶數為 (T + 1) ^ p。
令這些桶子的編號為從 0 到 (T + 1) ^ p - 1，對於某個編號 i 的桶子將其轉換成一個 (T + 1) 進位且固定為 p 位數長的數字。接著我們從最低位（最右側）開始依序對應到每一隻豬（也一併編號 0 到 p - 1；而對應關係實際上的怎麼對應的不重要，只要這個對應關係在所有桶子中的一樣的即可）。
對於第 j 個位數，其可能的值只會是 0（含）～ T（含）之間的數字（畢竟是一個 (T + 1) 進位的數字）。而當其值為 1，則編號 i 這個桶子安排在第 j 隻豬的第 1 輪測試、數值為 2 則安排在第 2 輪、數值為 3 則在第 3 輪、……、數值為 T 則安排在最後一輪（即第 T 輪），而數值 0 則代表完全不在這隻豬身上測試 i 號桶子。
因此我們可以看到這 (T + 1) ^ p 個桶子正好一一對應著 p 隻豬的所有可能的生死狀態。因此不管哪個桶子有毒都可以測出來，但是如果再多加一個桶子則就不行了（豬隻的生死狀態不夠用）。
所以我們要找到一個數字 p，使其滿足
(T + 1) ^ p ≧ buckets
因此對兩邊取對數，則得到
p × log(T + 1) ≧ log(buckets)
根據等量公理把 log(T + 1) 移到右側（該值必正，所以不需要擔心正負號），得
p ≧ log(buckets) ÷ log(T + 1)
而因為 p 是整數，因此 p 之值為上式右側取整後之結果，即為所求最少所需豬隻。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
