由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
_DC版 - 惨绝人寰!WSN为解Google难题舍身取义去跳楼
相关主题
凄美的恋爱问题(转帖)[报到] E300
当当当,上菜了周日有人去salsa么?
新烤的spinach pie提醒:今天是wsn的盛大节日
劳动节 -- WSN 绣花 (已解决)WSN 的好消息:美国华人女多于男 by 21万
参赛★☆【WSN组歌】☆★第6章合唱《WSN啊WSN》 (转载)请转 马里兰版 -- 超级WSN (转载)
sigh, bbs上WSN忒多了最近WSN们都很NB啊
Wsn 们应该都搬去纽约。。。数学:如果香港游客都是由毛泽东思想武装起来的人伤亡不会那么多
今天在DC酒吧看球时为中国WSN争光了 (转载)家版那个傻铞T什么逼把老子给办了
相关话题的讨论汇总
话题: wsn话题: 楼层话题: google话题: sqrt话题: 假设
1 (共1页)
c*********t
发帖数: 1861
1
好了,周末了,委索男们又出来活动了!
假设有N个一模一样的WSN。另外有M(M>1)层的高楼。现在想知道WSN最少要从第几
层楼跳下去才会死。假设这个楼层是K (K<=M)
当然,最简单的办法是派一个WSN从一楼开始,一层一层地跳,啥楼层死了,K就是那里
。但是,WSN不乐意。每个WSN声称只愿意跳一次(不管死活)。而且如果有两个WSN跳
死了,其他WSN都不跳了。。。
现在的问题是,楼层M最多多高能保证WSN一定能找到死亡楼层K?
原题出自Google Jam 练习题,有简化。
http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIP6AQw#s=p2
i*********n
发帖数: 219
2
sounds like there should be some constrains on N,
otherwise, if N => M, then K can always be found no matter how big M is.
c*********t
发帖数: 1861
3
For a give N, you want to find max M so that K is solvable. Obviously,
max M > N.

【在 i*********n 的大作中提到】
: sounds like there should be some constrains on N,
: otherwise, if N => M, then K can always be found no matter how big M is.

p**********e
发帖数: 101
4
跳的时候脑袋向下,一楼就归西天

【在 c*********t 的大作中提到】
: 好了,周末了,委索男们又出来活动了!
: 假设有N个一模一样的WSN。另外有M(M>1)层的高楼。现在想知道WSN最少要从第几
: 层楼跳下去才会死。假设这个楼层是K (K<=M)
: 当然,最简单的办法是派一个WSN从一楼开始,一层一层地跳,啥楼层死了,K就是那里
: 。但是,WSN不乐意。每个WSN声称只愿意跳一次(不管死活)。而且如果有两个WSN跳
: 死了,其他WSN都不跳了。。。
: 现在的问题是,楼层M最多多高能保证WSN一定能找到死亡楼层K?
: 原题出自Google Jam 练习题,有简化。
: http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIP6AQw#s=p2

s*******u
发帖数: 5796
5
恩,周末了,赶紧做题来发泄多余的精力吧!
g******3
发帖数: 133
6
我算了一下, 好象 M 最多可以到: INT( ((N + 1) / 2) ^ 2 )
举例: 当 M = 100 时, 至少需要 19 个WSN 来测量 K.
死第一个WSN之前: 每次跳的层数是: SQRT(M) 是最快的测量办法.
死第一个WSN之后(假设是100层): 从91层开始, 每次加一层测量, 需要最多 SQRT(M)-1
个WSN.
所以: N = 2 * SQRT(M) - 1.
M = ((N+1) / 2) ^ 2
不知道还有更大的M否?

