Poison: You have 1000 bottles of soda, and exactly one is poisoned. You have 10 test strips which can be used to detect poison. A single drop of poison will turn the test strip positive permanently. You can put any number of drops on a test strip at once and you can reuse a test strip as many times as you’d like (as long as the results are negative). However, you can only run tests once per day and it takes seven days to return a result. How would you figure out the poisoned bottle in as few days as possible?
FOLLOW UP
Write code to simulate your approach.
Hlnts: #146, #163, #183, #191, #205, #221, #230, #241, #249
解法1
把1000个样本分成10组，每组100个，分别在10根试纸上测试
- 7天后：知道某组里有毒，试纸剩9根
- 样本100个，分10组，每组11个，最后一组1个
- 7天后，知道某组里有毒，试纸剩8根
- 样本11个，分9组，每组1个，最后一组2个
- 7天后，知道某组里有毒，试纸剩余7根
- 样本2个，分2组，每组1个
- 7天后，确定哪个有毒
最差情况28天。
解法2
如果你有7个样本，一个试纸，那你怎么最快知道哪个样本有毒？
你可以第1天滴样本1，第2天滴样本2，第3天滴样本3，……，因为已知7天后试纸会发生反应，那么如果第7天发生反应就意味着样本1有毒，第8天发生反应意味着样本2有毒，第13天发生反应意味着样本7有毒。所以最慢第13天就能测出来。
也就是说1根试纸可以当7根用，那么10根试纸可以当70根用，那么把1000个样本分为70组，每组15个样本，然后同时测，最慢13天之后能够知道哪15个样本有毒。
此时试纸还剩9根，我们可以取8根，每根第一天点1滴，第二天点1滴。比如这样负责：
- 1号试纸负责样本1、2
- 2号试纸负责样本3、4
- 3号试纸负责样本5、6
- 8号试纸负责样本15
那么最慢8天之后能够知道哪个样本有毒。
这样就是最差情况13 + 8 = 21天可以测完全部1000个样本。
不过这个结果还可以优化的，比如第一轮测试1根试纸当4根用，那么最慢10天就能知道哪25个样本有问题。然后第二轮每根试纸当3根用，那么最慢9天就能知道那个样本有问题，最慢19天可以测完。
解法3(最优)
如果把10根试纸看作10个bit，那么它一共能代表210=1024个数字，因此可以hold住1000个瓶子。
把1000个瓶子从1～1000编号，然后将其编号的二进制数字对应的1 bit滴到10根试纸里。
最后看哪3个bit是1，然后就能知道是哪个瓶子有问题了。
所以只要7天就能知道结果。
评论