**Clarifications:**

I definitely think the description in this problem needs to be clarified as I initially read it. After reading some posts, I finally got exactly what it expected and restricted in this problem of the storytelling style (which is likely to introduce ambiguity).

**Here are the two key points that have to be clarified if you really want to work on this "poorly" defined problem**:

**A pig can be allowed to drink simultaneously on as many buckets as one would like, and the feeding takes no time**(!). I guess this is the really bizarre assumption hidden behind this story. And I finally got this point after reading some posts.**After a pig has instantly finished drinking buckets, there has to be a "cool down" time of**. During this time, only observation is allowed and no feedings at all. Actually, this is a derived hint from the problem instead of an assumption. Because after feeding on poison bucket, it is stated that a pig will die`minutesToDie`

minutes**within**`minutesToDie`

minutes instead of**exact**minutes. This means that if you feed a pig more than once in a time frame less that`minutesToDie`

minutes, there is no way to tell which feeding contains poison if the pig happens to die eventually

With the two key points above, I think the problem picked a "bad" story. Instead, it could be re-translated into a better story such as:

- Given
`N`

sources with exactly one of them sending bad signal. You are given`x`

receivers to detect which source is sending bad signal. A receiver can be configured to pick up signals from any number of specified sources. The bad signal will permanently damage a receiver within`minutesToDie`

minutes after received. Find the minimum`x`

if given`minutesToTest`

minutes to test.

**Solution:**

```
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
return ceil(log(buckets)/log(minutesToTest/minutesToDie+1)); // log_{T+1}(N)
}
```

**Proof:** For given `minutesToDie`

and `minutesToTest`

, with the clarification above, the only thing that matters here is the number of tests allowed `T = (int)(minutesToTest/minutesToDie)`

because of the "cool down" restriction. Then the problem is translated equivalently to:

**How many states can we generate with**to cover`x`

pigs and`T`

tests`N`

scenarios?

The number of states is exactly `(T+1)^x`

and here is why. For each pig during `T`

tests, it has exactly `T+1`

states: dies at some test#`i`

(`1<=i<=T`

) or still alive eventually. For `x`

pigs, obviously the maximum possible number of states we could have is `(T+1)^x`

since each pig's well-being solely depends on whether it ever fed on poison bucket and nothing to do with other pigs. So all we need to do is to

**find minimum**.`x`

such that`(T+1)^x >= N`

, which means`x = ceil(logN/log(T+1))`

Now we have the optimal candidate, but can we actually implement a feeding solution to achieve that optimum solution? Sure, here it is:

- Label buckets as a
`(T+1)`

-based number represented as`x`

-dimensional vector`v = (v[1], v[2], ...,v[x])`

consecutively ascending from`(0,0,...0)`

. (each`0<=v[j]<=T`

) - For each Test#
`i`

(`1<=i<=T`

), if all pigs are dead by now, process is finished. Otherwise, for each pig`j`

alive, feed it on all buckets with`v[j] = i`

simultaneously, and record its death time`D[j] = i`

if it dies after this test. - Default
`D[j] = 0`

if pig`j`

is still alive after all`T`

tests.

Then we claim that: **bucket with label (D[1],D[2],...,D[x]) must be the poison one**.

Because for each pig`j`

, by design of Step 2, it is guaranteed to be alive before feeding on bucket `(D[1],D[2],...,D[x])`

and all those pigs which have ever fed on this bucket died right after that test.