【在 c*********t 的大作中提到】
: 好了,周末了,委索男们又出来活动了!
: 假设有N个一模一样的WSN。另外有M(M>1)层的高楼。现在想知道WSN最少要从第几
: 层楼跳下去才会死。假设这个楼层是K (K<=M)
: 当然,最简单的办法是派一个WSN从一楼开始,一层一层地跳,啥楼层死了,K就是那里
: 。但是,WSN不乐意。每个WSN声称只愿意跳一次(不管死活)。而且如果有两个WSN跳
: 死了,其他WSN都不跳了。。。
: 现在的问题是,楼层M最多多高能保证WSN一定能找到死亡楼层K?
: 原题出自Google Jam 练习题,有简化。
: http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIP6AQw#s=p2

c*********t
发帖数: 1861
7
想法不错,答案的数量级也是对的,不过系数错了。
【友情提示】
M可以更大。。。因为,如果K=1,按你的方法跳两次(头两次WSN都死)就能判别出来,
那剩下的17个WSN就浪费了。所以最优解法一定是不论K是多少,都让最后一个WSN跳死
,最大限度利用N个WSN。。。
-1
c*********t
发帖数: 1861
8
看来大家对WSN不感兴趣了。。。我把答案说一下好了:
假设 N个WSN中可以死 L(题目中L=2)个,能够探测的最高楼层数是 M, M显然与N和L有
关。记 M=M(N,L). 那么:
1。M(N,1) = N (为什么?)
2。M(N,N) = 2^N - 1 (为什么?)
3。一般地,
M(N,L) = M(N-1, L-1) + M(N-1, L) + 1
知道杨辉三角的同学一定非常熟悉上面的递推关系。特别地,取 L=2, 可得:
M(N,2) = N + (N-1) + (N-2) + ... + M(2,2) = N(N+1)/2

【在 c*********t 的大作中提到】
: 好了,周末了,委索男们又出来活动了!
: 假设有N个一模一样的WSN。另外有M(M>1)层的高楼。现在想知道WSN最少要从第几
: 层楼跳下去才会死。假设这个楼层是K (K<=M)
: 当然,最简单的办法是派一个WSN从一楼开始,一层一层地跳,啥楼层死了,K就是那里
: 。但是,WSN不乐意。每个WSN声称只愿意跳一次(不管死活)。而且如果有两个WSN跳
: 死了,其他WSN都不跳了。。。
: 现在的问题是,楼层M最多多高能保证WSN一定能找到死亡楼层K?
: 原题出自Google Jam 练习题,有简化。
: http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIP6AQw#s=p2

A***n
发帖数: 2705
9
以前做过了。

【在 c*********t 的大作中提到】
: 好了,周末了,委索男们又出来活动了!
: 假设有N个一模一样的WSN。另外有M(M>1)层的高楼。现在想知道WSN最少要从第几
: 层楼跳下去才会死。假设这个楼层是K (K<=M)
: 当然,最简单的办法是派一个WSN从一楼开始,一层一层地跳,啥楼层死了,K就是那里
: 。但是,WSN不乐意。每个WSN声称只愿意跳一次(不管死活)。而且如果有两个WSN跳
: 死了,其他WSN都不跳了。。。
: 现在的问题是,楼层M最多多高能保证WSN一定能找到死亡楼层K?
: 原题出自Google Jam 练习题,有简化。
: http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIP6AQw#s=p2

1 (共1页)
相关主题
家版那个傻铞T什么逼把老子给办了参赛★☆【WSN组歌】☆★第6章合唱《WSN啊WSN》 (转载)
恭喜侦探版的历史时刻sigh, bbs上WSN忒多了
Re: 汪精卫当时为什么要投靠日本人 (转载)Wsn 们应该都搬去纽约。。。
章子怡裸戏大尺度露点 顾长卫说是“舍身取义”今天在DC酒吧看球时为中国WSN争光了 (转载)
凄美的恋爱问题(转帖)[报到] E300
当当当,上菜了周日有人去salsa么?
新烤的spinach pie提醒:今天是wsn的盛大节日
劳动节 -- WSN 绣花 (已解决)WSN 的好消息:美国华人女多于男 by 21万
相关话题的讨论汇总
话题: wsn话题: 楼层话题: google话题: sqrt话题: 假设