初来乍到的同学先刷"分类"标签下"语言入门"题,参加初试的同学请刷"分类"标签下"数据结构"题。大伙有任何疑问,都可以在QQ群(546311977)里讨论, 群二维码在页面下方~欢迎大家咨询~另外所有通过麓研购买资料进入本OJ的全都是盗版,出题不易,请大家抵制麓研!
Problem B: PIPI的DNA序列

Problem B: PIPI的DNA序列

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 365  Solved: 185
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有m个长度均为n的DNA序列,求一个DNA序列,使其到所有序列的总HaMM距离尽量小。
HaMM距离: 两个等长字符串的HaMM距离等于字符不同的位置个数。

Input

输入包含T组测试用例。
对于每一组测试用例,第一行输入整数m和n (4<=m<=50,4<=n<=1000)。
接下来m行每行一个长度为n的DNA序列(只包含A、C、G、T)。

Output

对于每一组测试用例,输出让HaMM距离最小的DNA序列和其对应的距离。若有多解,输出字典序最小的解。

Sample Input

3
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

Sample Output

TAAGATAC
7
ACGTACGTAA
6
AAGTTACCAA
12
welcome to PIPIOJ 2025
湘ICP备19004804号