c*********t
发帖数: 1861 | 1 好了，周末了，委索男们又出来活动了！
假设有N个一模一样的WSN。另外有M（M＞１）层的高楼。现在想知道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＞１）层的高楼。现在想知道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 的大作中提到】
: 好了，周末了，委索男们又出来活动了！
: 假设有N个一模一样的WSN。另外有M（M＞１）层的高楼。现在想知道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＞１）层的高楼。现在想知道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＞１）层的高楼。现在想知道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
|
