每日一题 [1]-pigs

猪的故事

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.

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.

解：

最开始天真的以为猪是一次喝一桶，后来想到二分法，让n只猪每次喝buckets/n桶水，然后确定哪块有毒，然后接下去。。。

/**

* @param {number} buckets

* @param {number} minutesToDie

* @param {number} minutesToTest

* @return {number}

*/

var poorPigs = function(buckets, minutesToDie, minutesToTest) {

if(buckets == 1) return 0;

var pigs = 1;

var times = Math.floor(minutesToTest / minutesToDie);

while(buckets/Math.pow(pigs + 1, times) > 1){

pigs += 1;

}

return pigs;

};

然而，猪是会死的，所以二分法不靠谱。。。。。这道题的难度竟然是easy😭。。。。。。

求助别人，使用定位法。

如果有两头猪，有四次尝试机会，我们可以发现25桶里的毒药，使用5×5的矩阵来安排：

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

使用一只猪一行一行的尝试，另外一只猪一列一列的尝试，就可以确定哪行有毒哪列有毒了，因为有排除的方法，所以是五维的。依次类推，有三只猪的话，就可以构建5×5×5的矩阵。。。

所以，n只猪可以寻找5的n次方桶水。

/**

* @param {number} buckets

* @param {number} minutesToDie

* @param {number} minutesToTest

* @return {number}

*/

var poorPigs = function(buckets, minutesToDie, minutesToTest) {

if(buckets == 1) return 0;

var pigs = 1;

var times = Math.ceil(minutesToTest / minutesToDie);

while((times+1) ** pigs < buckets) pigs += 1;

return pigs;

};