万粥帮帮我解一下这道题

babypig
猪爸爸 2017-03-03 字数 622

10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

BTW:

1. 毒酒喝到就必死,一点点都不行,一个毒酒分子的剂量喝到了都必死好嘛。。。

2. 大家看清题啊,2天内必须找出来,还有1天的毒发周期,找不出来国王的酒会没法办了

3. 死的人是没办法继续验酒的

4. 必须验出具体是哪一桶酒,其他9999桶酒酒会上都会被喝掉,少一桶都不行,不然酒不够,酒会上和酒会后国王请来的贵宾不允许出任何事故

5. 方案必须能保证到最后一定能验出来,毕竟任何极端情况都有可能,绝对不能靠运气,国王的酒会输不起,只有2天时间

Joke 笑话连篇
27 个Like
520 个回复
R11
史上最强11号--Romario 2017-03-03

二进制位数?

【 在 babypig (猪爸爸) 的大作中提到: 】

: 标  题: 万粥帮帮我解一下这道题

: 发信站: 水木社区 (Fri Mar  3 10:39:27 2017), 站内

: 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

: --

changer
ChPAANNG-君子无故,玉不离身 2017-03-03

一半一半的来试?

【 在 babypig (猪爸爸) 的大作中提到: 】

: 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

gaofei
高飞 2017-03-03

最少一个就行

【 在 babypig (猪爸爸) 的大作中提到: 】

: 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

babypig
猪爸爸 2017-03-03

有时间限制

【 在 gaofei (高飞) 的大作中提到: 】

: 最少一个就行

babypig
猪爸爸 2017-03-03

注意有时间限制,人死就不能试了

【 在 changer (ChPAANNG-君子无故,玉不离身) 的大作中提到: 】

: 一半一半的来试?

xuppp
爱德华王子岛 2017-03-03

条件给的不足

酒会至少需要多少桶酒

毒酒的最低有效剂量

一个人的最大饮酒量

【 在 babypig (猪爸爸) 的大作中提到: 】

: 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

babypig
猪爸爸 2017-03-03

毒酒喝到就死,一点点都不行

【 在 xuppp (爱德华王子岛) 的大作中提到: 】

: 条件给的不足

: 酒会至少需要多少桶酒

: 毒酒的最低有效剂量

: ...................

xuppp
爱德华王子岛 2017-03-03

那如果酒会的需求量没有限制

直接2个人,每人试5000桶,不就行了

【 在 babypig (猪爸爸) 的大作中提到: 】

: 毒酒喝到就死,一点点都不行

babypig
猪爸爸 2017-03-03

看清题,有时间限制,还有毒发周期

【 在 xuppp (爱德华王子岛) 的大作中提到: 】

: 那如果酒会的需求量没有限制

: 直接2个人,每人试5000桶,不就行了

xuppp
爱德华王子岛 2017-03-03

我是说无毒的5000桶就够用了

剩下的都扔了

【 在 babypig (猪爸爸) 的大作中提到: 】

: 看清题,有时间限制,还有毒发周期

yanliushang
烟柳伤 2017-03-03

应该是100个人吧,第一次每人喝100桶酒,死掉一个人,第二次99个人在死掉的这个人的100桶酒中各喝一桶,死掉的就是那通,都没死就是剩下的那桶是毒酒

【 在 babypig 的大作中提到: 】

: 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

iEric
Eric 2017-03-03

大概思路

day1:

囚犯1 喝 1-5000

囚犯2 喝 5001-10000

囚犯3 喝 1-2500 5001-7500

囚犯4 喝 2501-5000 , 7501-10000

囚犯5 喝 1-1250, 2501-3750, 5001-6750,  7501-8750

囚犯6 喝 1251-2500,3751-5000, 6751-7500, 8751-10000

每次分一半给两个犯人....

通过十来个个犯人第一天结束就能 确定大概100桶酒有问题,

然后第二天再让,10来个犯人就能试出来了。

【 在 babypig (猪爸爸) 的大作中提到: 】

: 标  题: 万粥帮帮我解一下这道题

: 发信站: 水木社区 (Fri Mar  3 10:39:27 2017), 站内

: 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

: BTW:

: 1. 毒酒喝到就必死,一点点都不行

: 2. 大家看清题啊,2天内必须找出来,还有毒发周期,找不出来国王的酒会没法办了

: --

babypig
猪爸爸 2017-03-03

不是最优解,继续

出题人说最优解比这个少很多

【 在 yanliushang (烟柳伤) 的大作中提到: 】

: 应该是100个人吧,第一次每人喝100桶酒,死掉一个人,第二次99个人在死掉的这个人的100桶酒中各喝一桶,死掉的就是那通,都没死就是剩下的那桶是毒酒

allwar2
无昵称 2017-03-03

14人,这个题目很老了

aphei
一切归于平静 2017-03-03
libro
简简单单 2017-03-03

不是按照day来算,按照小时算。

因为小时可以推测有问题的组。

【 在 iEric (Eric) 的大作中提到: 】

: 标  题: Re: 万粥帮帮我解一下这道题

: 发信站: 水木社区 (Fri Mar  3 11:02:43 2017), 站内

: 大概思路

: day1:

: 囚犯1 喝 1-5000

: 囚犯2 喝 5001-10000

: 囚犯3 喝 1-2500 5001-7500

