《2009年ACM程序设计竞赛选拔赛试题-1.pdf》由会员分享，可在线阅读，更多相关《2009年ACM程序设计竞赛选拔赛试题-1.pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2009 年 ACM 程序设计竞赛选拔赛试题考生需知：1、答案必须写在答题纸上，写在试卷上无效。2、程序采用 C/C+语言实现，其他程序设计语言无效。3、考虑到各种因素，程序的键盘输入和结果输出可以用伪代码或者自然语言表示。但是必须说明输入变量和输出变量。4、题目最好能用完整、正确的C语言程序来解决问题，如确实无法编写完整C语言程序的，可以写出程序主要框架和流程，必要时可以用伪代码或者自然语言描述算法（程序）。一、水仙花数（10 分）所谓“水仙花数”是指一个3 位数，其各位数字的立方之和等于该数本身。例如，153 是一水仙花数，因为15313 5333。请输出所有的“水仙花数”。二、完数（10
2、 分）数的因子就是所有可以整除这个数的数,但是不包括这个数自身。比如15 的因子是1，3，5。如果一个正整数如果正好等于它的所有因子之和，这个数就称为“完数”。例如，6 的因子为1，2，3，而 6123，因此 6 是“完数”。请输出 1000 以内有几个这样的完数。三、走楼梯（10 分）楼上走到楼下共有h 个台阶，每一步有3 种走法：走 1 个台阶；走 2 个台阶；走 3 个台阶。问可走多少种方案？样例输入：10 样例输出：230 四、贝克的农场（10 分）贝克有一个很大的农场,他想用栅栏把农场上的奶牛圈起来为此，他需要在农场上打下木桩后再围栅栏，他只有n(n 2000)根木桩,他想知道他在农
3、场上打下木桩围上栅栏后所围成的区域的面积.木桩围成的面积是由这n 根木桩首尾顺次用直线连接形成的区域的面积,并且假定贝克只围成凸多边形.如右图:程序输入：输入数据可能有多组，每组第一行输入n(3 n 2000),表示有 n 根木桩,下面是 n 根木桩在农场上的位置(按照 1,2,3.n的顺序).木桩位置是由(x,y)表示,其中 x,y 是绝对值小于1000 的整数.输入 n=0 时表示所有输入结束.程序输出：输出每组情况下围成的面积，保留小数点后一位.每组情况占一行样例输入：3 0 0 1 0 0 1 3 0 0 2 0 0 2 0 样例输出：0.5 2.0 五、聪明的情侣（15 分）酋长的女
4、儿艾丽要出嫁了，按以往的风俗习惯，要搭个高台，台下是众多的求婚者，艾丽在台上扔束花，扔在台下谁身上，艾丽就得嫁给谁。但她担心落不到心爱的雷蒙身上。艾丽私下约雷蒙商量如何是好。雷蒙想出了一个主意,艾丽便和父亲说：“我不愿意搭台撒花，这么多人来，挤在一起乱哄哄的，没秩序。”父亲说，“不这样也可以，但结婚时要当场在人群中决定嫁给谁，不许指名，方法你自己定。”艾丽高兴的告诉主持人如何行事。婚日来临，人群拥挤，主持人叫求婚者排成一队，雷蒙在队外数了数队列共有101 人，于是自己找了个合适的位置也站在队列中，主持人要大家从前往后1，2，1，2,报数，报单数的退出场外，余下的人位置不变，再重新从前往后1，2
5、，1，2,报数，报单数的退场，如此下去最后只剩一人，艾丽便嫁给谁。大家惊奇的发现最后剩下的竟是雷蒙。请用程序回答雷蒙刚开始站在队列中的第几个位置。六、最佳编码（15 分）某通讯单位打算传递一段信息“XYZWYZWZYWYXZY”,为提高安全性，打算将字母W,X,Y,Z分别用不同的0,1 编码进行表示，并希望编码后，该段信息的编码总长度越短越好。请编写程序设计编码方案。七、汤姆的玩具（15 分）小汤姆有好多玩具，他都非常喜欢玩。可下个星期他们家就要般到另一个城市去了，他的妈妈觉得那些玩具带着太麻烦，准备都扔掉。小汤姆实在舍不得这些玩具，就向妈妈求情，妈妈后来同意可以带一部分玩具走，她给了小汤姆一
6、个小箱子，让他自己挑选。你现在就帮小汤姆想想办法，看看怎么样用这个小箱子带走最多的玩具。程序输入：第一行输入的两个数据a 和 b 分别表示箱子的体积和玩具的总数，接下来的b 行每行输入的两个数据x 和 y，分别表示玩具的编号和体积。输入数据以两个0 结束。程序输出：能够带走的玩具编号。样例输入：10 6 1 1 2 8 3 4 4 3 5 5 6 2 0 0 样例输出：1 3 4 6 八、秀水村的道路（输入文件：road.in，输出文件：road.out）（15 分）秀水村是一个美丽的山村，可长期以来，村民们的房子都零散的分布在各个地方，没有道路直接相连，大家走动不便，为了方便大家串门，村长决
7、定带领大家修建道路连接各家各户。但由于修路要花很多钱（修的路越长，花费越多），村里经费不足，因此村长召集大家一起商量，看怎么样修路花钱最少，还能把各家各户都连起来。你现在就帮助村民们设计一下修路方案吧。程序输入：每一行输入的三个数a,b,c 表示房子 a和房子 b 之间的距离为 c，输入数据以三个0 结束。程序输出：每一行输出两个数x 和 y，表示应该在房子 x 和房子 y 之间修一条道路。样例输入：（输入文件：road.in）1 2 2 2 4 3 1 4 4 3 5 5 2 5 6 2 3 6 3 4 10 4 5 15 0 0 0 样例输出：（输出文件：road.out）1 2 2 4 3 5 2 5 答题纸成绩：姓名：学号：专业级班