{"trustable":false,"sections":[{"title":"","value":{"format":"PLAIN","content":"DNA(Deoxyribonucleic Acid,脱氧核糖核酸)是包含遗传指令的分子,它由四种不同的核苷酸组成,即腺嘌呤、胸腺嘧啶、关氨酸和胞嘧啶。 它由四种不同的核苷酸组成,即腺嘌呤、胸腺嘧啶、鸟嘌呤和胞嘧啶,如图1所示。 如果我们用它的初始字符来表示一个核苷酸,那么一条DNA链就可以看作是由A、T、G、C这四个字符组成的长串(字符序列)。\n\n\"胸腺-腺嘌呤-腺嘌呤-胞嘧啶-腺嘌呤-胞嘧啶-腺嘌呤-胸腺\"\n\n那么我们就可以用字符串TAACTGCCGAT来表示上述DNA链。\"\n\n生物学家安教授发现,一种基因X普遍存在于五种不同动物的DNA链中,即狗、猫、马、牛和猴子。他还发现,每种动物的基因X的DNA序列都非常相似。见图2。\n\n基因X的DNA序列\nCat:GCATATGGCTGTGCA\n狗:GCAAATGGCTGTGCA\n马:GCTAATGGGTGTCCA\n牛:GCAAATGGCTGTGCA。\n猴子:GCAAATCGGTGAGCA\n\n图2.X基因在动物体内的DNA序列 基因X在动物体内的DNA序列。\n\n安教授认为人类可能也有基因X,于是决定寻找人类DNA中X的DNA序列。但是,在寻找之前,他必须要找到一个有代表性的基因X的DNA序列,因为它在五种动物的DNA中的序列并不完全相同。他决定用汉明距离来定义代表序列。\n\n汉明距离是指两个长度相等的字符串在每个位置上的不同字符数。例如,假设给我们两个字符串 \"AGCAT \"和 \"GGAAT\"。这两个字符串的汉明距离为2,因为这两个字符串的第1个和第3个字符是不同的.利用汉明距离,我们可以定义一组等长的多个字符串的代表字符串。给定一组长度为n的字符串S\u003d{s1,...,s_m},长度为n的字符串y与集合S之间的共识误差是y与S中每个si之间的汉明距离之和,如果y与S之间的共识误差是所有可能的长度为n的字符串y中的最小值,则称y为S的共识字符串。例如,给定三个字符串 \"AGCAT\"\"AGACT \"和 \"GGAAT\",给定字符串的共识字符串是 \"AGAT\",因为 \"AGAT \"和三个字符串之间的汉明距离之和是3,是最小的。(在这种情况下,共识字符串是唯一的,但一般情况下,可以有多个共识字符串)。我们将共识串作为DNA序列的代表。对于上面图2的例子,基因X的共识串是 \"GCAAATGGCTGTGCA\",共识错误是7。"}},{"title":"输入","value":{"format":"PLAIN","content":"你的程序要从标准输入中读取。输入由T个测试用例组成,测试用例的数量在输入的第一行给出。测试用例的数量T在输入的第一行给出。每一个测试用例都以包含两个整数m和n的行开始,这两个整数用一个空格隔开。整数m(4\u003c\u003dm\u003c\u003d50)分别代表DNA序列的数量,n(4\u003c\u003dn\u003c\u003d1000)分别代表DNA序列的长度。在接下来的每一行m中,都给出了每个DNA序列。"}},{"title":"輸出結果","value":{"format":"PLAIN","content":"你的程序要写到标准输出。在每个案例的第r行打印共识字符串,在每个案例的第二行打印共识错误。如果存在一个以上的共识字符串,打印词法上最小的共识字符串。 "}},{"title":"样品输入","value":{"format":"PLAIN","content":"3\n5 8\nTATGATAC\nTAAGCTAC\nAAAGATCC\nTGAGATAC\nTAAGATGT\n4 10\nACGTACGTAC\nCCGTACGTAG\nCCGTACGTAT\nTCGTACGTAA\n6 10\nATGTTACCAT\nAAGTTACGAT\nAACAAAGCAA\nAAGTTACCTT\nAAGTTACCAA\nTACTTACCAA"}},{"title":"采样输出","value":{"format":"PLAIN","content":"TAAGATAC\n7\nACGTACGTAA\n6\nAAGTTACCAA\n12"}}]}