Poison

作者 QIFAN 日期 2016-10-24
Poison

Source: Cracking the Code Interview 6.10


Description

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.
有1000瓶水,其中只有一瓶是有毒的;有10个试纸,如果水有毒,则试纸呈阳性(不可再用),若无毒的水,则没有反应(可以重复使用)。一天只能测试一次,一次测试七天后才能出结果。问最少需要多少天来测出有毒的瓶子?

思路

1000个瓶子,10个试纸,当然就是分组测试了。因为只有一瓶有毒,所以每次测试必然有且只有一张试纸变色。
而缩短时间的关键就在于并行多个test(再未显示结果时进行下一轮测试)

Solution

简单方法(28天)

0-7天:每100个分为一组,同一组组滴在同一张试纸上
7-14天:有一张试纸变色,说明毒水在该组。将毒水组分成9份,每组最多12个,最少11个
15-21天:(最坏情况下)12瓶的组变色,将该组分为8份,每组最多2个,最少一个
22-28天:若是单个组变色,毒水确定;若双个组变色,则需再进行一轮测试

优化方法(10天)

试想一下,1000个瓶子的编号若从0开始则都是三位数,如果三位数都确定了,那瓶子也确定了。因此可以想到将名字按照每一位数进行不同分组,每次测试可以确定毒水瓶对应位数。比如,第一次测试8号试纸变色,第二次测试2号试纸变色,第三轮试纸1号试纸变色,则可确定821号是毒水。但需要考虑例外情况,若某两位数是一样的,比如388和883的试纸变色情况一样。解决方式也很简单,只需要再加一轮测试,将个位数测试的顺序换一换,比如本来1号试纸测试个位数是0,换成测个位数是9的。所以如果是388号,则变色情况是3,8,8,9

试纸 0-7天 1-8天 2-9天 3-10天
1 1xx x1x xx1 xx0
2 2xx x2x xx2 xx1
3 3xx x3x xx3 xx2
4 4xx x4x xx4 xx3
5 5xx x5x xx5 xx4
6 6xx x6x xx6 xx5
7 7xx x7x xx7 xx6
8 8xx x8x xx8 xx7
9 9xx x9x xx9 xx8
10 0xx x0x xx0 xx9