NOI2000的第二天第二题。

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

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

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

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

把这个题抽象以下：
存在两个栈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)

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

在[url=http://www.xycq.net/forum/index.php?showtopic=31494][color=red]这里[/color][/url] 天痕兄以后出题可以改成“牛蛙渡江”之类的 防google  

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

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

在[url=http://www.xycq.net/forum/index.php?showtopic=31494][color=red]这里[/color][/url] 天痕兄以后出题可以改成“牛蛙渡江”之类的 防google  

ps:作者是我的中学校友王小川 IOI96世界第二名   按他说这道题还是出简单了
天痕能给我解释一下第三题算符破译吗 当年就没搞懂 现在全忘了  [/quote]
青木风亮这么一说就暴露的原来是成都七中学生的本质  

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

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

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

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

我推算的答案是：

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

不知是否正确？




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

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

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

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

不知是否正确？




--------------
发呆
-------------- [/quote]
思路如下，请指正：

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时青蛙的增量，最后推出结果）

[quote]原帖由[i]raydeng2003[/i]于2005-01-15, 11:05:38发表
[quote]原帖由[i]raydeng2003[/i]于2005-01-13, 17:49:38发表
我推算的答案是：

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

不知是否正确？




--------------
发呆
-------------- [/quote]
思路如下，请指正：

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时青蛙的增量，最后推出结果） [/quote]
还是不对  

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