2009年ACM程序设计竞赛选拔赛试题—1.doc

2009年ACM程序设计竞赛选拔赛试题 考生需知： 答案必须写在答题纸上，写在试卷上无效。 程序采用C/C++语言实现，其他程序设计语言无效。 考虑到各种因素，程序的键盘输入和结果输出可以用伪代码或者自然语言表示。但是必须说明输入变量和输出变量。 题目最好能用完整、正确的C语言程序来解决问题，如确实无法编写完整C语言程序的，可以写出程序主要框架和流程，必要时可以用伪代码或者自然语言描述算法（程序）。 一、水仙花数（10分） 所谓“水仙花数”是指一个3位数，其各位数字的立方之和等于该数本身。 例如，153是一水仙花数，因为153＝13＋53＋33。 请输出所有的“水仙花数”。 二、完数（10分） 数的因子就是所有可以整除这个数的数,但是不包括这个数自身。比如15的因子是1，3，5?3 0 0 1 0 0 1 3 0 0 2 0 0 2 0 样例输出： 0.5 2.0 五、聪明的情侣（15分） 酋长的女儿艾丽要出嫁了，按以往的风俗习惯，要搭个高台，台下是众多的求婚者，艾丽在台上扔束花，扔在台下谁身上，艾丽就得嫁给谁。但她担心落不到心爱的雷蒙身上。艾丽私下约雷蒙商量如何是好。雷蒙想出了一个主意……艾丽便和父亲说：“我不愿意搭台撒花，这么多人来，挤在一起乱哄哄的，没秩序。”父亲说，“不这样也可以，但结婚时要当场在人群中决定嫁给谁，不许指名，方法你自己定。”艾丽高兴的告诉主持人如何行事。婚日来临，人群拥挤，主持人叫求婚者排成一队，雷蒙在队外数了数队列共有101人，于是自己找了个合适的位置也站在队列中，主持人要大家从前往后1，2，1，2……报数，报单数的退出场外，余下的人位置不变，再重新从前往后1，2，1，2……报数，报单数的退场，如此下去最后只剩一人，艾丽便嫁给谁。大家惊奇的发现最后剩下的竟是雷蒙。请用程序回答雷蒙刚开始站在队列中的第几个位置。 六、最佳编码（15分） 某通讯单位打算传递一段信息“XYZWYZWZYWYXZY”,为提高安全性，打算将字母W,X,Y,Z分别用不同的0,1编码进行表示，并希望编码后，该段信息的编码总长度越短越好。请编写程序设计编码方案。 七、汤姆的玩具（15分） 小汤姆有好多玩具，他都非常喜欢玩。可下个星期他们家就要般到另一个城市去了，他的妈妈觉得那些玩具带着太麻烦，准备都扔掉。小汤姆实在舍不得这些玩具，就向妈妈求情，妈妈后来同意可以带一部分玩具走，她给了小汤姆一个小箱子，让他自己挑选。你现在就帮小汤姆想想办法，看看怎么样用这个小箱子带走最多的玩具。 程序输入： 第一行输入的两个数据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分） 秀水村是一个美丽的山村，可长期以来，村民们的房子都零散的分布在各个地方，没有道路直接相连，大家走动不便，为了方便大家串门，村长决定带领大家修建道路连接各家各户。但由于修路要花很多钱（修的路越长，花费越多），村里经费不足，因此村长召集大家一起商量，看怎么样修路花钱最少，还能把各家各户都连起来。你现在就帮助村民们设计一下修路方案吧。 程序输入： 每一行输入的三个数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 答题纸 成绩： 姓名： 学号： 专业 级 班