題目

• Example:

  1. 有1000個水桶，只有一個是有毒的，其餘的則裝滿水，你沒辦法分辨哪個是毒水。
  2. 如果小豬喝了毒藥，它將在15分鐘內死亡。
  3. 您需要在60分鐘內弄清楚哪個桶有毒的
     最少需要幾隻小豬才能做到？

• 請解決General case:

  1. 有buckets個水桶，只有一個是有毒的，其餘的則是一般的水，你沒辦法分辨哪個是毒水。
  2. 如果小豬喝了毒藥，它將在minutesToDie分鐘後死亡。
  3. 您需要在minutesToTest分鐘內弄清楚哪個桶有毒的
     最少需要幾隻小豬才能做到？

• Notes

  • 小豬能同時喝很多桶水，且喝的時間不考慮
  • 喝完後的m分鐘內，不能再進食。
  • 任何桶的水無限供應，小豬也無限供應。

分析

1. 首先，我們有
   • 桶數 buckets
   • 觀察時間 minutesToDie
   • 測試時間 minutesToTest
   • 求 小豬數 p
2. 測試次數T = 測試時間/觀察時間 (minutesToTest/minutesToDie)
   • 以上面的例子 T = 60/15 = 4
   • T很重要，代表每隻小豬最大能測試的次數!
   • minutesToDie與minutesToTest算完就沒用了
3. 再來我們觀察一下小的case:
   • buckets=2, T=1
   • 我們讓1隻小豬去試其中一桶
     • 小豬不幸死亡: 找到
     • 小豬不幸(?)活著: 代表沒被試的那桶有毒
   • Ans: p=1
     會發現測試次數只有1，但你其實隱式地測了1次，1+1=2
4. 讓我們換個角度: 有T與p，能測的最大桶數buckets為多少?
   1. T=1, p=2
      • Pig1 死, Pig2 活 -> 2有毒
      • Pig1 活, Pig2 死 -> 3有毒
      • Pig1 死, Pig2 死 -> 1有毒
      • Pig1 活, Pig2 活 -> 4有毒
      • 可測試 2^2 個桶子

   o -> 喝爆,  x -> 沒喝
   
   Bucket 1 2 3 4 
   Pig1   o o x x 
   Pig2   o x o x  
   

   2. T=2, p=2
      • Pig1 死, Pig2 活 -> 2,3其中有毒，還有一隻小豬能測試。
      • Pig1 活, Pig2 死 -> 4,5其中有毒，還有一隻小豬能測試。
      • Pig1 死, Pig2 死 -> 1有毒
      • Pig1 活, Pig2 活 -> 6,7,8,9其中有毒，2小豬都活著，使用上面例子即可測試出來。
      • 可測試 3^2 個桶子

   o -> 喝爆,  x -> 沒喝
   
   Bucket 1 2 3 4 5 6 7 8 9
   Pig1   o o o x x x x x x
   Pig2   o x x o o x x x x
   

5. 從4.1與4.2，我們可以看到能測試最大桶數
   buckets = (T+1)^p
6. 反推
   p >= log(T+1, buckets)
7. 阿這裡用C++的log function是以e為底的，即ln。 所以要換底一下。

Code

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int T = minutesToTest/minutesToDie;
        return  static_cast<int>(ceil(log(buckets) / (log(T + 1))));
    }
};