青蛙过河 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#1

发表于 2005-1-4 06:48 资料主页个人空间短消息只看该作者

NOI2000的第二天第二题。

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

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

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

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

[广告] 真诚支持说岳，携手共创辉煌


	loranrowe

组别	士兵
级别	奋威校尉
好贴	1
功绩	6
帖子	143
编号	17767
注册	2004-9-16

#2

发表于 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)

[广告] 真诚支持说岳，携手共创辉煌


	青木风亮 (枯木)


	定远侯谏议大夫

组别	翰林学士
级别	平西将军
好贴	3
功绩	521
帖子	2357
编号	12000
注册	2004-7-18
家族	泡泡营

#3

发表于 2005-1-10 19:32 资料主页文集短消息只看该作者

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

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

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

[广告] 真诚支持说岳，携手共创辉煌


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#4

发表于 2005-1-11 02:34 资料主页个人空间短消息只看该作者

QUOTE:

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

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

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

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

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

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

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

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

[广告] 真诚支持说岳，携手共创辉煌


	发呆

组别	百姓
级别	破贼校尉
功绩	1
帖子	100
编号	30190
注册	2005-1-13

#5

发表于 2005-1-13 17:49 资料主页短消息只看该作者

我推算的答案是：

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

不知是否正确？

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

[广告] 真诚支持说岳，携手共创辉煌


	天宫公主 (司徒家的颖颖)


	虞国公主 ★

组别	限制发言用户
级别	大将军
好贴	6
功绩	517
帖子	11552
编号	1037
注册	2004-10-25
来自	天津
家族	司徒实业

#6

发表于 2005-1-13 17:59 资料主页短消息只看该作者

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

[广告] 《精忠报国岳飞传完整版》火热发布


	发呆

组别	百姓
级别	破贼校尉
功绩	1
帖子	100
编号	30190
注册	2005-1-13

#7

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

[广告] 真诚支持说岳，携手共创辉煌


	天痕


	白衣伯爵中大夫

组别	白衣卿相
级别	右将军
好贴	4
功绩	224
帖子	1182
编号	208
注册	2003-8-29

#8

发表于 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；

不知是否正确？

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

思路如下，请指正：

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

还是不对

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

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！