2006 年安联杯安徽省青少年信息学奥林匹克竞赛 一试试题安徽 合肥 2006.4.152006 年安徽省安联杯信息学奥林匹克竞赛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. 命名规则：(1)每题都规定了该题的英文名称2)程序文件和数据文件的主文件名都是该题的英文名字3)程序文件扩展名采用语言环境的默认扩展名4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in 和.out。
5. 程序应从输入文件读取数据，并 严格地按照规 定的输出格式将结果输出到输出文件中输入数据文件和 输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允 许在程序中含有盘符信息和任何形式的路径信息6. 选手在竞赛结束时应在硬盘指定位置建立以参赛号命名的文件夹，并将所完成各题的源程序文件和编译所产生的可执行文件(即扩展名为.exe 的文件)拷贝到该文件夹中2006 年安联杯安徽省青少年信息学奥林匹克竞赛 一试试题安徽 合肥 2006.4.15题目1. 斐波卡契的兔子（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，第二行是一个整2006 年安联杯安徽省青少年信息学奥林匹克竞赛 一试试题安徽 合肥 2006.4.15数 Q，它 们的含 义见上文描述样例：输入：0 1 1 1010000输出：89113评分方法：本题设有部分分，对于每一个测试点： 若你的程序输出的第一行 P 正确，则你的程序可以获得该测试点 60%的分数； 若你的程序输出完全正确，则你的程序可以获得该测试点 100%的分数。
注意在你的程序输出的每一行中不应该有多余的字符，数字前不应有前导0，否则 可能影响到你的得分！2. 基因匹配（Match ）卡卡昨天晚上做梦梦见他和可可来到了另外一个星球，这个星球上生物的DNA 序列由无数种碱基排列而成（地球上只有 4 种），而更奇怪的是，组成 DNA序列的每一种碱基在该序列中正好出现 5 次！这样如果一个 DNA 序列有 N 种不同的碱基构成，那么它的长度一定是 5N卡卡醒来后向可可叙述了这个奇怪的梦，而可可这些日子正在研究生物信息学中的基因匹配问题，于是他决定 为这个奇怪星球上的生物写一个 简单的 DNA匹配程序2006 年安联杯安徽省青少年信息学奥林匹克竞赛 一试试题安徽 合肥 2006.4.15为了描述基因匹配的原理，我们需要先定义子序列的概念：若从一个 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 序列的最大匹配数目样例：输入：21 1 2 2 1 1 2 1 2 21 2 2 2 1 1 2 2 1 1输出：7数据约束：60%的 测试数据中：1<= N <= 1 000100%的 测试数据中：1<=N <= 20 0002006 年安联杯安徽省青少年信息学奥林匹克竞赛 一试试题安徽 合肥 2006.4.15评分方法：本题不设部分分，对于每个测试点只有当你的程序的输出和我们的标准输出完全一致时才可以得到相应的分数。
3. 梦游超空间（Hyper）卡卡又做梦了，这次他和可可来到了一个 N 维空间 的星球我们知道，在我们的三维空间中，我们可以用下面这样的方程来描述一个椭球状的星球球面： 122czbyax其中 a, b, c 是和星球三个方向半轴长度有关的常数将这个方程推广至 N 位空间中的星球，先 设用 x1, x2, …, xN 表示 N 维坐标，而 a1, a2, …, aN 表示星球在每一维坐标轴上半轴的长度，那么就有其球面方程： 112Niiiax好了，现在卡卡和可可就可以用清晰的数学语言来描述那一团常人脑子根本想不清楚的超空间了在这个超球面上，可可和卡卡发现了一种分布不均匀的场，经过长时间的测量，他们发现场强对应 坐标 的函数可以描述如下： Nijjijxbxf 121),.(2006 年安联杯安徽省青少年信息学奥林匹克竞赛 一试试题安徽 合肥 2006.4.15其中 bij 是由星球自身决定的常数卡卡猜测，在这个星球球面上场强最高的地方，一定会有一些能揭示一切秘密的事物，但是如何找到这 个地方的坐标呢？他们找到了你。
任务：编写一个程序： 从输入文件中读入空间维数 N，星球方程 ai 和关于 场强的常数 bij； 计算出球面上场强最高的地方； 向输出文件打印你的结果输入：输入文件的第一行为一个整数 N，表示空 间 的位数第二行中有 N 个由一个空格隔开的正整数，依次 为 a1, a2, …, aN，表示球面的方程接下来有 N 行，每行 N 个由一个空格隔开的整数，其中第 i 行（总第(i +2)行）第 j 列的整数为 bij这些数值表示与场强相关的常数输出：输出文件第一行为一个实数，为你找到的场强最高点的强度第二行有 N 个由一个空格隔开的实数，依次是 这个的坐 标 x1, x2, …, xN所有实数均保留 12 位小数样例 1：输入：21 11 20 1输出：2.0000000000570.707106781167 0.707106781207样例 2：输入：510 10 20 20 20530 789 458 723 -2212006 年安联杯安徽省青少年信息学奥林匹克竞赛 一试试题安徽 合肥 2006.4.15614 652 712 903 -521804 558 590 444 59190 677 575 417 599600 811 330 -30 91输出：627679.4363344982302.795994232103 3.456328784443 12.743617414782 10.650068829539 6.717222600396 数据约束：30%的数据 ：N=2100%的数据 ：2<= N<=5, 1<=ai<=50, -1000<=bij<=1000评分方法：本题设有部分分，对于每一个测试点： 如果你的输出不合法，那么不能得分； 否则将依据你得到的解答 yourans 和参考解答 reference 的相比之优劣按如下公式给分： 其 他 情 况}10)(log4*,1max{ 106youransrefcMscreefcoyoursce其中 Maxscore 是该测试点得满分分值，而你最 终的得分将是 yourscore 四舍五入后的结果。
我们判断输出是否合法的依据：你输出的解答合法，当且仅当： 你所输出的坐标代入球面方程中，方程两边的绝对误差不超过 10-6； 你所输出的坐标代入场强公式中得到的实际场强和你输出的最大场强绝对误差不超过 10-6。