There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.
Answer this question, and write an algorithm for the follow-up general case.
Follow-up:
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 "poison" bucket within p minutes? There is exact one bucket with poison.
总共有1000个罐子,其中有且只有1个是毒药,另外其他的都是水. 现在用一群可怜的猪去找到那个毒药罐. 已知毒药让猪毒发的时间是15分钟, 那么在60分钟之内,最少需要几头猪来找出那个毒药罐?
解题思路：
一开始的时候陷入思维误区，准备采取二分法寻找，后来发现每个bucket都是一样的，只不过15分钟有可怜的猪遭殃的时候，才知道有毒的bucket大概会在哪里。然后就联想到与pow函数有关。
如果只有一只猪，考虑到间隔时间为15分钟，而测试时间是60分钟，所以一维的情况下，一只猪可以测出最多五只桶(为什么不是60/15, 4只呢，因为如果前面四个测试猪都没有死，则证明第五只桶有毒，但是不能六只桶，因为四次测试时间用完，会剩下两只，无法确定哪只有毒)。也就是说如果只有一只猪，可以最多检查(测试时间/毒发时间 + 1)个桶。
扩展到二维，则2只猪可以检查出5*5个桶，3个猪就是5^3个桶，因此到最后就是使用pow函数来和桶数进行比较。
import math
class Solution(object):
def poorPigs(self, buckets, minutesToDie, minutesToTest):
"""
:type buckets: int
:type minutesToDie: int
:type minutesToTest: int
:rtype: int
"""
time = minutesToTest/minutesToDie + 1
res = 0
while(math.pow(time, res)< buckets):
res=res+1
return res
if __name__ == "__main__":
sol = Solution()
print sol.poorPigs(1000, 15, 60)
print sol.poorPigs(5, 15, 60)
