喝水试毒
==========

老鼠喝水
----------

**问题** ：有 :math:`n` 瓶水，有且仅有 1 瓶水有毒，老鼠喝到有毒的水之后会立即死亡。每只老鼠只能喝一次水（可以是多瓶水的混合），
请问找出有毒的水瓶至少要用多少只老鼠？

**答案** ： :math:`m = \lceil \log_2 n \rceil` 。

**策略** ：将水瓶进行二进制编号，第 :math:`k\ (1 \leqslant k \leqslant m)` 只老鼠喝编号第 :math:`k` 位为 1 的所有水瓶的混合水，如果该老鼠死亡，说明有毒的水瓶编号第 :math:`k` 位为 1 ，
否则为 0。例如， :math:`n=8,\ m=3` ，第 1 只老鼠喝 :math:`001, 011, 101, 111` ，第 2 只老鼠喝 :math:`010, 011, 110, 111` ，第 3 只老鼠喝 :math:`100, 101, 110, 111` ；
如果第 1 只老鼠和第 3 只老鼠死亡，第 2 只老鼠没死，则有毒水瓶的编号为 :math:`101` 。


可怜的小猪
-------------

**问题** ：[LeetCode] Poor Pigs。假设有 :math:`n` 只水桶，有且仅有一只水桶有毒。猪喝水中毒后会在 :math:`t` 分钟内死亡，请问至少需要多少只猪能在 :math:`T\ (T \geqslant t)` 分钟内找出有毒水桶？

  - 小猪可以同时饮用任意数量的桶中的水，并且该过程不需要时间。

  - 小猪喝完水后，必须有 :math:`t` 分钟的冷却时间。在这段时间里，只允许观察，不允许继续喝水。

  - 任何给定的桶都可以无限次采样。

**答案** ： :math:`m = \lceil \frac{\log n}{\log (T / t + 1)} \rceil` 。Hint：如果只用 1 只猪，在 :math:`T` 分钟内，可以喝 :math:`T/t` 桶水，因此可以找出 :math:`T/t + 1` 只水桶中的有毒水桶。

**策略** ：将水桶按 :math:`T/t + 1` 进制进行编号，第 :math:`k\ (1 \leqslant k \leqslant m)` 只猪在 :math:`0` 时刻喝编号第 :math:`k` 位为 0 的所有水桶的混合水，
在 :math:`t` 时刻喝编号第 :math:`k` 位为 1 的所有水桶的混合水，在 :math:`2t` 时刻喝编号第 :math:`k` 位为 2 的所有水桶的混合水 ……。以 :math:`n=25,\ t=15,\ T=60,\ m=2` 为例：

.. image:: ./20_poison.webp
    :align: center
    :width: 500px

参考资料
--------------

1. LeetCode 题解 | 458.可怜的小猪

  https://zhuanlan.zhihu.com/p/74663700