2009年acm程序设计竞赛选拔赛试题 - 1

《2009年acm程序设计竞赛选拔赛试题 - 1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2009年ACM程序设计竞赛选拔赛试题考生需知：1、答案必须写在答题纸上，写在试卷上无效。2、程序采用C/C++语言实现，其他程序设计语言无效。3、考虑到各种因素，程序的键盘输入和结果输出可以用伪代码或者自然语言表示。但是必须说明输入变量和输出变量。4、题目最好能用完整、正确的C语言程序来解决问题，如确实无法编写完整C语言程序的，可以写出程序主要框架和流程，必要时可以用伪代码或者自然语言描述算法（程序）。一、水仙花数（10分）所谓“水仙花数”是指一个3位数，其各位数字的立方之和等于该数本身。例如，153是一水仙花数，因

2、为153＝13＋53＋33。请输出所有的“水仙花数”。二、完数（10分）数的因子就是所有可以整除这个数的数,但是不包括这个数自身。比如15的因子是1，3，5 。如果一个正整数如果正好等于它的所有因子之和，这个数就称为“完数”。例如，6的因子为1，2，3，而6＝1＋2＋3，因此6是“完数”。请输出1000以内有几个这样的完数。三、走楼梯（10分）楼上走到楼下共有h个台阶，每一步有3种走法：走1个台阶；走2个台阶；走3个台阶。问可走多少种方案？样例输入：10样例输出：230四、贝克的农场（10分）贝克有一个很大的农场,他想

3、用栅栏把农场上的奶牛圈起来．为此，他需要在农场上打下木桩后再围栅栏，他只有n(n<2000)根木桩,他想知道他在农场上打下木桩围上栅栏后所围成的区域的面积.木桩围成的面积是由这n根木桩首尾顺次用直线连接形成的区域的面积,并且假定贝克只围成凸多边形.如右图:程序输入：输入数据可能有多组，每组第一行输入n(3≤n≤2000),表示有n根木桩,下面是n根木桩在农场上的位置(按照1,2,3...n的顺序).木桩位置是由(x,y)表示,其中x,y是绝对值小于1000的整数.输入n=0时表示所有输入结束.程序输出：输出每组情况下围

4、成的面积，保留小数点后一位.每组情况占一行．样例输入：300100130020样例输出：0.52.0good,noloosening.6.5.2DCSsidewiringtocompletetheenclosureandtheothersideafterthewiringiscompleted,DCSwithintheenclosurewhenthepowermoduleshouldbeloosenedorthepowergoesout.6.6lowvoltagecableterminalmaking6.6.1firs

5、t020五、聪明的情侣（15分）酋长的女儿艾丽要出嫁了，按以往的风俗习惯，要搭个高台，台下是众多的求婚者，艾丽在台上扔束花，扔在台下谁身上，艾丽就得嫁给谁。但她担心落不到心爱的雷蒙身上。艾丽私下约雷蒙商量如何是好。雷蒙想出了一个主意……艾丽便和父亲说：“我不愿意搭台撒花，这么多人来，挤在一起乱哄哄的，没秩序。”父亲说，“不这样也可以，但结婚时要当场在人群中决定嫁给谁，不许指名，方法你自己定。”艾丽高兴的告诉主持人如何行事。婚日来临，人群拥挤，主持人叫求婚者排成一队，雷蒙在队外数了数队列共有101人，于是自己找了个合适的

6、位置也站在队列中，主持人要大家从前往后1，2，1，2……报数，报单数的退出场外，余下的人位置不变，再重新从前往后1，2，1，2……报数，报单数的退场，如此下去最后只剩一人，艾丽便嫁给谁。大家惊奇的发现最后剩下的竟是雷蒙。请用程序回答雷蒙刚开始站在队列中的第几个位置。六、最佳编码（15分）某通讯单位打算传递一段信息“XYZWYZWZYWYXZY”,为提高安全性，打算将字母W,X,Y,Z分别用不同的0,1编码进行表示，并希望编码后，该段信息的编码总长度越短越好。请编写程序设计编码方案。七、汤姆的玩具（15分）小汤姆有好多玩

7、具，他都非常喜欢玩。可下个星期他们家就要般到另一个城市去了，他的妈妈觉得那些玩具带着太麻烦，准备都扔掉。小汤姆实在舍不得这些玩具，就向妈妈求情，妈妈后来同意可以带一部分玩具走，她给了小汤姆一个小箱子，让他自己挑选。你现在就帮小汤姆想想办法，看看怎么样用这个小箱子带走最多的玩具。程序输入：第一行输入的两个数据a和b分别表示箱子的体积和玩具的总数，接下来的b行每行输入的两个数据x和y，分别表示玩具的编号和体积。输入数据以两个0结束。程序输出：能够带走的玩具编号。样例输入：10611283443556200样例输出：1346

8、八、秀水村的道路（输入文件：road.in，输出文件：road.out）（15分）秀水村是一个美丽的山村，可长期以来，村民们的房子都零散的分布在各个地方，没有道路直接相连，大家走动不便，为了方便大家串门，村长决定带领大家修建道路连接各家各户。但由于修路要花很多钱（修的路越长，花费越多），村里经费不足，因此村长召集大家一起商量，看怎