可怜的猪——458

概述

---

1000个桶，其中一桶里面有毒，猪喝了之后15分钟会死亡，其余桶里装的都是水。要求60分钟内找出有毒的是哪一桶，需要多少头猪？

进一步，有n个桶，其中1桶有毒，可以在m分钟内毒死猪，要求在p分钟内找出有毒的那一桶，求需要多少头猪？

原题

---

链接：https://leetcode.com/problems/poor-pigs/description/

There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.

Answer this question, and write an algorithm for the follow-up general case.

Follow-up:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the "poison" bucket within p minutes? There is exact one bucket with poison.

思路

---

这不是编程题，代码简单思路难。很明显一头猪一次不能只喝一桶里面的水，这样需要很多很多猪。应该要每头猪都喝很多桶，根据哪几头猪死了，判断他们都喝了的那一桶有毒。
首先，假设15分钟死亡，要求15分钟内找出有毒的桶，也就是每一头猪可以尝试一次。那么15分钟后，每头猪有两种状态，活着或者死亡，可以分别用0和1来代表，那么x头猪能代表最多2^x 种不同信息，也就是能从最多2^x 个桶里找出有毒的那一桶。
具体来说，假如有4个桶，2头猪，4个桶编号 00, 01, 10, 11，两头猪编号1，2。其中11号桶给两头猪都喝，10号给第一头猪喝，01号给第二头猪喝，00号两头猪都不喝。15分钟后，猪死了代表1，没死代表0，假如两头猪都死了，代表11，也就是11号桶有毒，第一头猪死了，第二头没死，代表10，也就是编号10的桶有毒，仅第二头死了，就是01的桶有毒，都没死就是00号桶有毒。
类似的，如果有8个桶，3头猪，八个桶编号是二进制的0~7，正好用三位二进制可以表示，其中三位的每一位对应一头猪，编号第一位是1的桶要给第一头猪喝，是0的不给第一头猪喝；第二位，第三位同理。最后死的猪对应位为1，没死的位为0，组成的二进制数正好是有毒的桶的编号。

因此，如果只有一次尝试机会，要从n个桶里面找出毒桶，只需⌈log(n)⌉头猪即可。
那么对于p>=2m，也就是可以尝试两次以上的情况呢？一开始可能会想到，如果可以尝试两次，就把桶平分成两份，每次测其中一半，转化为上面的问题。但是这样想的问题是，分成两份后，必然有一半的桶全都没有毒，而上面解法的前提是已知有且仅一个桶有毒。
我们可以这样想，假设能尝试两次，每头猪都可以表示的信息量是3，即没有死，第一次死了，第二次死了三种情况，分别用0，1，2 来代表，所以x头猪能区分最多3^x 中不同状态，也就是能从3^x 个桶中找出有毒的那一桶。桶的编号也改成三进制，仍然是每一位代表一头猪，0代表这头猪不喝这桶水，1代表第一次喝，2代表第二次喝。同样根据猪的死亡对应编号确定有毒的桶。

总结一下，x头猪，k次尝试，最多可以从x^k+1 个桶中找出毒桶。因此，答案是x=⌈log(n)/log(⌊p/m⌋+1)⌉（简书的Markdown下标打不出来，就用除法表示log的底数了）

代码

---

import math
class Solution(object):
    def poorPigs(self, buckets, minutesToDie, minutesToTest):
        """
        :type buckets: int
        :type minutesToDie: int
        :type minutesToTest: int
        :rtype: int
        """
        return int(math.ceil(math.log(buckets,minutesToTest//minutesToDie + 1)))