시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 3640 1957 1676 57.123%

문제

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오티드의 첫글자를 따서 표현한다. 만약에 Thymine-Adenine-Adenine-Cytosine-Thymine-Guanine-Cytosine-Cytosine-Guanine-Adenine-Thymine로 이루어진 DNA가 있다고 하면, “TAACTGCCGAT”로 표현할 수 있다. 그리고 Hamming Distance란 길이가 같은 두 DNA가 있을 때, 각 위치의 뉴클오티드 문자가 다른 것의 개수이다. 만약에 “AGCAT"와 ”GGAAT"는 첫 번째 글자와 세 번째 글자가 다르므로 Hamming Distance는 2이다.

우리가 할 일은 다음과 같다. N개의 길이 M인 DNA s1, s2, ..., sn가 주어져 있을 때 Hamming Distance의 합이 가장 작은 DNA s를 구하는 것이다. 즉, s와 s1의 Hamming Distance + s와 s2의 Hamming Distance + s와 s3의 Hamming Distance ... 의 합이 최소가 된다는 의미이다.

입력

첫 줄에 DNA의 수 N과 문자열의 길이 M이 주어진다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 DNA가 주어진다. N은 1,000보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 Hamming Distance의 합이 가장 작은 DNA 를 출력하고, 둘째 줄에는 그 Hamming Distance의 합을 출력하시오. 그러한 DNA가 여러 개 있을 때에는 사전순으로 가장 앞서는 것을 출력한다.

예제 입력 1

5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

예제 출력 1

TAAGATAC
7

예제 입력 2

4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA

예제 출력 2

ACGTACGTAA
6

예제 입력 3

6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

예제 출력 3

