1-line solution with detailed problem clarification & math proof (please read if you really want to know what this problem means)
Clarifications:\nI definitely think the description in this problem needs to be clarified as I initially read it. After reading some posts, I finally got exactl
**Clarifications:**\nI 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).\n\n**Here are the two key points that have to be clarified if you really want to work on this "poorly" defined problem**:\n* **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.\n* **After a pig has instantly finished drinking buckets, there has to be a "cool down" time of `minutesToDie` minutes**. 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 **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\n\nWith 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:\n* 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.  \n***\n**Solution:**\n```\n    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {\n      return ceil(log(buckets)/log(minutesToTest/minutesToDie+1));  // log_{T+1}(N)\n    }\n```\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:\n\n* **How many states can we generate with `x` pigs and `T` tests** to cover `N` scenarios?\n\nThe 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 \n* **find minimum `x` such that `(T+1)^x >= N`, which means `x = ceil(logN/log(T+1))`**.\n\nNow we have the optimal candidate, but can we actually implement a feeding solution to achieve that optimum solution? Sure, here it is:\n1. 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`)\n2. 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.\n3. Default `D[j] = 0` if pig`j` is still alive after all `T` tests. \n\nThen we claim that: **bucket with label `(D[1],D[2],...,D[x])` must be the poison one**. \n\nBecause 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.
[]