458.可怜的小猪

原题

一、进制

d为实验对象的反应时间，t为测试总时间

最大测试次数为k=⌊d/t⌋。

1. 先从简单情况开始，k=1

用一个二进制表示液体编码，二进制的第i位$x_i$为1表示该液体由第i只猪测试。例如8桶水，二进制编码3位，用3只即可测试完：第0只猪负责1(001),3(011),5(101),7(111)号液体，若第0只猪中毒，说明$x_0$为1的液体有毒，否则$x_0$为0的液体无毒；再用第1只猪测试2，3，6，7号液体，看$x_1$的状态；依次类推，3只小猪测试完就可得到有毒液体每一位的编号，也就确定了有毒液体是哪一桶。

1. 复杂情况，k>1

相当于在原问题基础上，多考虑一层「轮数」维度，即不仅考虑某个实验对象是否有所反应，还需要考虑是在哪一轮有所反应。

先使用 k + 1 进制对所有水进行编号，此时每桶水都有唯一的进制表示编码。然后我们考虑「什么时候」将水喂给「哪个实验对象」。

其中一种可行的测试方式是：设定需要的实验对象数量 m 为 k+1 进制数的长度，若某桶水的 k+1 进制中的第 x 位为 i（0 <= i <= k），则代表将该水在第 i 轮喂给编号为 x 的实验对象。

详细推导参考

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