2006年安徽省安联杯信息学奥林匹克竞赛(第一试).doc

2006年安徽省安联杯信息学奥林匹克竞赛 AHOI 2006 第一试 比赛时间：2006年4月15日8:00至11:00 题目名称 斐波卡契的兔子 基因匹配 梦游超空间 可执行文件名 kacci.exe match.exe hyper.exe 输入文件名 kacci.in match.in hyper.in 输出文件名 kacci.out match.out hyper.out 试题类型 传统型 传统型 传统型 满分 100 100 100 是否有部分分 是 否 是 时限 3秒 1秒 2秒 注意事项 务必看清题目，严格按照所要求的格式输入、输出。 在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。 测试有严格的时间限制，请尽可能优化算法。 命名规则：(1)每题都规定了该题的英文名称。(2)程序文件和数据文件的主文件名都是该题的英文名字。(3)程序文件扩展名采用语言环境的默认扩展名。(4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。 程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在程序中含有盘符信息和任何形式的路径信息。 选手在竞赛结束时应在硬盘指定位置建立以参赛号命名的文件夹，并将所完成各题的源程序文件和编译所产生的可执行文件(即扩展名为.exe的文件)拷贝到该文件夹中。 题目 斐波卡契的兔子（Kacci） 最近，卡卡开始玩一个叫《牧场物语》的网络游戏，在游戏中卡卡办了一个养兔场！开始的时候他只有一对刚出生的兔子，经过一段时间的饲养，卡卡了解到兔子的繁殖规律是这样的：才出生的一对兔子在一个月后将第一次生出一胎a对兔子，接着在出生后的二个月又将生出b对兔子，在第三个月和以后每个月都会繁殖c对兔子(a = b = c，其中0=a = b = c=100)。 由于繁殖的过程类似于斐波纳契数列，所以卡卡给它的养兔场取名叫“斐波卡契”。繁殖出的兔子都是可以到市场上卖的，但是游戏中限定一个玩家只能买一对兔子，现在已知有k个玩家，卡卡想在m个月后让他们每个人都能买到一对，他的愿望是否能够实现呢？（1=m=3 000, 1=k=106 000）（题目中每对兔子均为一公一母） 任务：编写一个程序： 从输入文件中读入输入信息； 计算m个月后卡卡将有多少对兔子，设之为P； 计算如果m个月后卡卡要拥有至少k对兔子，那么开始时他至少应该有多少对兔子，设之为Q； 将结果输出至输出文件。 输入：输入文件的第一行有4个由一个空格隔开的正整数：a, b, c和m；而第二行则仅含一个正整数k。它们的含义见上文描述。 输出：你的程序将向输出文件输出两行，第一行是一个整数P，第二行是一个整数Q，它们的含义见上文描述。 样例： 输入： 0 1 1 10 10000 输出： 89 113 评分方法： 本题设有部分分，对于每一个测试点： 若你的程序输出的第一行P正确，则你的程序可以获得该测试点60%的分数； 若你的程序输出完全正确，则你的程序可以获得该测试点100%的分数。 注意在你的程序输出的每一行中不应该有多余的字符，数字前不应有前导0，否则可能影响到你的得分！ 基因匹配（Match） 卡卡昨天晚上做梦梦见他和可可来到了另外一个星球，这个星球上生物的DNA序列由无数种碱基排列而成（地球上只有4种），而更奇怪的是，组成DNA序列的每一种碱基在该序列中正好出现5次！这样如果一个DNA序列有N种不同的碱基构成，那么它的长度一定是5N。 卡卡醒来后向可可叙述了这个奇怪的梦，而可可这些日子正在研究生物信息学中的基因匹配问题，于是他决定为这个奇怪星球上的生物写一个简单的DNA匹配程序。 为了描述基因匹配的原理，我们需要先定义子序列的概念：若从一个DNA序列（字符串）s中任意抽取一些碱基（字符），将它们仍按在s中的顺序排列成一个新串u，则称u是s的一个子序列。对于两个DNA序列s1和s2，如果存在一个序列u同时成为s1和s2的子序列，则称u是s1和s2的公共子序列。 卡卡已知两个DNA序列s1和s2，求s1和s2的最大匹配就是指s1和s2最长公共子序列的长度。 任务：编写一个程序： 从输入文件中读入两个等长的DNA序列； 计算它们的最大匹配； 向输出文件打印你得到的结果。 输入：输入文件中第一行有一个整数N，表示这个星球上某种生物使用了N种不同的碱基，以后将它们编号为1…N的整数。 以下还有两行，每行描述一个DNA序列：包含5N个1…N的整数，整数之间由一个空格隔开，且每一个整数在对应的序列中正好出现5次。 输出：输出文件中只有一个整数，即两个DNA序列的最大匹配数目。 样例： 输入： 2