時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
兩個同長度字串的 Hamming 距離，是對應位置字元不同的個數。給定 m 個長度 n 的 DNA 字串，找出一個長度 n 的字串，使它與所有輸入字串的 Hamming 距離總和最小。若有多個最優字串，輸出字典序最小者，字母順序為 A < C < G < T。
輸入格式
第一行為測試筆數 T。每筆先給 m、n，4 ≤ m ≤ 50，4 ≤ n ≤ 1000；接著 m 行各有一個只含 A、C、G、T 的長度 n 字串。
輸出格式
每筆輸出兩行：第一行為最優代表字串，第二行為最小距離總和。
題目來源：UVa 1368 — DNA Consensus String，CPE 歷屆試題。 原題：https://onlinejudge.org/external/13/1368.pdf
範例測資
範例輸入 1
3 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA 6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA
範例輸出 1
TAAGATAC 7 ACGTACGTAA 6 AAGTTACCAA 12
請先登入後再提交程式碼
討論與題解
載入討論區…