leetcode 458 Poor Pigs
z
 2019-06-10 18:30:10  

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the poisonous bucket within p minutes? There is exactly one bucket with poison.

  1. A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time.
  2. After a pig has instantly finished drinking buckets, there has to be a cool down time of m minutes. During this time, only observation is allowed and no feedings at all.
  3. Any given bucket can be sampled an infinite number of times (by an unlimited number of pigs).

假设现在一共有25个桶，2只猪，每只猪在喝完水后有15分钟的观察时间，一共有60分钟的时间供我们找出有毒的水桶。这样就意味着我们一共可以进行四轮验证。

对着25桶水，我们这样对它们进行排列：

1
2
3
4
5
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

对于第一只猪，我们按行来验证，第一次给它喝下第一行的水，第二次给它喝下第二行的水。

在对第一只猪操作的同时，我们在第一次为第二只猪喝下第一列的水，第二次给它喝下第二列的水。

假设第一只猪在第i次喝完水后挂了，第二只在第j次喝完水后挂了，那么有毒的水就是第i，j个桶。

如果第一只猪在四次实验后还活着，说明有毒的水在第5行。也就是说，虽然我们只能验证4轮，但是我们可以设置5行(列)

那么，每一只猪相当于是一个维度。每一个维度上，一共有(验证次数+1)个桶组成一个超立方体。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def poorPigs(self, buckets, minutesToDie, minutesToTest):
        """
        :type buckets: int
        :type minutesToDie: int
        :type minutesToTest: int
        :rtype: int
        """
        test_times = minutesToTest//minutesToDie
        pig = 0
        while (test_times + 1) ** pig < buckets:
            pig += 1
        return pig