铜陵市2006奥赛选拔赛.doc

铜陵市青少年信息学奥林匹克竞赛市队选拔赛测试试卷(2006-03)考生须知*若试卷中试题字迹不清，考生可以在审题时举手请求解释，由考务人员加以说明。涉及题意理解问题，则不得提问且考务人员不予解答。*考生上机编程时应在指定目录下工作，并请每隔5分钟存盘一次。发生机器故障时由考务人员确认补给修复时间，且最长不超过10分钟。*对考生答题测试有严格时间限制，若超时则该测试项判为0分。考生应注意优化算法。*考生应严格遵守考场规则，不得违纪。*考试时间为8时30分至11时30分，计180分钟（其中30分钟为审题时间）。试卷满分为180分第一部分试题一、换钱（20分）【题目】把一元钞票换成一分、二分、五分硬币（每种至少一枚），有哪些种换法？试题二、求因数个数（30分）【题目】任给一个自然数n,求出这个自然数不同因数的个数。例如 n=6时，因为1,2,3,6这四个数均是的因数，故输出为total=。数据输入:由文件input.0提供输入数据。文件的每一行给出n的值。结果输出: 对于输入文件中每一行的正整数n，将计算出的结果输出到文件out.0中。输入文件示例input.0输出文件示例out.064试题三、化简繁分式（本题满分35分）【题目】化简繁分式 11+- 式子中共含N条分数线 (1=N100) 1 要求化为一般分式 1+- . 1 1+ - 2数据输入: 由文件input.000提供输入数据。文件的每一行给出n的值。结果输出: 对于输入文件中每一行的正整数n，将计算出的结果输出到文件out.000中。测试数据输入文件示例input.000输出文件示例out.00013/225/3第二部分试题一、宝石项链问题（本题满分35分）“B&N”公司是生产珠宝项链的著名产商。该公司的产品中有一款由彩色宝石串成的项链倍受客户的青睐。客户们在购买宝石项链时都希望买到与众不同宝石项链。“B&N”公司产品开发部的工程师希望迅速计算出用c种不同颜色的宝石能串成多少种长度为s的宝石项链。这里所说的长度是指项链中用的宝石的个数。例如，用红色和蓝色2种颜色的5颗宝石，在不考虑旋转和翻转等价的情况下，共有25=32种不同的宝石项链。如果这32种宝石项链中的一串宝石项链经过旋转或翻转与另一串宝石项链相同，就认为这2串宝石项链属于同一种宝石项链。事实上，用红色和蓝色2种颜色的5颗宝石能制作出8种不同的宝石项链。编程任务: 对于给定的正整数c和s，计算出用c种不同颜色的宝石能串成多少种长度为s的宝石项链。数据输入: 由文件input.001提供输入数据。文件的每一行给出2个正整数c和s的值，其中c表示宝石的颜色数，s表示项链的长度。由于制作工艺的要求，每一行中c和s的值满足cs=32。文件的最后一行为0，表示文件结束。结果输出: 对于输入文件中每一行的正整数c和s，将计算出的用c种不同颜色的宝石串成长度为s的宝石项链数输出到文件out.001中。输入文件示例input.001输出文件示例out.0011 12 12 25 12 52 66 20 0123581321试题二、金币游戏问题（本题满分30分）Sam Loyd 先生发明了一个有趣的翻币游戏。在一个特制的棋盘中有N x M个方格，每个方格中放1枚金币。方格中的金币或正面朝上，或反面朝上。棋盘的每一行的左侧都有一个黑色按钮，可以控制该行中金币的朝向。每按一次黑色按钮，相应行中的所有金币翻转。棋盘每一列上方都有一个白色按钮，用于交换2列中的金币。同时按第i列和第j列的白色按钮，可以交换第i列和第j列的金币，且保持金币在原列中的位置和朝向。 翻币游戏要求游戏者对于金币在棋盘中的一个给定初始布局，通过操纵棋盘上的黑白按钮，达到一确定的目标布局。编程任务: 对于金币在棋盘中的一个给定初始布局和目标布局，编程计算是否可通过操纵棋盘上的黑白按钮，从初始布局达到目标布局。数据输入: 由文件input.002提供输入数据。文件含多个测试数据项。文件的第一行中只有1个整数k，表示共有k个测试数据项。每个测试数据项的第一行中有2个整数n 和m分别表示棋盘的行数和列数。接着的2n行中，前n行表示该测试数据项的初始布局，后n行表示该测试数据项的目标布局。每行有m个符号（+或-）表示该行中金币的朝向。“+”表示金币正面朝上，“-” 表示金币反面朝上。结果输出: 对每个测试数据项，如果可通过操纵棋盘上的黑白按钮，从初始布局达到目标布局则输出“Yes”， 否则输出“No”。所有结果输出到文件out.002中。输入文件示例input.002输出文件示例out.00223 4- + - + - - +- - - - + - + + - - - - -2 2- - + + +YesNo试题三、小鼠迷宫问题 (本题满分30分)源程序：maze.c/maze.cpp/maze.pas/maze.pp问题描述：小鼠a与小鼠b身处一个mn的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这mn个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。图 小鼠的迷宫编程任务：对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。数据输入：由文件input.txt给出输入数据。第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。结果输出:将计算出的小鼠a通向小鼠b的最短路长度和有多少条不同的最短路输出到文件output.t