L**********u
发帖数: 194 | 1 有10个罐子，每个罐子里有500颗candy。
有的罐子装的是假candy， 每颗重0.9g，
有的罐子装的是真candy， 每颗重1g。
有没有办法只称一次，找出所有的假的来。
（可能有多于1的罐子装的是假的）。
我知道，如果每罐有512颗candy， 一次就可以搞定。 | u****g
发帖数: 402 | 2 从第九个罐子里拿出12颗加到第十个罐里
对于第九个和第十个罐子，有下列四种情况：
9 10
fake fake
true true
fake true
true fake
前面两张情况很容易分辨，后面两种情况稍微分析一下就行 | C*O
发帖数: 389 | 3 一次可能不行吧.
若只有1个罐子是假的，就可以了 | L**********u
发帖数: 194 | 4 肯定不对。我曾经这样想过的。
按你的方法，如果第9罐是fake的case没有办法确定。
因为从第9罐中取出的个数可以表示成1-8罐中某些
罐的和。
【在 u****g 的大作中提到】
: 从第九个罐子里拿出12颗加到第十个罐里
: 对于第九个和第十个罐子，有下列四种情况：
: 9 10
: fake fake
: true true
: fake true
: true fake
: 前面两张情况很容易分辨，后面两种情况稍微分析一下就行
| L**********u
发帖数: 194 | 5 2次就trivial了。
1-9罐分别取 2^0，2^1,....., 2^8个， 一次可以找出fake的，
然后称第10罐，
所有用2次就trivial了。
【在 C*O 的大作中提到】
: 一次可能不行吧.
: 若只有1个罐子是假的，就可以了
| L**********u
发帖数: 194 | 6 我试过4罐每罐7个candy的case，
分别取 3，5，6，7就可以称一次分辨出来。
对于10罐每罐500颗的case没有办法。 | z****g
发帖数: 1978 | | L**********u
发帖数: 194 | 8 你被问了吗？
呵呵
【在 z****g 的大作中提到】
: 狗日的题目
| z****g
发帖数: 1978 | 9 平生最恨brainteaser
【在 L**********u 的大作中提到】
: 你被问了吗？
: 呵呵
| u****g
发帖数: 402 | 10 sorry，的确不行
9 10
取 256 500+12
fake fake //fake的数目在 768--768+255之间
true true //fake的数目在 0--255之间
fake true //相当于第九罐取了 268，fake的数目在 268--268+255之间
true fake //fake的数目在 500--500+255之间
第三和第四种情况有重合
【在 L**********u 的大作中提到】
: 肯定不对。我曾经这样想过的。
: 按你的方法，如果第9罐是fake的case没有办法确定。
: 因为从第9罐中取出的个数可以表示成1-8罐中某些
: 罐的和。
| | | m********l
发帖数: 4394 | 11 提示： 200颗就行了
【在 u****g 的大作中提到】
: sorry，的确不行
: 9 10
: 取 256 500+12
: fake fake //fake的数目在 768--768+255之间
: true true //fake的数目在 0--255之间
: fake true //相当于第九罐取了 268，fake的数目在 268--268+255之间
: true fake //fake的数目在 500--500+255之间
: 第三和第四种情况有重合
| L**********u
发帖数: 194 | 12 提示个毛呀，
直接给答案就好了。
【在 m********l 的大作中提到】
: 提示： 200颗就行了
| m********l
发帖数: 4394 | 13 呵呵， 不要
你们想想
【在 L**********u 的大作中提到】
: 提示个毛呀，
: 直接给答案就好了。
| A*****s
发帖数: 13748 | 14 你搜搜他以前的帖子就知道了，装B专业户
【在 L**********u 的大作中提到】
: 提示个毛呀，
: 直接给答案就好了。
| m********l
发帖数: 4394 | 15 我说出来， 你要叫我爷爷？
【在 A*****s 的大作中提到】
: 你搜搜他以前的帖子就知道了，装B专业户
| L**********u
发帖数: 194 | 16 面试官提示说500不是随便取的，是有讲究的。
但是我没有搞明白。 | A*****s
发帖数: 13748 | 17 大家都看出来了，你什么都不懂
别再来这儿逗人笑了
【在 m********l 的大作中提到】
: 我说出来， 你要叫我爷爷？
| m********l
发帖数: 4394 | 18 那你不妨把我们的帖子搜出来， 让大家看看你的傻B样
【在 A*****s 的大作中提到】
: 大家都看出来了，你什么都不懂
: 别再来这儿逗人笑了
| d*j
发帖数: 13780 | 19 和 512 有关呗 。。。
2^9
【在 L**********u 的大作中提到】
: 面试官提示说500不是随便取的，是有讲究的。
: 但是我没有搞明白。
| m********l
发帖数: 4394 | 20 500内绝对可能
在来看提示：
不要用 2 power
【在 d*j 的大作中提到】
: 和 512 有关呗 。。。
: 2^9
| | | m********l
发帖数: 4394 | 21 500纯误导你
【在 d*j 的大作中提到】
: 和 512 有关呗 。。。
: 2^9
| L**********u
发帖数: 194 | | m********l
发帖数: 4394 | 23 也可以。。。
500的
1, 3, 5, 7, 14, 28, 56, 112, 224, 448
其实100颗也可以
【在 L**********u 的大作中提到】
: 贴答案才是王道，
: 耍嘴皮子有毛用
| E*****T
发帖数: 1193 | 24 1 2 5 9 13 31 62 124 248 496 | E*****T
发帖数: 1193 | | S*********g
发帖数: 5298 | 26 这个显然不行，举个例子
3+5+7=15
1+14=15
【在 m********l 的大作中提到】
: 也可以。。。
: 500的
: 1, 3, 5, 7, 14, 28, 56, 112, 224, 448
: 其实100颗也可以
| S*********g
发帖数: 5298 | 27 5+9=1+13
【在 E*****T 的大作中提到】
: 1 2 5 9 13 31 62 124 248 496
| u****g
发帖数: 402 | 28 9+5 = 1+ 13
【在 E*****T 的大作中提到】
: 1 2 5 9 13 31 62 124 248 496
| m********l
发帖数: 4394 | 29 o.. 好样子
让我想想， 200还是应该可以的
【在 S*********g 的大作中提到】
: 这个显然不行，举个例子
: 3+5+7=15
: 1+14=15
| l******u
发帖数: 1174 | 30 别想了。2的power应该是optimal的。
【在 m********l 的大作中提到】
: o.. 好样子
: 让我想想， 200还是应该可以的
| | | m********l
发帖数: 4394 | 31 但是不行啊， 500颗
【在 l******u 的大作中提到】
: 别想了。2的power应该是optimal的。
| m********l
发帖数: 4394 | 32 妈的， 出法宝了
10, 20, 40, 80, 160
161, 172, 184, 198, 216
【在 m********l 的大作中提到】
: 但是不行啊， 500颗
| E*****T
发帖数: 1193 | 33 500 499 498 249 124 62 31 15 7 3 撒花喽 | m********l
发帖数: 4394 | 34 这太不厚道了
最小可以多少
【在 E*****T 的大作中提到】
: 500 499 498 249 124 62 31 15 7 3 撒花喽
| E*****T
发帖数: 1193 | 35 3 6 12 24 48 96 192 383 384 385 更优一些 | E*****T
发帖数: 1193 | 36 直到192都不可能给你1或2的差，后面三个数正好给了1或2的差，而且前面数全加也弥
补不了后面。
【在 E*****T 的大作中提到】
: 3 6 12 24 48 96 192 383 384 385 更优一些
| m********l
发帖数: 4394 | 37 100颗大概是可以的吧。
【在 E*****T 的大作中提到】
: 直到192都不可能给你1或2的差，后面三个数正好给了1或2的差，而且前面数全加也弥
: 补不了后面。
| s****p
发帖数: 187 | 38 1 2 5 11 23 43 87 173 337 499 | j****1
发帖数: 65 | 39 感觉这个可以倒过来，从500往下减。这样只要最后差不是特别大，假的罐子数目不同
时总和就不能重合（比如八个假的和九个假的的情况）。
第一个是500-0，第二个是500-1 。。。
后面只用考虑后N个减前N个差最大的情况，N = 1, 2。。。
结果是: 0, -1, -2, -4, -7, -13, -24, -46, -88, -172
加上500就是: 500, 499, 498, 496, 493, 487, 476, 454, 412, 328。 | u****g
发帖数: 402 | 40 牛，检查了下，只有EveryLT的两组work
用到2的power，只是不从1开始，make sense。
【在 E*****T 的大作中提到】
: 3 6 12 24 48 96 192 383 384 385 更优一些
| | | u****g
发帖数: 402 | 41 这个也work。
很好的想法。
【在 j****1 的大作中提到】
: 感觉这个可以倒过来，从500往下减。这样只要最后差不是特别大，假的罐子数目不同
: 时总和就不能重合（比如八个假的和九个假的的情况）。
: 第一个是500-0，第二个是500-1 。。。
: 后面只用考虑后N个减前N个差最大的情况，N = 1, 2。。。
: 结果是: 0, -1, -2, -4, -7, -13, -24, -46, -88, -172
: 加上500就是: 500, 499, 498, 496, 493, 487, 476, 454, 412, 328。
| o**o
发帖数: 3964 | 42 三进制？
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 L**********u 的大作中提到】
: 有10个罐子，每个罐子里有500颗candy。
: 有的罐子装的是假candy， 每颗重0.9g，
: 有的罐子装的是真candy， 每颗重1g。
: 有没有办法只称一次，找出所有的假的来。
: （可能有多于1的罐子装的是假的）。
: 我知道，如果每罐有512颗candy， 一次就可以搞定。
| u****g
发帖数: 402 | 43 11 23 43 87 173 vs 337
【在 s****p 的大作中提到】
: 1 2 5 11 23 43 87 173 337 499
| u****g
发帖数: 402 | 44 20 172 184 vs 160 216
【在 m********l 的大作中提到】
: 妈的， 出法宝了
: 10, 20, 40, 80, 160
: 161, 172, 184, 198, 216
| l******u
发帖数: 1174 | 45 看成你当妈生出宝宝了。
【在 m********l 的大作中提到】
: 妈的， 出法宝了
: 10, 20, 40, 80, 160
: 161, 172, 184, 198, 216
| y********l
发帖数: 11 | 46 我想的是500-0， 500-2^i (i = 1,2,...8)。不过你这个方法可以分辨的情况更多。再
仔细想想，因为是用500减去某个数，所以只要同样数目的罐子是假的时候，减去的数的
和之间是可分辨的就可以了。
举个例子，如果我们从0开始减，那么减数就可以是：
0，1，2，4 (因为3+0=1+2, 4+0>1+2), 7(6+0=2+4,7+0>2+4), 12, 20...
如果从1开始减，就是：
1, 2, 3(>1, >2), 5, 8, 13, 21, ...
如果从2开始减，就是：
2, 3, 5, 8, 13, ...
如果一共有M个罐子，用这个方法的条件是M个减数中任意i个减数的和不能等于j个减数的和加上(j-
i)*M。比如说有4个罐，每罐7个candy，那必须从0开始减，得到(3,5,6,7)。如果从1开始减，4
个减数为 1, 2, 3, 5。这时有两个减数的和 3 + 5 = 8 = 1 + 7*1 ==> 不行。
【在 j****1 的大作中提到】
: 感觉这个可以倒过来，从500往下减。这样只要最后差不是特别大，假的罐子数目不同
: 时总和就不能重合（比如八个假的和九个假的的情况）。
: 第一个是500-0，第二个是500-1 。。。
: 后面只用考虑后N个减前N个差最大的情况，N = 1, 2。。。
: 结果是: 0, -1, -2, -4, -7, -13, -24, -46, -88, -172
: 加上500就是: 500, 499, 498, 496, 493, 487, 476, 454, 412, 328。
| p*****k
发帖数: 318 | 47 since there are total of 2^N-1 sums for an N-element set, so 2^(i-1)
optimizes the total sum.
OP's problem (or rather the discussion so far) is related to Erdos's
conjecture:
find a set with such property (i.e., distinctive subset sums) with the
smallest largest element.
(his conjecture is the asymptotic form with N->infty)
the solution was the so-called Conway-Guy sequence, which gives the upper
bound, and they verified up to N=8 that their solution is optimal.
(but the asymptotic form had been improved by subsequent works, the current
record is by Bohman)
Conway-Guy sequence for N=10 gives 309 to be the largest element | m********l
发帖数: 4394 | 48 啥意思？
这个答案
不是可以在200 之内？
200 199 198 196 193, 187, 176, 154, 112, 28
current
【在 j****1 的大作中提到】
: 感觉这个可以倒过来，从500往下减。这样只要最后差不是特别大，假的罐子数目不同
: 时总和就不能重合（比如八个假的和九个假的的情况）。
: 第一个是500-0，第二个是500-1 。。。
: 后面只用考虑后N个减前N个差最大的情况，N = 1, 2。。。
: 结果是: 0, -1, -2, -4, -7, -13, -24, -46, -88, -172
: 加上500就是: 500, 499, 498, 496, 493, 487, 476, 454, 412, 328。
| j****1
发帖数: 65 | 49 只要差的和小于500，那8个假的的总和肯定在3501-4000之间，7个假的在3001-3500之
间，9个在4001-4500之间 。。。 不会有重复。接下来只用考虑在假的罐子数目相同的
时候怎么不重复。
从一个罐子开始，每次都找差最大的情况，就是后N个数和前N-1个数要碰到一起的时候
。然后在多减一个1就行了。
7 = 2 + 4 - 0 + 1
13 = 7 + 4 + 2 - 1 - 0 + 1
24 = 13 + 7 + 4 - 1 - 0 + 1
。。。
【在 m********l 的大作中提到】
: 啥意思？
: 这个答案
:
: 不是可以在200 之内？
: 200 199 198 196 193, 187, 176, 154, 112, 28
: current
| p*****k
发帖数: 318 | 50 mercuriusl, 198+193=187+176+28
this might sound harsh, but there are only 1023 subset sums in total.
please run a quick check before you spit out random sequences.
details on Conway-Guy sequence:
http://oeis.org/A005318 | | | m********l
发帖数: 4394 | 51 not at all.
500, 499, 498, 496, 493, 487, 476, 454, 412, 328
498+493
ok. that's still good.
btw, how do you check? hopefully not by hand...
and the theory says 309 is the min?
【在 p*****k 的大作中提到】
: mercuriusl, 198+193=187+176+28
: this might sound harsh, but there are only 1023 subset sums in total.
: please run a quick check before you spit out random sequences.
: details on Conway-Guy sequence:
: http://oeis.org/A005318
| C*O
发帖数: 389 | 52 很好的想法
数的
数的和加上(j-
【在 y********l 的大作中提到】
: 我想的是500-0， 500-2^i (i = 1,2,...8)。不过你这个方法可以分辨的情况更多。再
: 仔细想想，因为是用500减去某个数，所以只要同样数目的罐子是假的时候，减去的数的
: 和之间是可分辨的就可以了。
: 举个例子，如果我们从0开始减，那么减数就可以是：
: 0，1，2，4 (因为3+0=1+2, 4+0>1+2), 7(6+0=2+4,7+0>2+4), 12, 20...
: 如果从1开始减，就是：
: 1, 2, 3(>1, >2), 5, 8, 13, 21, ...
: 如果从2开始减，就是：
: 2, 3, 5, 8, 13, ...
: 如果一共有M个罐子，用这个方法的条件是M个减数中任意i个减数的和不能等于j个减数的和加上(j-
| L********a
发帖数: 44 | 53 Take 1 candy from the 1st can, 2 candies from 2nd can, 3 candies from 3rd
can... 10 candies from 10th can.
If all candies are real (I.e. 1g per candy) we will have 55g
If the weight is 54.9 then no1 is the fake one ( I.e one fake )
If 55-nx0.1 then No. n is the fake one | L**********u
发帖数: 194 | 54 这个显然是错的，
这么简单我就不拿来讨论了。
【在 L********a 的大作中提到】
: Take 1 candy from the 1st can, 2 candies from 2nd can, 3 candies from 3rd
: can... 10 candies from 10th can.
: If all candies are real (I.e. 1g per candy) we will have 55g
: If the weight is 54.9 then no1 is the fake one ( I.e one fake )
: If 55-nx0.1 then No. n is the fake one
| m********l
发帖数: 4394 | 55 still at it?
【在 L**********u 的大作中提到】
: 这个显然是错的，
: 这么简单我就不拿来讨论了。
| m********l
发帖数: 4394 | 56 run a quick check for me:
8， 9， 10， 20， 40， 80， 168， 175， 182， 193
how come i am seeing more than 1023 subsets of sums??
【在 p*****k 的大作中提到】
: mercuriusl, 198+193=187+176+28
: this might sound harsh, but there are only 1023 subset sums in total.
: please run a quick check before you spit out random sequences.
: details on Conway-Guy sequence:
: http://oeis.org/A005318
| m********l
发帖数: 4394 | 57 and this one:
10, 11, 20, 22, 40, 44, 80, 88, 96, 103
【在 m********l 的大作中提到】
: not at all.
: 500, 499, 498, 496, 493, 487, 476, 454, 412, 328
: 498+493
: ok. that's still good.
: btw, how do you check? hopefully not by hand...
: and the theory says 309 is the min?
| H*****1
发帖数: 4815 | 58 100纯属扯淡
你要鉴别2^10 = 1024种可能
而10罐100颗都放在一起，一共1000个，怎么表达1024种可能！
【在 m********l 的大作中提到】
: 也可以。。。
: 500的
: 1, 3, 5, 7, 14, 28, 56, 112, 224, 448
: 其实100颗也可以
| o**o
发帖数: 3964 | 59 想了想，还是套2进制的老路。 2^0, 2^1, ...2^8，
然后从第二罐拿4个，第三罐拿8个放到最后一罐凑2^9。
低位递归判别一下就可以了：如果第二罐假那么第三罐flip，如果第三罐假第四罐flip
，直到不进位。 |
|
