111
OIER 题库
DNA分子的最佳比对（DNA）
提交文件名：DNA.PAS 问题描述：
DNA分子是人类遗传信息的载体，它间接地指导蛋白质的合成。DNA分子是由四种核苷酸组成的长链，这四种核苷酸分别是腺嘌呤核苷酸（用A代表）、鸟嘌呤核苷酸（用G代表）、胞嘧啶核苷酸（用C代表）和胸腺嘧啶核苷酸（用T代表）。习惯上用一个字符集为{A，T，C，G}的字符串来表示一个DNA分子序列，如CGTTAGA。
在生物进化过程中，DNA分子可能发生各种各样的突变。这种突变形成了生物遗传信息的改变，从而使生物得以分化，构成了生物的多样性。主要的突变有三种：（1）在一个DNA序列中插入一个新的核苷酸，（2）DNA序列中丢失了一个核苷酸，（3）DNA序列中的某个核苷酸被另一个核苷酸所取代。 所谓两个DNA序列的一个比对是寻找一种排列方式，使得两个DNA序列在同样的位置上有相同的核苷酸，而若在同样的位置上两个DNA序列的核苷酸不同，则是由三种突变之一得到。例如，对两个DNA序列T=ATCAG，T2=ACTAG，可以按如下方式比对， 比对1： T T2 A A
T -- （“--”表示空白） C C -- T A A G G 也可以按如下方式比对 比对2：
T T2 A A T C C T A A G G
如果两个DNA序列在相同的位置上有越多相同的核苷酸对，则表明它们之间越相似，即它们存在功能上的相似性和进化史上的亲缘关系。
对于两个DNA序列的一个比对，规定如下得分方式：（1）一个同样的位置上有相同的核苷酸对，则可得1分；（2）一个同样的位置上有不同的核苷酸对，则得0分；（3）如果在某个位置上一个序列有核苷酸，而另一个序列在该位置上为“--”，则得 -2分。例如，比对1的得分是0分，比对2的得分是3分。 问题求解：
1
1对于两个DNA序列，寻找一种比对方式，使得它们的得分最高。 输入文件（DNA.IN）：
输入数据共有2行。第1行为DNA序列T, 第2行为DNA序列T2。序列的长度不大于500。序列中的字母是英文大写字母。 输出文件（DNA.IN）：
程序运行结束时，在屏幕上输出两个DNA序列比对的最高得分。
输入文件示例 INPUT3.001 Atcag Actag
K好数（K-GOOD NUMBER）
提交文件名：KGOOD.PAS 问题描述：
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。 问题求解：
给定K、L，求L位K好数的数目。 输入文件（KDOOD.IN）：
从文件读入数据，第一行为K、Ｌ，其中K<=16，L<=10。 输出文件（KDOOD.OUT）：
将结果输出到 KGOOD.OUT 输入输出样例：
KGOOD.IN 4 2
N的倍数（MULTIPLE OF N）
提交文件名：MULTIPLE.PAS 问题描述：
对于给定的一个自然数N（1≤N≤5000），和M个互不相同的十进制数字X1，X2，X3 ? XM（至少一个），找出N的一个最小的正的倍数，使得该倍数中没有X1，X2，X3 ? XM之外的其它数字。 输入文件（MULTIPLE.IN）：
输入文件第一行为整数N ，第二行为整数M，接下来M行，分别列出数字X1，X2，X3 ? XM。 输出文件（MULTIPLE.OUT）：
输出文件输出这个最小的整数，如果无解输出0。在所有的测试数据中答案都不会超过500位。 输入输出示例： MULTIPLE.IN 22 3
KGOOD.OUT 7 3
输出示例
2
7 0 1
MULTIPLE.OUT 110
巴比伦塔（THE TOWER OF BABYLON）
提交文件名：BABYLON.PAS 问题描述：
巴比伦人有n种砖块，每种数量不限。每一种砖块i是一个长方体,有三个维度(Xi,Yi,Zi)。一个砖块可被任意放置，三个维度中的任两个可作为底座，第三个作为高。巴比伦人要用堆砖块的方法建造尽可能最高的塔。问题是，建塔时，一个砖块仅当它的底座的长宽比另一个砖块的都小时，它才能堆在另一个砖块上。这意味着，两个底座相同的砖块不能堆在一起。
你的任务是要确定用所给的砖块，巴比伦人最高能堆的塔的高度。 输入文件（BABYLON.IN）：
输入文件有一组或多组测试数据。每组测试的第一行有一个整数N ，表示有N种不同种类的砖块，N 最大值为30。以下N行每行3个整数，表示一种砖块的三个维度X,Y,Z。
N = 0时输入结束。 输出文件（BABYLON.OUT）：
对每一组测试，输出该组测试的序号（从1开始）和最高可能高度，格式为： Case C: maximum height = h
其中C为测试序号，h 为最高高度。 输入输出样例： BABYLON.IN 1 10 20 30 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27
3
0
BABYLON.OUT
Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342
被毁坏的玉米地（CROP CIRCLES）
提交文件名：CROP.PAS 问题描述：
“哈姆！外星人又在那了！”。埃塞和哈姆他们的玉米地是长方形的。每年在丰收之前,他们的玉米地都会很奇怪地遭到毁坏（据埃塞说是外星人干的）。所有破坏的地方都是以1米为半径的圆。哈姆发现,如果在玉米地上建立一个适当的直角坐标系的话,那些圆心的坐标将都为整数。万幸的是,埃塞和哈姆有玉米保险,但必须把损坏的面积统计出来。
输入文件（CROP.IN）:
输入文件的第一行为一个整数N(O 输出统计出的总面积，四舍五入到小数点后4位。(Pi = 3.1415926535) 输入输出样例： CROP.IN 2 0 0 1 0 CROP.OUT 5.0548 变移单词（ANAGRAMS） 提交文件名：ANAGRAMS.PAS 问题描述： 变移单词是指由一个单词或短语的字母重新排列后组成的一个新的单词或短语。例如，“carthorse”是 4 “orchestra”的一个变移单词。在短语的变移过程中空格可以被忽略，因此，“orchestra”和“horse cart”，互为变移的单词。 写一个程序，读入一个单词表，输出表中的单词中互为变移的单词。 输入文件（ANAGRAMS.IN）： 输入为1至100行，由一个只有“#”标志行结束。每行为一个单词，都为小写字符。 输出文件（ANAGRAMS.OUT）： 输出为一些行（有可能在表中没有互为变移的单词，则为0行），每一行为两个用“=”分离的变移单词。 每个变移单词对只能输出一次，并且以字典的顺序输出，假如第一个单词一样应该以第二个单词的字典顺序排列。 输入输出样例： ANAGRAMS.IN carthorse horse horse cart i do not know u ok i now donut orchestra ANAGRAMS.OUT carthorse=horse cart carthorse=orchestra horse cart=orchestra i do not know u=ok i now donut 病毒实验（VIRUS） 提交文件名：VIRUS.PAS 问题描述： 某实验室在一种正三角型的实验器皿中进行一种特殊的病毒繁殖实验，此器皿分成很多正三角形形状的小格，每个格子的边长为1。按从上到下，从左到右的顺序对所有格子进行编号。已知在某些格子中含有病毒，为了不让这些病毒无限制的扩散，必须将有病毒的这些格子圈起来。请你编程需求出圈住这些格子所需要的材料长度。 输入文件（VIRUS.IN）： 输入文件第一行为大三角形中小格子的行数N (1≤N≤100) 输入文件第二行为含有病毒的三角形的个数M (1≤M≤2000) 以下M行分别为含有病毒的小格编号，此编号按从小到大排序 输出文件（VIRUS.OUT）： 输出文件仅一行，为圈住这些格子的边长。 输入输出样例： VIRUS.IN 4 8 3 4 6 5