搜索
2014年安徽省青少年信息学奥林匹克竞赛小学组试题AOI2014比赛时间：2014年4月18日08:00至11:00题目名称木板面积最大长度奶牛家谱树源文件名area.pas/c/cppmaxlen.pas/c/cppcowtree.pas/c/cpp输入文件名area.inmaxlen.incowtree.in输出文件名area.outmaxlen.outcowtree.out试题类型传统型传统型传统型满分100100100是否有部分分否否否时限1秒1秒1秒内存限制128M128M128M注意事项1.务必看清题目，严格按照所要求的格式输入、输出。2.在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据行调试。测试有严格的时间限制，请尽可能优化算法。3.命名规则：每题都规定了该题的英文名称。程序文件和数据文件的主文件名都是该题的英文名字。和.out。4.要求提交源程序的文件名一律采用小写。不同程序设计语言的源文件其扩展名请使用默认的扩展名。例如，PASCAL语言编写的源程序文件的扩展名应该为.pas；C语言编写的源程序文件的扩展名应该为.c；C++语言编写的源程序文件的扩展名应该为.cpp。注意：扩展名也应为小写。5.选手在桌面上建立以选手的参赛号为名的目录，并由选手为每道试题再单独建立一个子目录，子目录名与对应的试题英文名相同（英文小写，参见试题封面页）。选手提交的每道试题的源程序必须存放在相应的子目录下。未按规定建立子目录、建立的子目录名出现错误、或提交的源程序没有存放在相应的子目录下等都会导致选手成绩为0分，责任由选手承担。请注意参赛号前缀AH为大写的半角英文字符。6.所有的输入输出文件最后一行均无回车换行符。题目1．木板面积（area）一年一次的夏令营又要开始了，卡卡西和小伙伴们早就做好了准备，满心期待着这趟快乐之旅。在一个阳光明媚的清晨，卡卡西在老师的带领下来到了这次夏令营的首站——“神奇木材加工厂”。这个木材加工厂比较特别，工人们只制作圆形和长方形样式的木板，工厂的测量工人每天需要计算每块成品木板的面积以便统计使用木材的数量。如果是一个圆形木板，他们只需要测量半径的长度；如果是一个长方形木板，仅需要测量两条边的长度（单位：厘米）。对工人师傅们而言，测量是一件很简单的事，但是计算木板面积却是一件重复而又繁琐的事，看着测量工人们愁眉苦脸的样子，卡卡西急在心上，亲爱的小朋友们，你们能帮助卡卡西，为测量工人们解决这个问题吗？输入：输入数据有两行。第一行一个正整数m，表示测量的木板形状（1表示圆形，2表示长方形）；第二行有若干个数，如果m=1，第二行给出圆形的半径a（规定圆周率取3.14）；如果m=2，第二行给出长方形长和宽a，b（中间用空格隔开）。输出：木板面积。（最后输出结果四舍五入精确到小数点后2位）样例1：输入：（area.in）13.0输出:(area.out）28.26样例2：输入：（area.in）23.04.0输出:(rea.out）12.00数据范围:0≤木板边长或半径≤5002．最大长度（maxlen）聪明的卡卡西帮助工人师傅们解决了难题，师傅们为了表示感谢，特别赠送卡卡西一块三角形和一块长方形的两片小木块，并再三叮嘱卡卡西：“卡卡西，这可不是一般的小木块哦，在你迷路或走失时，它们会引领着你到达想去的地方！”“这太神奇了！谢谢！”，卡卡西如获至宝似的将这两块小木块收进包里，整晚都想着下一段奇妙的旅行。早上醒来之后，发现太阳已经高高的挂在空中，小朋友们都不见了，“不好，一定是起的太迟，没跟上大部队，这可怎么办呢？！”卡卡西懊悔的快要哭了，她赶紧站起来，收拾自己的书包，突然，包里的长方形木块和三角形木块飞了出来，组装在一起，形成一个大大的指示箭头，漂浮在空中，“对了，这个箭头一定是在告诉我，如何找到老师和同学”，卡卡西破涕为笑，满心欢喜的跟着箭头，向前方走去。走着走着，她来到了一个原木加工厂，看见老师和小朋友们都围绕在门口，一位工人叔叔正忧心忡忡的坐在地上，不停的抽着烟。卡卡西向前询问情况，这位叔叔说：“这个木材厂主要是把M根原木切割成N根长度一样的小段木头，切割时木头可以有剩余，老板让我计算可得到的这N根小段木头的最大长度（其中原木和小段木头长度都是正整数），可是我不知道该怎么算，你们能帮帮我么？”卡卡西眼前一亮，上前轻轻拍了拍叔叔的肩膀，大声的说：“叔叔，这个你放心，我来帮你完成！”小朋友们，你们能计算出切割的小段木头的最大长度吗？输入：输入共两行。第一行M、N用空格分开，分别表示原木数目和需要切割的小段木头数目。接下来一行共M个正整数，分别表示M根原木的长度（中间用空格隔开）。输出：切割后可得到的N根小段木头的最大长度。样例：输入：（maxlen.in）3741026输出：（maxlen.out）5样例说明：将3根长度分别是4、10和26的原木切割成7根长度一样的小段木头，这7根长度一样的小段木头的最大长度是5。数据范围:0≤M≤100000，0≤N≤1000003．奶牛家谱树（cowtree）卡卡西帮助原木加工厂工人解决难题之后，发现已过去2个小时，由于太专心，没注意到老师已经带着其他小朋友去了下一站——奶牛场。卡卡西在指示箭头的帮助下，加速赶路，很快来到了奶牛场，终于看见了大家，并告诉大家加工厂的问题解决啦，大家都很佩服卡卡西乐于助人的精神。奶牛场经理听了卡卡西的故事，说他这里也有一个问题需要解决，想请卡卡西帮忙，卡卡西拍着胸脯说，“没问题，交给我吧！请您告诉我问题”，经理告诉卡卡西：奶牛场准备购买一群新奶牛。在这个新的奶牛群中，每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示，这些二叉树总共有N个节点(3≤N200)，并具有如下性质:（1）每一个节点的度只能是0或2。度是这个节点的孩子的数目；（2）树的高度等于K(1K100)。高度是从根到最远的那个叶子节点所需要经过的节点数（包括根节点和最远的叶子节点）；叶子节点是指没有孩子的节点。如果一个家谱的树结构不同于另一个的，那么这两个家谱就是不同的。请问，有多少种不同的家谱树结构?输出可能的家谱树的个数除以9901的余数。输入：共一行，两个正整数N和K（中间用空格隔开），分别表示二叉树的节点总数和二叉树的高度。输出：共一行。一个正整数，表示可能的家谱树的个数除以9901的余数。样例：输入：（cowtree.in）53输出：（cowtree.out）2样例说明：输出结果表示在5个节点，高为3的情况下，有两个不同的家谱树，除以9901的余数为2。家谱树结构如下：AA/\/\BC和BC/\/\DEDE家谱树1家谱树2其中：家谱树1中共5个节点，树的高度为3，A为根节点，C、D、E为叶子节点(没有孩子节点)，A、B节点的度均为2；家谱树2中共5个节点，树的高度为3，A为根节点，B、D、E为叶子节点(没有孩子节点)，A、C节点的度均为2。数据范围:3≤N200,1K1002011年安联杯安徽省青少年信息学奥林匹克竞赛小学组试题AOI2011比赛时间：2011年4月16日08:00至12:00题目名称三次方求和最高得分字母项链源文件名cubsum.pas/c/cppmaxvalue.pas/c/cppnecklace.pas/c/cpp输入文件名cubsum.inmaxvalue.innecklace.in输出文件名cubsum.outmaxvalue.outnecklace.out试题类型传统型传统型传统型满分100100100是否有部分分否否否时限1秒1秒1秒内存限制128M128M128M注意事项1.务必看清题目，严格按照所要求的格式输入、输出。2.在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。3.测试有严格的时间限制，请尽可能优化算法。4.命名规则：(1)每题都规定了该题的英文名称。(2)程序文件和数据文件的主文件名都是该题的英文名字。(3)程序文件扩展名采用语言环境的默认扩展名。(4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。5.程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在程序中含有盘符信息和任何形式的路径信息。6.选手在竞赛结束时应在D盘根目录下建立以参赛号命名的文件夹，并将所完成各题的源程序文件放到该文件夹中。测试以评测组编译的可执行文件为准，测试系统使用的是标准的编译指令处理源程序，没有附加任何编译选项，请选手按照考试机器上语言环境的默认配置来编译调试自己的程序。题目1.三次方求和（cubsum）卡卡西要过10岁生日啦！今年，她特别想要一份与众不同的礼物，那就是一条能在阳光下发出五光十色耀眼光芒的水晶项链。她把这个想法告诉了妈妈。妈妈对卡卡西神秘的一笑，透露道：“邻居芭比阿姨家有个后花园。她的花园里有很多漂亮的水晶珠。可是芭比阿姨从来不会轻易让人进入她的后花园，你必须回答出她提出的问题，才可以进去采集水晶珠……”还没等妈妈说完，卡卡西已经迫不及待的飞奔而去。她来到芭比阿姨家，说明了来意，芭比阿姨乐呵呵的说：“卡卡西，如果你能回答出我的问题，我可以让你进入我的水晶花园。我的问题很简单，给你一个三位数，你要对这个三位数的各位数字的3次方求和，然后再对求出的和中各位数字的3次方求和，如此一直继续下去，判断最后能否得到一个不再变化的固定值。如能得到一个固定值，就告诉我这个固定值；如果不能，则告诉我提示信息“error”。注意了，在求解过程中，若某一次求和得到的值超过3位数，则取该数的低三位继续往下运算……例如：对于三位数111，则第一次计算应该是1×1×1+1×1×1+1×1×1=3。第二次应是0×0×0+0×0×0+3×3×3=27。第三次应是0×0×0+2×2×2+7×7×7=351。第四次应是3×3×3+5×5×5+1×1×1=153。第五次应是1×1×1+5×5×5+3×3×3=153，与第四次结果重合，不再计算，输出固定值153。”亲爱的小朋友们，你也来和卡卡西一起锻炼一下思维吧。输入：一行，一个三位数N（100≤N≤999）。输出：一行，如能得到一个固定值，则输出这个固定值；如不能，输出提示信息“error”。样例1：输入：（cubsum.in）111输出：（cubsum.out）153样例2：输入：（cubsum.in）102输出：（cubsum.out）error限制：40％的数据100≤N≤500。100％的数据100≤N≤999。2.最高得分（maxvalue）三次方求和的问题，被卡卡西迎刃而解，芭比阿姨拿出钥匙，打开了她后花园的大门。卡卡西被眼前的景色惊呆了！她从未见过这么多珍奇的鲜花，还有她梦寐以求的在阳光下发出异样光彩的水晶珠，她慢慢向前走着，忽然被一小块花圃吸引住了。这块花圃中，满是各式各样闪闪发亮的字母水晶珠，卡卡西心想要是能从这花圃中取出自己想要的字母水晶珠串成项链，那该多好啊！卡卡西往右手边一看，有一个告示牌，上面写道：亲爱的朋友，如果你想从花圃中获取字母水晶珠，必须先完成如下游戏：假设所有的字母水晶珠都可以采，每种字母水晶珠的单颗价值都是一样的，且采摘任意一颗水晶珠所需要的时间都是1秒，但是采摘水晶珠的总时间是有限的，那么应该如何选择自己所要的字母水晶珠，使得总价值最高呢？假设每种字母水晶珠的数量和总价值用（A,B）表示，其中A表示这种水晶珠总的数量，B表示所有这种水晶珠的总价值。例如一共有3种字母水晶珠，其数量和价值分别如下：（4，20）、（4，24）、（5，38），留给卡卡西采摘水晶珠的总时间是10秒，则选择后两种水晶珠全部摘取，第一种摘取一颗时，可得摘取的最大价值为67.00，如果选择摘前两种水晶珠和两颗第三种水晶珠，所能得价值为59.20。小朋友，你能帮助卡卡西计算出给定时间内所能采摘水晶珠的最大价值，从而让她顺利进入花圃采摘字母水晶珠吗？输入：共N+1行，第一行为两个整数N（100