大学生程序设计竞赛试题(正式赛)..docVIP

中原工学院第一届大学生程序设计竞赛 正式比赛试题 主办：中原工学院教务处 学生处 校团委 计算机学院 承办：中原工学院计算机学院 地点：计算机学院实验中心406实验室 时间：2010年4月11日 【试题一】 兔子 【题目描述】 兔子具有很强的繁殖能力。一对成年兔子每个月可以繁殖一对小兔子，而一对小兔子经过m个月之后，就会长成一对成年兔子。通过分析，我们可以看出：若m=2的时候，每个月兔子的对数构成了一个Fibonacci数列。 但是，若m2，这个问题看起来就不那么简单了。你的任务是计算：假定初始只有一对兔子，那么，经过d个月之后，共有多少对兔子？可以假定，在此阶段没有任何兔子死亡。 【输入】 输入包括多组测试数据。每组测试数据的一行中包括2个整数m(1=m=10)，d(1=d=30)。当测试数据遇到一行中有两个0时，即m=d=0，测试数据结束。 【输出】 针对每组测试数据，在每一行输出经过d个月后共有多少对兔子。 【输入样例】 2 3 3 5 0 0 【输出样例】 5 9 【试题二】 网页浏览器 【题目描述】 Mozilla Firefox是一个自由的，开放源码的网页浏览器，适用于Windows, Linux 和 MacOS X等平台。Firefox火狐校园大使是Mozilla开源社区项目的一部分，针对在校的高年级本科生和研究生以及众多技术爱好者，在校园中推广开源项目和开放技术，让更多的开发人员受益于Mozilla的开放技术和免费资源。你很荣幸得到了这样一个机会，为Firefox编写一个重要的导航模块。 正如上图所示，导航模块要接受用户的后退、前进、进入用户输入的网址以及清空浏览记录等操作。 【输入】 为了简化问题，用户所有的操作都以字符的形式从标准输入读入。每一行描述一个操作，各操作的格式和功能如下所示： 操作 功能 back 如果当前页面不是第一个页面，则跳到到前一个页面，并输出这个页面的网址 forward 如果当前页面不是最后一个页面，则跳到到后一个页面，并输出这个页面的网址 url 网址 跳转到用户输入的网址（网址不含空格） clear 清空浏览记录（当前页面除外） exit 退出浏览器 浏览器启动时默认进入中原工学院的主页” ” 【输出】 对于每一个需要输出网址的操作，输出对应的网址。每个网址恰好占一行，不要有多余的字符（包括空格和换行）。详细格式可以参考输入输出样例。 【输入样例】 url /chinacampus/ url back back back forward clear url / forward back back exit 【输出样例】 /chinacampus/ /chinacampus/ /chinacampus/ 【试题三】 茶商 【题目描述】 一位茶叶商人从南方收购了n吨新茶，由于产地偏僻不通铁路，茶商准备先沿水路运到武汉，再发往全国各地销售。码头上只有m条规格不同的小货船，每条船都不足以装载全部茶叶。各船的最大载重量分别为w[i]吨，需f[i]费用(1=i=m)。当然，由于茶商是老主顾，而且货船还可以搭载其他货物，因此船主比较客气，声称可以装一部分货物，按实际装多少货物计费（例如，只装了1/3载重，则费用也为1/3）。 请问，茶商应该选择哪些货船，使得费用最低？ 【输入】 输入包括多组测试数据。每组测试数据的第一行为2个非负整数n和m，其含义如题目描述所示。接下来的m行，每行有两个非负整数w[i]和f[i]，代表每条船的最大载重量和费用。当测试数据遇到一行中有两个-1时，测试数据结束。所有的整数不超过1000。 【输出】 针对每组测试数据，在每一行输出一个唯一的整数，表示茶商所需要的最少运费（运算过程中可以采用浮点数，输出最终结果时取整）。 【输入样例】 15 3 7 2 4 3 5 2 30 3 25 18 24 15 15 10 -1 -1 【输出样例】 6 21 【试题四】 中原工学院网络系统 【题目描述】 虽然中原工学院的网络安全已经做得非常完善，但是天有不测风云，学校内部网络系统的一台服务器意外感染了一种新型病毒。为了避免更大的损失，管理员必须采取紧急措施遏制病毒的蔓延。中原工学院内部网络系统共有n台服务器，这n台服务器使用m条电缆互相连接。为了描述方便，我们给服务器编号1到n。初始时，1号服务器感染了病毒。每隔一分钟，病毒便会从已感染病毒的服务器扩散到所有与之直接相连的服务器上。中原工学院的网络系统设计得非常坚固，即使要切断电缆也非常困难。管理员只能在初始时切断一根电缆。为了让整个网络系统尽可能晚地全部被病毒感染，他应该切断哪根电缆？ 【输入】 输入包含