AAGTTACCAA
12
W3sicHJvYmxlbV9pZCI6IjE5NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJETkEiLCJkZXNjcmlwdGlvbiI6IjxwPkROQVx1Yjc4MCBcdWM1YjRcdWI1YTQgXHVjNzIwXHVjODA0XHViYjNjXHVjOWM4XHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWJkODRcdWM3OTBcdWM3NzRcdWIyZTQuIFx1Yzc3NCBETkFcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCA0XHVhYzAwXHVjOWMwXHVjNzU4IFx1YjI3NFx1ZDA3NFx1YjgwOFx1YzYyNFx1ZDJmMFx1YjRkY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0KEFkZW5pbmUsIFRoeW1pbmUsIEd1YW5pbmUsIEN5dG9zaW5lKS4gXHVjNmIwXHViOWFjXHViMjk0IFx1YzViNFx1YjVhNCBETkFcdWM3NTggXHViYjNjXHVjOWM4XHVjNzQ0IFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWI1NGMsIFx1Yzc3NCBETkFcdWI5N2MgXHVjNzc0XHViOGU4XHViMjk0IFx1YjI3NFx1ZDA3NFx1YjgwOFx1YzYyNFx1ZDJmMFx1YjRkY1x1Yzc1OCBcdWNjYWJcdWFlMDBcdWM3OTBcdWI5N2MgXHViNTMwXHVjMTFjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkXHVjNWQwIFRoeW1pbmUtQWRlbmluZS1BZGVuaW5lLUN5dG9zaW5lLVRoeW1pbmUtR3VhbmluZS1DeXRvc2luZS1DeXRvc2luZS1HdWFuaW5lLUFkZW5pbmUtVGh5bWluZVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgRE5BXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWJhNzQsICZsZHF1bztUQUFDVEdDQ0dBVCZyZHF1bztcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBIYW1taW5nIERpc3RhbmNlXHViNzgwIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3NDAgXHViNDUwIEROQVx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFjMDEgXHVjNzA0XHVjZTU4XHVjNzU4IFx1YjI3NFx1ZDA3NFx1YzYyNFx1ZDJmMFx1YjRkYyBcdWJiMzhcdWM3OTBcdWFjMDAgXHViMmU0XHViOTc4IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjljY1x1YzU3ZFx1YzVkMCAmbGRxdW87QUdDQVQmcXVvdDtcdWM2NDAgJnJkcXVvO0dHQUFUJnF1b3Q7XHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVjNjQwIFx1YzEzOCBcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVhYzAwIFx1YjJlNFx1Yjk3NFx1YmJjMFx1Yjg1YyBIYW1taW5nIERpc3RhbmNlXHViMjk0IDJcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YWMwMCBcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuIE5cdWFjMWNcdWM3NTggXHVhZTM4XHVjNzc0IE1cdWM3NzggRE5BIHM8c3ViPjE8XC9zdWI+LCBzPHN1Yj4yPFwvc3ViPiwgLi4uLCBzPHN1Yj5uPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzQ0IFx1YjU0YyBIYW1taW5nIERpc3RhbmNlXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIEROQSBzXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgc1x1YzY0MCBzPHN1Yj4xPFwvc3ViPlx1Yzc1OCBIYW1taW5nIERpc3RhbmNlICsgc1x1YzY0MCBzPHN1Yj4yPFwvc3ViPlx1Yzc1OCBIYW1taW5nIERpc3RhbmNlICsgc1x1YzY0MCBzPHN1Yj4zPFwvc3ViPlx1Yzc1OCBIYW1taW5nIERpc3RhbmNlIC4uLiBcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MWNcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBETkFcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBOXHVhYzFjXHVjNzU4IEROQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgMSwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWFjZTAsIE1cdWM3NDAgNTBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBIYW1taW5nIERpc3RhbmNlXHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIEROQSBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOCBIYW1taW5nIERpc3RhbmNlXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWRmOFx1YjdlY1x1ZDU1YyBETkFcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHViNTRjXHVjNWQwXHViMjk0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjMTFjXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTk2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkROQSBDb25zZW5zdXMgU3RyaW5nIiwiZGVzY3JpcHRpb24iOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RuYWIxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjM3MXB4OyB3aWR0aDoyNjlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5ETkEgKERlb3h5cmlib251Y2xlaWMgQWNpZCkgaXMgdGhlIG1vbGVjdWxlIHdoaWNoIGNvbnRhaW5zIHRoZSBnZW5ldGljIGluc3RydWN0aW9ucy4gSXQgY29uc2lzdHMgb2YgZm91ciBkaWZmZXJlbnQgbnVjbGVvdGlkZXMsIG5hbWVseSBBZGVuaW5lLCBUaHltaW5lLCBHdWFuaW5lLCBhbmQgQ3l0b3NpbmUgYXMgc2hvd24gaW4gRmlndXJlIDEuIElmIHdlIHJlcHJlc2VudCBhIG51Y2xlb3RpZGUgYnkgaXRzIGluaXRpYWwgY2hhcmFjdGVyLCBhIEROQSBzdHJhbmQgY2FuIGJlIHJlZ2FyZGVkIGFzIGEgbG9uZyBzdHJpbmcgKHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMpIGNvbnNpc3Rpbmcgb2YgdGhlIGZvdXIgY2hhcmFjdGVycyBBLCBULCBHLCBhbmQgQy4gRm9yIGV4YW1wbGUsIGFzc3VtZSB3ZSBhcmUgZ2l2ZW4gc29tZSBwYXJ0IG9mIGEgRE5BIHN0cmFuZCB3aGljaCBpcyBjb21wb3NlZCBvZiB0aGUgZm9sbG93aW5nIHNlcXVlbmNlIG9mIG51Y2xlb3RpZGVzOiAmbGRxdW87VGh5bWluZS1BZGVuaW5lLUFkZW5pbmUtQ3l0b3NpbmUtVGh5bWluZS1HdWFuaW5lLUN5dG9zaW5lLUN5dG9zaW5lLUd1YW5pbmUtQWRlbmluZS1UaHltaW5lJnJkcXVvOyBUaGVuIHdlIGNhbiByZXByZXNlbnQgdGhlIGFib3ZlIEROQSBzdHJhbmQgd2l0aCB0aGUgc3RyaW5nICZsZHF1bztUQUFDVEdDQ0dBVC4mcmRxdW87PFwvcD5cclxuXHJcbjxwPlRoZSBiaW9sb2dpc3QgUHJvZi4gQWhuIGZvdW5kIHRoYXQgYSBnZW5lIFggY29tbW9ubHkgZXhpc3RzIGluIHRoZSBETkEgc3RyYW5kcyBvZiBmaXZlIGRpZmZlcmVudCBraW5kcyBvZiBhbmltYWxzLCBuYW1lbHkgZG9ncywgY2F0cywgaG9yc2VzLCBjb3dzLCBhbmQgbW9ua2V5cy4gSGUgYWxzbyBkaXNjb3ZlcmVkIHRoYXQgdGhlIEROQSBzZXF1ZW5jZXMgb2YgdGhlIGdlbmUgWCBmcm9tIGVhY2ggYW5pbWFsIHdlcmUgdmVyeSBhbGlrZS4gU2VlIEZpZ3VyZSAyLiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RuYWIyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2OXB4OyB3aWR0aDozNjJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Qcm9mLiBBaG4gdGhvdWdodCB0aGF0IGh1bWFucyBtaWdodCBhbHNvIGhhdmUgdGhlIGdlbmUgWCBhbmQgZGVjaWRlZCB0byBzZWFyY2ggZm9yIHRoZSBETkEgc2VxdWVuY2Ugb2YgWCBpbiBodW1hbiBETkEuIEhvd2V2ZXIsIGJlZm9yZSBzZWFyY2hpbmcsIGhlIHNob3VsZCBkZWZpbmUgYSByZXByZXNlbnRhdGl2ZSBETkEgc2VxdWVuY2Ugb2YgZ2VuZSBYIGJlY2F1c2UgaXRzIHNlcXVlbmNlcyBhcmUgbm90IGV4YWN0bHkgdGhlIHNhbWUgaW4gdGhlIEROQSBvZiB0aGUgZml2ZSBhbmltYWxzLiBIZSBkZWNpZGVkIHRvIHVzZSB0aGUgSGFtbWluZyBkaXN0YW5jZSB0byBkZWZpbmUgdGhlIHJlcHJlc2VudGF0aXZlIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5UaGUgSGFtbWluZyBkaXN0YW5jZSBpcyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBjaGFyYWN0ZXJzIGF0IGVhY2ggcG9zaXRpb24gZnJvbSB0d28gc3RyaW5ncyBvZiBlcXVhbCBsZW5ndGguIEZvciBleGFtcGxlLCBhc3N1bWUgd2UgYXJlIGdpdmVuIHRoZSB0d28gc3RyaW5ncyAmbGRxdW87QUdDQVQmcmRxdW87IGFuZCAmbGRxdW87R0dBQVQuJnJkcXVvOyBUaGUgSGFtbWluZyBkaXN0YW5jZSBvZiB0aGVzZSB0d28gc3RyaW5ncyBpcyAyIGJlY2F1c2UgdGhlIDFzdCBhbmQgdGhlIDNyZCBjaGFyYWN0ZXJzIG9mIHRoZSB0d28gc3RyaW5ncyBhcmUgZGlmZmVyZW50LiBVc2luZyB0aGUgSGFtbWluZyBkaXN0YW5jZSwgd2UgY2FuIGRlZmluZSBhIHJlcHJlc2VudGF0aXZlIHN0cmluZyBmb3IgYSBzZXQgb2YgbXVsdGlwbGUgc3RyaW5ncyBvZiBlcXVhbCBsZW5ndGguIEdpdmVuIGEgc2V0IG9mIHN0cmluZ3Mge3M8c3ViPjE8XC9zdWI+LCAuLi4sIHM8c3ViPm08XC9zdWI+fSBvZiBsZW5ndGggbiwgdGhlIGNvbnNlbnN1cyBlcnJvciBiZXR3ZWVuIGEgc3RyaW5nIHkgb2YgbGVuZ3RoIG4gYW5kIHRoZSBzZXQgUyBpcyB0aGUgc3VtIG9mIHRoZSBIYW1taW5nIGRpc3RhbmNlcyBiZXR3ZWVuIHkgYW5kIGVhY2ggczxzdWI+aTxcL3N1Yj4gaW4gUy4gSWYgdGhlIGNvbnNlbnN1cyBlcnJvciBiZXR3ZWVuIGlzIHkgYW5kIFMgaXMgdGhlIG1pbmltdW0gYW1vbmcgYWxsIHBvc3NpYmxlIHN0cmluZ3Mgb2YgbGVuZ3RoIG4sIGlzIGNhbGxlZCBhIGNvbnNlbnN1cyBzdHJpbmcgb2YuIEZvciBleGFtcGxlLCBnaXZlbiB0aGUgdGhyZWUgc3RyaW5ncyAmbGRxdW87QUdDQVQmcmRxdW87LCAmbGRxdW87QUdBQ1QmcmRxdW87LCBhbmQgJmxkcXVvO0dHQUFUJnJkcXVvOywgdGhlIGNvbnNlbnN1cyBzdHJpbmcgb2YgdGhlIGdpdmVuIHN0cmluZ3MgaXMgJmxkcXVvO0FHQUFUJnJkcXVvOyBiZWNhdXNlIHRoZSBzdW0gb2YgdGhlIEhhbW1pbmcgZGlzdGFuY2VzIGJldHdlZW4gJmxkcXVvO0FHQUFUJnJkcXVvOyBhbmQgdGhlIHRocmVlIHN0cmluZ3MgaXMgMyB3aGljaCBpcyBtaW5pbWFsLiAoSW4gdGhpcyBjYXNlLCB0aGUgY29uc2Vuc3VzIHN0cmluZyBpcyB1bmlxdWUsIGJ1dCBpbiBnZW5lcmFsLCB0aGVyZSBjYW4gYmUgbW9yZSB0aGFuIG9uZSBjb25zZW5zdXMgc3RyaW5nLikgV2UgdXNlIHRoZSBjb25zZW5zdXMgc3RyaW5nIGFzIGEgcmVwcmVzZW50YXRpdmUgb2YgdGhlIEROQSBzZXF1ZW5jZS4gRm9yIHRoZSBleGFtcGxlIG9mIEZpZ3VyZSAyIGFib3ZlLCBhIGNvbnNlbnN1cyBzdHJpbmcgb2YgZ2VuZSBYIGlzICZsZHF1bztHQ0FBQVRHR0NUR1RHQ0EmcmRxdW87IGFuZCB0aGUgY29uc2Vuc3VzIGVycm9yIGlzIDcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIGFuZCB3aGljaCBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgaW50ZWdlciBtICg0ICZsZTsgbSAmbGU7IDUwKSByZXByZXNlbnRzIHRoZSBudW1iZXIgb2YgRE5BIHNlcXVlbmNlcyBhbmQgbig0ICZsZTsgbiAmbGU7IDEwMDApIHJlcHJlc2VudHMgdGhlIGxlbmd0aCBvZiB0aGUgRE5BIHNlcXVlbmNlcywgcmVzcGVjdGl2ZWx5LiBJbiBlYWNoIG9mIHRoZSBuZXh0IG0gbGluZXMsIGVhY2ggRE5BIHNlcXVlbmNlIGlzIGdpdmVuLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IHRoZSBjb25zZW5zdXMgc3RyaW5nIGluIHRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggY2FzZSBhbmQgdGhlIGNvbnNlbnN1cyBlcnJvciBpbiB0aGUgc2Vjb25kIGxpbmUgb2YgZWFjaCBjYXNlLiBJZiB0aGVyZSBleGlzdHMgbW9yZSB0aGFuIG9uZSBjb25zZW5zdXMgc3RyaW5nLCBwcmludCB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgc21hbGxlc3QgY29uc2Vuc3VzIHN0cmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBzaG93cyBzYW1wbGUgaW5wdXQgYW5kIG91dHB1dCBmb3IgdGhyZWUgdGVzdCBjYXNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2006 B번

  • 빠진 조건을 찾은 사람: jsa3824
  • 잘못된 번역을 찾은 사람: previc1
  • 데이터를 추가한 사람: sohnjunior
  • 잘못된 데이터를 찾은 사람: tncks0121