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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好了,周末了,委索男们又出来活动了! : 假设有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 | |
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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好了,周末了,委索男们又出来活动了! : 假设有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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好了,周末了,委索男们又出来活动了! : 假设有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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好了,周末了,委索男们又出来活动了! : 假设有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
|