: 囚犯4 喝 2501-5000 , 7501-10000

: 囚犯5 喝 1-1250, 2501-3750, 5001-6750,  7501-8750

: 囚犯6 喝 1251-2500,3751-5000, 6751-7500, 8751-10000

: 每次分一半给两个犯人....

: 通过十来个个犯人第一天结束就能 确定大概100桶酒有问题,

: 然后第二天再让,10来个犯人就能试出来了。

: 【 在 babypig (猪爸爸) 的大作中提到: 】

: : 标  题: 万粥帮帮我解一下这道题

: : 发信站: 水木社区 (Fri Mar  3 10:39:27 2017), 站内

: :

: : 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

: :

: : BTW:

: : 1. 毒酒喝到就必死,一点点都不行

: : 2. 大家看清题啊,2天内必须找出来,还有毒发周期,找不出来国王的酒会没法办了

: : --

: :

: --

libro
简简单单 2017-03-03

大约是

0-m小时里。(m<24)

一个人第一小时,喝 n桶样品,第二小时喝n,第m小时喝n桶。

一个人能够验证mn桶。

k个人。

nmk>10000?

然后第二天剩下的k-1个人确认n桶就行了。

k-1=n最优?

似乎可以解方程了。

【 在 libro (简简单单) 的大作中提到: 】

: 标  题: Re: 万粥帮帮我解一下这道题

: 发信站: 水木社区 (Fri Mar  3 11:03:29 2017), 站内

: 不是按照day来算,按照小时算。

: 因为小时可以推测有问题的组。

: 【 在 iEric (Eric) 的大作中提到: 】

: : 标  题: Re: 万粥帮帮我解一下这道题

: : 发信站: 水木社区 (Fri Mar  3 11:02:43 2017), 站内

: :

: :

: : 大概思路

: : day1:

: : 囚犯1 喝 1-5000

: : 囚犯2 喝 5001-10000

: :

: : 囚犯3 喝 1-2500 5001-7500

: : 囚犯4 喝 2501-5000 , 7501-10000

: :

: : 囚犯5 喝 1-1250, 2501-3750, 5001-6750,  7501-8750

: : 囚犯6 喝 1251-2500,3751-5000, 6751-7500, 8751-10000

: :

: : 每次分一半给两个犯人....

: : 通过十来个个犯人第一天结束就能 确定大概100桶酒有问题,

: : 然后第二天再让,10来个犯人就能试出来了。

: :

: :

: :

: :

: :

: :

: : 【 在 babypig (猪爸爸) 的大作中提到: 】

: : : 标  题: 万粥帮帮我解一下这道题

: : : 发信站: 水木社区 (Fri Mar  3 10:39:27 2017), 站内

: : :

: : : 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

: : :

: : : BTW:

: : : 1. 毒酒喝到就必死,一点点都不行

: : : 2. 大家看清题啊,2天内必须找出来,还有毒发周期,找不出来国王的酒会没法办了

: : : --

: : :

: :

: :

: : --

: :

: --

iEric
Eric 2017-03-03

恩,好复杂,一组同样的犯人,可以在不同的时间段喝不同的桶的酒,根据死期再推算

。。。

这个题好复杂

【 在 libro (简简单单) 的大作中提到: 】

: 标  题: Re: 万粥帮帮我解一下这道题

: 发信站: 水木社区 (Fri Mar  3 11:03:29 2017), 站内

: 不是按照day来算,按照小时算。

: 因为小时可以推测有问题的组。

: 【 在 iEric (Eric) 的大作中提到: 】

: : 标  题: Re: 万粥帮帮我解一下这道题

: : 发信站: 水木社区 (Fri Mar  3 11:02:43 2017), 站内

: :

: :

: : 大概思路

: : day1:

: : 囚犯1 喝 1-5000

: : 囚犯2 喝 5001-10000

: :

: : 囚犯3 喝 1-2500 5001-7500

: : 囚犯4 喝 2501-5000 , 7501-10000

: :

: : 囚犯5 喝 1-1250, 2501-3750, 5001-6750,  7501-8750

: : 囚犯6 喝 1251-2500,3751-5000, 6751-7500, 8751-10000

: :

: : 每次分一半给两个犯人....

: : 通过十来个个犯人第一天结束就能 确定大概100桶酒有问题,

: : 然后第二天再让,10来个犯人就能试出来了。

: :

: :

: :

: :

: :

: :

: : 【 在 babypig (猪爸爸) 的大作中提到: 】

: : : 标  题: 万粥帮帮我解一下这道题

: : : 发信站: 水木社区 (Fri Mar  3 10:39:27 2017), 站内

: : :

: : : 10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人;国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒,问最少需要多少囚犯才能保证找出毒酒?

: : :

: : : BTW:

: : : 1. 毒酒喝到就必死,一点点都不行

: : : 2. 大家看清题啊,2天内必须找出来,还有毒发周期,找不出来国王的酒会没法办了

: : : --

: : :

: :

: :

: : --

: :

: --

babypig
猪爸爸 2017-03-03

这个答案我最早就是这么做的,很明显不是最优解,继续

【 在 aphei (一切归于平静) 的大作中提到: 】

: 我来一个,101个人?

: 第一次,100人,每人喝100种酒。23小时后有一人必死,把他喝的100种酒,再补充一人,每人喝一种。