轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 青蛙过河 [打印本页]

作者: 天痕 时间: 2005-1-4 06:48

NOI2000的第二天第二题。

当年天痕代表江苏省出战，结果惨败澳门，本题仅对两个测试点，得2/10*40=8分

虽然是计算机奥林匹克，但这却是一道难得的数学题。

题目见附件，请大家不要用GOOGLE搜索答案。

所有答对者给200通宝，大家加油~~

作者: loranrowe 时间: 2005-1-4 16:12

把这个题抽象以下：
存在两个栈A和D，A中数据希望转移到D中去
存在n个中转栈和m个临时变量
出栈无限制，只有当栈为空或待入栈元素为栈顶元素的prior时允许入栈
A只出，D只入
A中最多可以有多少元素。
设A中最多存在k个元素，不难证明

当n=0时，只有m个临时单元，k=m+1
当n=1时，临时栈中最多存放m+1个元素，k=2m+2
当n=2时，k=4m+4
当n=3时，k=8m+8
猜测：k=2^n(m+1)
n=0时，k_0=2^0(m+1)成立
假设n=p时,k_p=2^p(m+1)成立
n=p+1时
k_(p+1)=k_p+(k_(p-1))+...+k_1+k_0+m+1
=2^p(m+1)+2^(p-1)(m+1)+...+2^1(m+1)+2^0(m+1)+(m+1)
=2^(p+1)(m+1)

因此，对于m,n属于任意自然数，k(n,m)=2^n(m+1)

作者: 青木风亮 时间: 2005-1-10 19:32

这道题我已经出过了给了A级周瑜拿了1000

在这里天痕兄以后出题可以改成“牛蛙渡江”之类的防google

ps:作者是我的中学校友王小川 IOI96世界第二名按他说这道题还是出简单了
天痕能给我解释一下第三题算符破译吗当年就没搞懂现在全忘了

作者: 天痕 时间: 2005-1-11 02:34

QUOTE:

原帖由青木风亮于2005-01-10, 19:32:48发表
这道题我已经出过了给了A级周瑜拿了1000

在这里天痕兄以后出题可以改成“牛蛙渡江”之类的防google

ps:作者是我的中学校友王小川 IOI96世界第二名按他说这道题还是出简单了
天痕能给我解释一下第三题算符破译吗当年就没搞懂现在全忘了

青木风亮这么一说就暴露的原来是成都七中学生的本质

当年和王小川一起夺金的李申杰（南京金陵中学）则是和我一样在江苏队训练

青木风亮中学时也玩过这个？

至于NOI2000，别提了，天痕输得那个惨啊。
现在看来，青蛙过河不算难，可在当时的环境中天痕糊涂了

算符破译似乎纯粹的搜索就可以，最近课程都进入尾升了，时间不会太多，一星期内我会给出答复，表急~~

作者: 发呆 时间: 2005-1-13 17:49

我推算的答案是：

（n+1）（n+2）/2 + m；

不知是否正确？

--------------
发呆
--------------

作者: 天宫公主 时间: 2005-1-13 17:59

呵呵，这里又来一群钻营IOI的牛人！

作者: 发呆 时间: 2005-1-15 11:05

QUOTE:

原帖由raydeng2003于2005-01-13, 17:49:38发表
我推算的答案是：

（n+1）（n+2）/2 + m；

不知是否正确？

--------------
发呆
--------------

思路如下，请指正：

1、先设m=0，即有n个石墩，0片荷叶：
思考可知：若要使总青蛙数目最大，且符合题目的规则，则：n+2 个落点上，分别落着0、1、……、n+1只青蛙，共计（n+1）（n+2）/2只。
2、再推至m>0的情况：
m每增加1，总青蛙数可增加1。

故，窃以为，最终结果当是：（n+1）（n+2）/2 + m 。

（步骤1似乎还可以用那种那种方法，名字已经还给老师了，就是在1的基础上进行自然数递推，先算出n为1时的青蛙数，再算出n每增加1时青蛙的增量，最后推出结果）

作者: 天痕 时间: 2005-1-15 17:01

QUOTE:

原帖由raydeng2003于2005-01-15, 11:05:38发表

QUOTE:

原帖由raydeng2003于2005-01-13, 17:49:38发表
我推算的答案是：

（n+1）（n+2）/2    +  m；

不知是否正确？

--------------
发呆
--------------

还是不对

loranrowe做对了，可以买他的答案看一看，当然也欢迎继续想~~

欢迎光临轩辕春秋文化论坛 (http://xycq.org.cn/forum/)