### 题目

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.

### 问题描述的补充

• 猪可以同时喝很多杯水
• 毒药发作的15分钟是一个大约范围，不是说一定是15*60秒后死亡。所以想让猪每一秒喝一杯水，然后按秒表计时的做法不可行。
• 判断一杯水有没有毒，就要让一头猪喝这杯水，然后等15分钟，15分钟以后猪没死，就说明没毒，否则就是有毒。

### 用N维坐标定位一杯水

15m  15m  15m  15m
|    |    |    |
1    2    3    4    5



• 猪1号按列[1,6,11,16,21]这么喝。5杯水一起喝，喝完等15分钟出结果。
• 猪2号按行[1,2,3,4,5]这么喝。也一次喝5杯水，喝完等15分钟出结果。

1个小时之后，这杯水在第几行，第几列我们就知道了。

猪1号
15m  15m  15m  15m
|    |    |    |
1    2    3    4    5  <- 15min 猪2号
6    7    8    9   10  <- 15min
11   12   13   14   15  <- 15min
16   17   18   19   20  <- 15min
21   22   23   24   25


(minutesToTest / minutesToDie + 1) ^ pigs >= buckets

#### 代码

class Solution {
public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
if (buckets == 1) return 0;
int len = (minutesToTest / minutesToDie + 1);
for (int pigs = 1, product = 1; pigs <= buckets; pigs++) {
product *= len;
if (product >= buckets) return pigs;
}
return 0;
}
}