p**********9
发帖数: 101 | 1 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
， 怎么能最快找到最小的miss掉的数。C＋＋ |
m***s
发帖数: 605 | 2 1. 二进制
2. 5只老鼠可以测31瓶。10只62瓶？
3. 就地对应放进去以后扫描？ 应该是O(n)吧？
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
d********e
发帖数: 132 | 3
怎么个二进制法？
【在 m***s 的大作中提到】
: 1. 二进制
: 2. 5只老鼠可以测31瓶。10只62瓶？
: 3. 就地对应放进去以后扫描？ 应该是O(n)吧？
|
f*******g
发帖数: 79 | 4 Try 2：the information we need to identify 2 in 1000 is C(2,1000) and the
information we can get from 10 mice is 2^10. Assume we have n bottles of
wine undetermined. we should have
C(2,n)=C(2,1000)/1024
so we get n=32. |
p*******t
发帖数: 213 | 5 lost. the information we can get from 10 mice is 2^10? why? |
j*****4
发帖数: 292 | 6 1.use binary for bottle number, pour some in the kth mouse's glass if the
kth bit is 1.
2.if n(10>n>1) mice die, then 1000-(2^n-1) are non-poisonous.??
if n=10,it could be more complex coz there are just 1000 bottles of wine
rather than 1024.
3.bitmap?
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
s*****v
发帖数: 360 | 7 >> 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
Why can't we use *one single rat* to try the wine one by one. |
m*****n
发帖数: 2152 | 8 2 不要用二进制，最少能测800瓶没毒，每个老鼠不重复喝100瓶，最多两个毒死。
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
m*****n
发帖数: 2152 | 9 他给的题目不全，是时间不允许，必须要同时喝。
【在 s*****v 的大作中提到】
: >> 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: Why can't we use *one single rat* to try the wine one by one.
|
s********r
发帖数: 529 | 10 第一道题目和以前那个两个玻璃瓶测一百层楼那个是不是一个系列的？
好像版内有总结的，可以用任意多个球搞任意多个楼层，但是我不确定这个题目这么做
是不是最优解。。。
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
|
|
s*******r
发帖数: 60 | 11 第3题貌似最简单的方法是用（1+...+100）- 实际的和=偏差 来判定？
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
w*****e
发帖数: 197 | 12 这个应该是正解
【在 m*****n 的大作中提到】
: 2 不要用二进制，最少能测800瓶没毒，每个老鼠不重复喝100瓶，最多两个毒死。
|
f***a
发帖数: 329 | 13 Good one~! :D
After several tests, the mouse will be so drunk and lose reaction that you
can't even tell the effect is from poison or from alcohol. So this way
won't work. :)
【在 s*****v 的大作中提到】
: >> 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: Why can't we use *one single rat* to try the wine one by one.
|
f***a
发帖数: 329 | 14 先分成k份（3<=k<=10）然后用k个老鼠去喝，这个方法挺好的。
不过就是要找出optimized的k,貌似k=4挺好的,比k=10好。
【在 m*****n 的大作中提到】
: 2 不要用二进制，最少能测800瓶没毒，每个老鼠不重复喝100瓶，最多两个毒死。
|
m*****n
发帖数: 2152 | 15 那是缺一个数，这个可能缺n个数。
貌似可以这么做
#include
using namespace std;
int main ()
{
unsigned int array[100] = {/*randnumber*/};
unsigned int array2[100] = {0};
for(int i=0; i<100; ++i) array2[array[100]-1] = 1;
int j=0;
while(array2[j]) ++j;
cout << j+1 << endl;
}
【在 s*******r 的大作中提到】
: 第3题貌似最简单的方法是用（1+...+100）- 实际的和=偏差 来判定？
|
m*****n
发帖数: 2152 | 16 看来大家老是误解题意，原题是这样的， 1000瓶酒，10个老鼠，老鼠喝了10分钟毒发
，无论毒药剂量
大小。如果两瓶毒酒，问只有10分钟可以测几瓶无毒的？
分4份然后怎么测？
【在 f***a 的大作中提到】
: 先分成k份（3<=k<=10）然后用k个老鼠去喝，这个方法挺好的。
: 不过就是要找出optimized的k,貌似k=4挺好的,比k=10好。
|
c******r
发帖数: 300 | 17 If no sequential design is allowed, then make 11 groups and test ten out of
them, you should be able to identify 9 out of the 11 groups that contains no
poison, so roughly you can get
floor(9/11*1000)=818
though not sure whether this is optimal
【在 m*****n 的大作中提到】
: 看来大家老是误解题意，原题是这样的， 1000瓶酒，10个老鼠，老鼠喝了10分钟毒发
: ，无论毒药剂量
: 大小。如果两瓶毒酒，问只有10分钟可以测几瓶无毒的？
: 分4份然后怎么测？
|
m*****n
发帖数: 2152 | 18 恩，是更好一点。
of
contains no
【在 c******r 的大作中提到】
: If no sequential design is allowed, then make 11 groups and test ten out of
: them, you should be able to identify 9 out of the 11 groups that contains no
: poison, so roughly you can get
: floor(9/11*1000)=818
: though not sure whether this is optimal
|
s*****y
发帖数: 33 | 19 1024 = 2^10 = 1+C(10,1) + C(10,2) +...+C(10,10)
Give each mouse a number, then you can use the 1000 out of 1024 combinations
of mice to drink the 1000 beers, if one of the combinations of mice died
after 10 mins, then you know the corresponding beer is poissoned.
【在 m*****n 的大作中提到】
: 恩，是更好一点。
:
: of
: contains no
|
m*****n
发帖数: 2152 | 20 Are you talking about one poisoned bear? But we are discussing two
poisoned bear case.
combinations
died
【在 s*****y 的大作中提到】
: 1024 = 2^10 = 1+C(10,1) + C(10,2) +...+C(10,10)
: Give each mouse a number, then you can use the 1000 out of 1024 combinations
: of mice to drink the 1000 beers, if one of the combinations of mice died
: after 10 mins, then you know the corresponding beer is poissoned.
|
|
|
b********a
发帖数: 5418 | 21 for(int i=0; i<100; ++i) array2[array[100]-1] = 1;
这句没有用到 i 啊。。。
【在 m*****n 的大作中提到】
: 那是缺一个数，这个可能缺n个数。
: 貌似可以这么做
: #include
: using namespace std;
: int main ()
: {
:
: unsigned int array[100] = {/*randnumber*/};
: unsigned int array2[100] = {0};
: for(int i=0; i<100; ++i) array2[array[100]-1] = 1;
|
m***s
发帖数: 605 | 22 array[i]
【在 b********a 的大作中提到】
: for(int i=0; i<100; ++i) array2[array[100]-1] = 1;
: 这句没有用到 i 啊。。。
|
t******t
发帖数: 40 | 23 太麻烦了。排序之后，找最小的数然后去减i, i从1开始i++，如果有最小的数有多个，
就减一次，然后弃掉这个数找下一个，减的结果不是0就是最小的miss的数.
【在 m*****n 的大作中提到】
: 那是缺一个数，这个可能缺n个数。
: 貌似可以这么做
: #include
: using namespace std;
: int main ()
: {
:
: unsigned int array[100] = {/*randnumber*/};
: unsigned int array2[100] = {0};
: for(int i=0; i<100; ++i) array2[array[100]-1] = 1;
|
m*****k
发帖数: 731 | 24 perm 被audit期间， h1B 用光了，是不是必须回国或转身份。 |
r*******y
发帖数: 290 | 25 if perm petition is submitted 1 year before expiration date of H1b, you are
fine
【在 m*****k 的大作中提到】
: perm 被audit期间， h1B 用光了，是不是必须回国或转身份。
|
M*****y
发帖数: 666 | 26 my old one is flawed.
new one:
divide into 6*6 grid
use five on x-axis, and the other five on y-axis
so 4/36 can be identified as possible poison.
so 1000*8/9 = 888 |
c******r
发帖数: 300 | 27 Interesting. But why don't do a three-way design?
It seems if you do 3*3*4, at most
2/4*2/4*2/5 = 1/ 10 will not be identifiable. So you can get 900 in the end.
i feel this might not be the optimal solution though.
【在 M*****y 的大作中提到】
: my old one is flawed.
: new one:
: divide into 6*6 grid
: use five on x-axis, and the other five on y-axis
: so 4/36 can be identified as possible poison.
: so 1000*8/9 = 888
|
v*******y
发帖数: 1586 | 28 能再讲讲第一题用二进制怎么做吗...
我好弱... |
c*******7
发帖数: 17225 | 29 第三个放好以后先排序。
不要用三种基本形式排序。
或者简单一点，用第一个数和第二个数字比较，如果小，就取小的再和下一个比较。
反正他说要最小的，有没有说要保留这100个数字。不过也是O(n)
anyway .为什么版上中秋不发包子啊。 |
i*****r
发帖数: 1302 | |
|
|
s*********8
发帖数: 107 | |
g*****a
发帖数: 340 | 32 1. 720瓶分10份，分别喝，如果毒死一个，有毒那份继续分9份，肯定再毒死一个，剩
下8个，一个耗子一瓶，应该就能出来了。
如果第一次没毒，换280那个，分10份，死一个，分9份，一份4瓶的，死一个，最后剩8
个耗子3～4瓶酒
最后expected value 0.72*3+ 0.28*4 = 3.28次可以找出来
还有没有更优化的？小于3.28的？有公式么？
2. 我能想到的，100个一份，一下能出来至少800瓶没毒的。但如果不限次数，就又要
分情况讨论咯。。。
第一次分100瓶一份，毒死一个跟两个，分情况
然后如果开始分两次，再分两个分支呢？会好一点么？
3. 1到100的随机数，放到数组中，找出最小miss那个...
可以用Set
Set s;
while(int ii < 100){
s.insert(generator(1,100));
ii ++;
}
for(ii = 1 ; ii < 100 ; ii ++){
if(!s.contains(ii)){
return ii;
}
}
should be O(n)
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
d********e
发帖数: 132 | 33 "好像版内有总结的", 在哪？
找了半天，没找到。好心人给各联接吧！
【在 s********r 的大作中提到】
: 第一道题目和以前那个两个玻璃瓶测一百层楼那个是不是一个系列的？
: 好像版内有总结的，可以用任意多个球搞任意多个楼层，但是我不确定这个题目这么做
: 是不是最优解。。。
|
V*********y
发帖数: 37 | 34 第二题
考虑最坏情况:
能找到
(250+125+62+31)*2 = 936 没毒？
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
v*******y
发帖数: 1586 | 35 喝酒那个可以这样喝吗
第一个喝1-150，第二个100-250，第三个200-350....最后一个900-1000-50
这样只有2个相邻的老鼠挂了，能测出来950瓶
有相邻的挂了，能测出来900瓶 |
m**********4
发帖数: 774 | 36 1. I think this is a binary search type of question...
2. no idea
3. build a harsh table, from 1-100. O(1), go over the array. O(n). If the
array is sorted, you can do it pretty fast, like O(lgn). Now I think you
need a sequential search.
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
D***a
发帖数: 939 | 37 1. 是不是要有两个假定：
i）每个老鼠只能喝一次
ii）只要有毒，不管计量多少，都会毒死老鼠
这样的话，我的方法是：
如果两瓶酒中一瓶有毒，这样只要让一只老鼠喝其中的一瓶，就能知道哪瓶酒有毒了；
如果四瓶酒中有一瓶有毒，就需要两只老鼠，具体做法是先将4瓶酒分两份，每份两瓶
，先将其中的两瓶酒混合了给第一只老鼠喝，如果没事，就让第二只老鼠来区分剩下的
两瓶，如果挂了，就让第二只老鼠来区分这两瓶酒；以此类推，十只老鼠就能搞定 2^
10=1024瓶酒，所以1000瓶酒也就可以搞定了
为什么这么考虑？
首先题目中没说这1000瓶酒中有什么关联，就意味着这1000瓶酒至少都要被喝一次才能
测出来那瓶酒有毒，那只有混合着喝了 |
D***a
发帖数: 939 | 38 每只老鼠都能喝很多次的话，那一只老鼠就够了，呵呵 |
z****e
发帖数: 54598 | 39 哎呀，看了半天，我说怎么看怎么觉得题目有问题呢
要是有空，我用一只老鼠都可以一直测到有毒那瓶为止
【在 m*****n 的大作中提到】
: 看来大家老是误解题意，原题是这样的， 1000瓶酒，10个老鼠，老鼠喝了10分钟毒发
: ，无论毒药剂量
: 大小。如果两瓶毒酒，问只有10分钟可以测几瓶无毒的？
: 分4份然后怎么测？
|
w*******x
发帖数: 489 | 40 2. I guess:
(48-2)/48*1000=958
use 3,(3+1),4, or 2,2,2,2,(2+1) lattice to divide groups. we can use one
blank row that is the extra +1 come from.
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
|
|
M*****d
发帖数: 100 | 41 3,(3+1),4,情况下，可能有6只老鼠死掉，这样有8个cell都可能有毒
结果应该是1000*（48-8）/48=833
用这种factorial的实验设计，前面chopinor的做法应该是最佳了，可以有分出900瓶
【在 w*******x 的大作中提到】
: 2. I guess:
: (48-2)/48*1000=958
: use 3,(3+1),4, or 2,2,2,2,(2+1) lattice to divide groups. we can use one
: blank row that is the extra +1 come from.
|
B****n
发帖数: 11290 | 42 我想是因為這樣的話你無法分辨它是酒精中毒還是酒裡有毒
【在 s*****v 的大作中提到】
: >> 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: Why can't we use *one single rat* to try the wine one by one.
|
t*****j
发帖数: 1105 | 43 第一道题是 2^10 = 1024 > 1000.
第二道题不会。
第三道题：O(n)时间 O(1) space.对数组两次scan,第一次swap，第二次核对。
【在 p**********9 的大作中提到】
: 1. 1000瓶酒，其中一瓶有毒，用10只老鼠来测，怎么能测出来哪瓶有毒？
: 2. 如果有2瓶酒有毒呢？能测出多少瓶酒没毒
: 3. 一个random generater制造了1－100的整数， 现在要放进一个size 100 的array里
: ， 怎么能最快找到最小的miss掉的数。C＋＋
|
p****x
发帖数: 707 | 44
4 bottles, 2 mouses example
bottles 0-3 (00 01 10 11)
cup: 1 (01) 2 (10)
bottles( 1&3 ) --> cup 1
bottles( 2&3 ) --> cup 2
drink results:
no mouse die 00
only mouse 1 die 01
only mouse 2 die 10
mouse 1&2 die 11
【在 v*******y 的大作中提到】
: 能再讲讲第一题用二进制怎么做吗...
: 我好弱...
|
t*****j
发帖数: 1105 | 45 what about 二分法？
200 200 200 200 200， 每个各分100分，和下一组的100分混合
200 200 200 200 200(首尾连接)
worst case也是200, best case也是100，但是好像best case概率高些。
【在 w*****e 的大作中提到】
: 这个应该是正解
|
