458. 可怜的小猪

题目链接：458. 可怜的小猪

测试的轮次，即 minutesToTest // minutesToDie，考虑只测试一轮的情况：

将所有的桶编号，比如 $bucket = 1000$ 个桶，编号为 $0, 1, 2, \dots, 999$，将该编号表示为二进制，即

根据桶的编号的二进制表示的对应位上，是否为$1$，可以将桶分为 $\lceil\log_2{bucket}\rceil$ 组，每只小猪喝对应组的液体，等到了时间，根据死去的小猪，可以还原出有毒的桶的二进制编号。此时，最少需要的小猪数量是 $\lceil\log_2{bucket}\rceil$。

考虑测试多轮的情况 $iteration > 1$：

• $1$ 只小猪，最多可以测试 $iteration + 1$ 个桶，如果前 $iteration$ 次没死，说明第 $iteration + 1$ 个桶有毒；
• $2$ 只小猪，最多可以测试 $(iteration + 1)^2$ 个桶，此时，可以如上，每个桶按二进制编码，总共可以测试 $iteration + 1$ 位二进制数可以表示的数量个桶；
• 以此类推，$3$ 只小猪，每个桶按三进制编码，总共可以测试 $iteration + 1$ 位三进制数可以表示的数量个桶，即 $(iteration + 1)^3$；
• 综上，多轮测试时，$n$ 只小猪，总共可以测试 $(iteration + 1)^n$ 只桶。

那么，在有 $(iteration + 1)^{n-1} < bucket \le (iteration + 1)^n$ 只桶的情况下，能够测试出有毒的桶所需的小猪的最少数目即 $n$。 \(n = \lceil\log_{iteration+1}{bucket}\rceil\) 代码如下：

import math


class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        return math.ceil(math.log2(buckets) / math.log2(minutesToTest // minutesToDie + 1))