|
|
发表于 20-8-2009 10:10 AM
|
显示全部楼层
原帖由 mathlim 于 20-8-2009 06:07 AM 发表 
① 12楼(不)→18楼(不)→22楼(不)→24楼(不)→25楼
② 12楼(不)→14楼(不)→18楼(不)→24楼(碎)→23楼
③ 12楼(不)→14楼(不)→22楼(碎)→20楼(不)→21楼
④ 12楼(不)→12楼(不)→16楼(碎)→20楼(碎)→19楼
⑤ 1 ...
⑿ 12楼(碎)→ 4楼(不)→ 8楼(碎)→ 6楼(碎)→ 5楼
第一次不可从 12 楼丢，这个方法有瑕疵。
12楼(碎)→ 4楼(不)→ 8楼(碎)→ 6楼(碎)→ 5楼
只能碎三个，万一 5 楼又碎那就不行了，所以这个行不通。
[ 本帖最后由 flash 于 20-8-2009 10:15 AM 编辑 ] |
|
|
|
|
|
|
|
|
|
|
|
发表于 20-8-2009 10:32 AM
|
显示全部楼层
回复 61# flash 的帖子
你怎样得到 ２５？ |
|
|
|
|
|
|
|
|
|
|
|
发表于 20-8-2009 11:19 AM
|
显示全部楼层
|
|
|
|
|
|
|
|
|
|
|
发表于 20-8-2009 11:21 AM
|
显示全部楼层
|
|
|
|
|
|
|
|
|
|
|
发表于 20-8-2009 11:55 AM
|
显示全部楼层
|
|
|
|
|
|
|
|
|
|
|
发表于 20-8-2009 12:35 PM
|
显示全部楼层
|
11>18>22.... 25 |
|
|
|
|
|
|
|
|
|
|
|
发表于 20-8-2009 12:50 PM
|
显示全部楼层
yw46跟我的一样。这一次不会错了！
① 11楼(不)→18楼(不)→22楼(不)→24楼(不)→25楼
② 11楼(不)→18楼(不)→22楼(不)→24楼(碎)→23楼
③ 11楼(不)→18楼(不)→22楼(碎)→20楼(不)→21楼
④ 11楼(不)→18楼(不)→22楼(碎)→20楼(碎)→19楼
⑤ 11楼(不)→18楼(碎)→14楼(不)→16楼(不)→17楼
⑥ 11楼(不)→18楼(碎)→14楼(不)→16楼(碎)→15楼
⑦ 11楼(不)→18楼(碎)→14楼(碎)→12楼(不)→13楼
⑧ 11楼(不)→18楼(碎)→14楼(碎)→12楼(碎)
⑨ 11楼(碎)→ 4楼(不)→ 7楼(不)→ 9楼(不)→10楼
⑩ 11楼(碎)→ 4楼(不)→ 7楼(不)→ 9楼(碎)→ 8楼
⑾ 11楼(碎)→ 4楼(不)→ 7楼(碎)→ 5楼(不)→ 6楼
⑿ 11楼(碎)→ 4楼(不)→ 7楼(碎)→ 5楼(碎)
⒀ 11楼(碎)→ 4楼(碎)→ 1楼(不)→ 2楼(不)→ 3楼
⒁ 11楼(碎)→ 4楼(碎)→ 1楼(不)→ 2楼(碎)
⒂ 11楼(碎)→ 4楼(碎)→ 1楼(碎)
① 如果25楼不，则25楼或以下都不，25楼以上未知。
如果25楼碎，则24楼或以下都不，24楼以上碎。
② 如果23楼不，则23楼或以下都不，23楼以上碎。
如果23楼碎，则22楼或以下都不，22楼以上碎。
③ 如果21楼不，则21楼或以下都不，21楼以上碎。
如果21楼碎，则20楼或以下都不，20楼以上碎。
④ 如果19楼不，则19楼或以下都不，19楼以上碎。
如果19楼碎，则18楼或以下都不，18楼以上碎。
⑤ 如果17楼不，则17楼或以下都不，17楼以上碎。
如果17楼碎，则16楼或以下都不，16楼以上碎。
⑥ 如果15楼不，则15楼或以下都不，15楼以上碎。
如果15楼碎，则14楼或以下都不，14楼以上碎。
⑦ 如果13楼不，则13楼或以下都不，13楼以上碎。
如果13楼碎，则12楼或以下都不，12楼以上碎。
⑧ 如果12楼碎，则11楼或以下都不，11楼以上碎。
⑨ 如果10楼不，则10楼或以下都不，10楼以上碎。
如果10楼碎，则 9楼或以下都不， 9楼以上碎。
⑩ 如果 8楼不，则 8楼或以下都不， 8楼以上碎。
如果 8楼碎，则 7楼或以下都不， 7楼以上碎。
⑾ 如果 6楼不，则 6楼或以下都不， 6楼以上碎。
如果 6楼碎，则 5楼或以下都不， 5楼以上碎。
⑿ 如果 5楼碎，则 4楼或以下都不， 4楼以上碎。
⒀ 如果 3楼不，则 3楼或以下都不， 3楼以上碎。
如果 3楼碎，则 2楼或以下都不， 2楼以上碎。
⒁ 如果 2楼碎，则 1楼不，1楼以上碎。
⒂ 如果 1楼碎，则都碎。 |
|
|
|
|
|
|
|
|
|
|
|
发表于 20-8-2009 01:17 PM
|
显示全部楼层
回复 67# mathlim 的帖子
我的想法也是这样。 |
|
|
|
|
|
|
|
|
|
|
|
发表于 22-8-2009 05:29 AM
|
显示全部楼层
|
|
|
|
|
|
|
|
|
|
|
发表于 22-8-2009 07:49 AM
|
显示全部楼层
解答细心就不会错这么多次！ |
|
|
|
|
|
|
|
|
|
|
|
发表于 22-8-2009 11:15 AM
|
显示全部楼层
|
|
|
|
|
|
|
|
|
|
|
发表于 22-8-2009 09:44 PM
|
显示全部楼层
|
|
|
|
|
|
|
|
|
|
|
发表于 23-8-2009 07:04 AM
|
显示全部楼层
我也研究出一点头绪了！
慢点再整理出来。 |
|
|
|
|
|
|
|
|
|
|
|
发表于 25-8-2009 01:25 AM
|
显示全部楼层
回复 67# mathlim 的帖子
我看不明白。。。
为什么你懂在25楼？？ |
|
|
|
|
|
|
|
|
|
|
|
楼主 |
发表于 25-8-2009 09:47 AM
|
显示全部楼层
25号了。。。好啦公布一下
是的，答案是25.
题目是出自于这里 ：
http://code.google.com/codejam/c ... nRlc3RzGIP6AQw#s=p2
我想的解决方法是这样：
首先呢，
假设现在有 m 颗可以破的鸡蛋，n颗不可以破的鸡蛋，
m ，n
例如：５颗可以破三颗，就写成 ３，２
每次丢了一颗就会两种下场。。。
下场1 ：鸡蛋破 ，剩下的颗数是 ｍ－１，ｎ
下场2：鸡蛋没破，剩下的颗数是 ｍ，ｎ－１
假设你在 ｋ楼 丢了一颗做测试，
下场１同时也得到ｋ楼还有以上的楼的结论，只剩下ｋ楼以下的楼还未知
下场２同时也得到ｋ楼还有以下的楼的结论，只剩下ｋ楼以上的楼还未知
那么ｋ楼以上可以有多少楼，ｋ楼以下又可以有多少楼呢？
其实就是 所剩下的鸡蛋 可以解决的楼数。。。
下场一， 你要 ｍａｋｅｓｕｒｅ剩下的楼数 可以被 ｍ－１，ｎ 颗鸡蛋 解决
下场二， 你要 ｍａｋｅｓｕｒｅ剩下的楼数 可以被 ｍ，ｎ－１ 颗鸡蛋 解决
所以 ，如果你有 m ，n 颗，你可以测出
Ｆ（ｍ，ｎ） = F(m - 1,n) + F(m,n-1 )＋ １
然后你可以ｃｏｎｓｔｒｕｃｔ 那个ｔａｂｌｅ 我在另一贴子有问过。。
小的ｃａｓｅ 例如 ５颗爆三颗（３，２）可以容易找到
可是，大的就必须把ｒｅｃｕｒｓｉｖｅ 的ｆｏｒｍｕｌａ 做成没有ｒｅｃｕｒｓｉｖｅ 的ｆｏｒｍｕｌａ。。。
不然没办法找出来。。
http://code.google.com/codejam/c ... nRlc3RzGIP6AQw#s=p2
我已经解决了 part A （small dataset），
part B （ｌａｒｇｅ ｄａｔａｓｅｔ） 还没。
因为ｐａｒｔ B ，ｃａｓｅ ４ ，
你有 1312683601 楼要测，给你37906895 颗鸡蛋，你至少要允许可以爆几颗？ |
|
|
|
|
|
|
|
|
|
|
|
发表于 25-8-2009 06:18 PM
|
显示全部楼层
|
|
|
|
|
|
|
|
|
|
|
楼主 |
发表于 26-8-2009 12:14 AM
|
显示全部楼层
谢谢。。。现在才看到。。。。
 |
|
|
|
|
|
|
|
|
|
|
|
发表于 9-4-2011 02:27 AM
|
显示全部楼层
很有趣的题目， 我的解法不懂对不对
假设 破 = 1
不破 = 0
1 和 0 的 combination 各代表一层楼....
比如 00000代表最高层不破
01010 又代表其中一层....
不过最高一层是 不破是00000， 破就00001， 共用了两个combination
其他楼层却只用一个combination
如果是5 粒准许 3 粒：
就是 拿所有的combination减1（最高一楼用掉2 个combination的关系）
so， 答案：
floor = 5C3 + 5C2 + 5C1 + 5C0 - 1
= 5C3 + 5C2 + 5C1
= 25
所以，m 粒蛋，准许破 n 粒
n
就是，f = ∑ mCk
k=1
不懂有没有错啦，吓猜的 |
|
|
|
|
|
|
|
|
|
| |
 本周最热论坛帖子
|
2995 
99
