시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB437685316.562%

문제

길이 B(1 ≤ B ≤ 16)인 이진수들이 E(1 ≤ E ≤ 100)개 있다. 이 이진수들을 두 개씩 선택하여 XOR연산을 하여, 어떤 이진수를 만들려고 한다. 이 과정에서 만들어지는 이진수들을 이용하여 XOR연산을 해도 되며, 같은 두 이진수를 XOR연산을 해도 된다.

만약 우리가 만들고자 하는 이진수를 만들 수 없다면, 이 이진수와 제일 가까운 이진수를 만들려고 한다. 제일 가깝다는 것은, 두 이진수들에서 서로 다른 비트의 개수가 최소인 것을 말한다. 만약 여러 개의 이진수가 제일 가까운 경우에는, XOR 연산을 가장 적게 사용하는 이진수를 출력한다. 같은 회수의 연산을 사용한다면 사전식으로 제일 앞에 오는 이진수를 출력한다.

XOR 연산자는 ^이고, 0^0=0, 0^1=1, 1^0=1, 1^1=0이다. 10110과 11101을 XOR 연산을 하면 01011이 된다.

입력

첫째 줄에 B, E가 주어진다. 다음 줄에는 우리가 만들고자 하는 이진수를 나타내는 B개의 숫자(0 또는 1)이 주어진다. 다음 E개의 줄에는 각각의 이진수들이 주어진다.

출력

첫째 줄에 사용한 XOR 연산의 회수를 출력한다. 다음 줄에는 이진수를 출력한다. 첫째 줄에 출력한 연산의 회수는 둘째 줄의 이진수를 만들기 위해 사용한 XOR 연산의 회수이다. XOR 연산은 적어도 한 번 해야 한다.

예제 입력 1

5 3
11100
10000
01000
00100

예제 출력 1

2
11100
W3sicHJvYmxlbV9pZCI6IjIxOTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5YzRcdWMyMTggWE9SIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFlMzhcdWM3NzQgQigxICZsZTsgQiAmbGU7IDE2KVx1Yzc3OCBcdWM3NzRcdWM5YzRcdWMyMThcdWI0ZTRcdWM3NzQgRSgxICZsZTsgRSAmbGU7IDEwMClcdWFjMWMgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjNzc0XHVjOWM0XHVjMjE4XHViNGU0XHVjNzQ0IFx1YjQ1MCBcdWFjMWNcdWM1MjkgXHVjMTIwXHVkMGRkXHVkNTU4XHVjNWVjIFhPUlx1YzVmMFx1YzBiMFx1Yzc0NCBcdWQ1NThcdWM1ZWMsIFx1YzViNFx1YjVhNCBcdWM3NzRcdWM5YzRcdWMyMThcdWI5N2MgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWNmY1x1YzgxNVx1YzVkMFx1YzExYyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzBcdWIyOTQgXHVjNzc0XHVjOWM0XHVjMjE4XHViNGU0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBYT1JcdWM1ZjBcdWMwYjBcdWM3NDQgXHVkNTc0XHViM2M0IFx1YjQxOFx1YmE3MCwgXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWM3NzRcdWM5YzRcdWMyMThcdWI5N2MgWE9SXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWM2YjBcdWI5YWNcdWFjMDAgXHViOWNjXHViNGU0XHVhY2UwXHVjNzkwIFx1ZDU1OFx1YjI5NCBcdWM3NzRcdWM5YzRcdWMyMThcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQsIFx1Yzc3NCBcdWM3NzRcdWM5YzRcdWMyMThcdWM2NDAgXHVjODFjXHVjNzdjIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWM3NzRcdWM5YzRcdWMyMThcdWI5N2MgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjODFjXHVjNzdjIFx1YWMwMFx1YWU1ZFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDAsIFx1YjQ1MCBcdWM3NzRcdWM5YzRcdWMyMThcdWI0ZTRcdWM1ZDBcdWMxMWMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJlNDRcdWQyYjhcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1Yzc3OCBcdWFjODNcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWM3NzRcdWM5YzRcdWMyMThcdWFjMDAgXHVjODFjXHVjNzdjIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQsIFhPUiBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVjNzc0XHVjOWM0XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzE5XHVjNzQwIFx1ZDY4Y1x1YzIxOFx1Yzc1OCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0XHViYTc0IFx1YzBhY1x1YzgwNFx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4MWNcdWM3N2MgXHVjNTVlXHVjNWQwIFx1YzYyNFx1YjI5NCBcdWM3NzRcdWM5YzRcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5YT1IgXHVjNWYwXHVjMGIwXHVjNzkwXHViMjk0IF5cdWM3NzRcdWFjZTAsIDBeMD0wLCAwXjE9MSwgMV4wPTEsIDFeMT0wXHVjNzc0XHViMmU0LiAxMDExMFx1YWNmYyAxMTEwMVx1Yzc0NCBYT1IgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU1OFx1YmE3NCAwMTAxMVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEIsIEVcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzZiMFx1YjlhY1x1YWMwMCBcdWI5Y2NcdWI0ZTRcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1Yzc3NFx1YzljNFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgQlx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTAoMCBcdWI2MTBcdWIyOTQgMSlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgRVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1Yzc3NFx1YzljNFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NWMgWE9SIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWQ2OGNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc3NFx1YzljNFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWQ2OGNcdWMyMThcdWIyOTQgXHViNDU4XHVjOWY4IFx1YzkwNFx1Yzc1OCBcdWM3NzRcdWM5YzRcdWMyMThcdWI5N2MgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMwYWNcdWM2YTlcdWQ1NWMgWE9SIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWQ2OGNcdWMyMThcdWM3NzRcdWIyZTQuIFhPUiBcdWM1ZjBcdWMwYjBcdWM3NDAgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1YyBcdWJjODggXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMTk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ293IEltcG9zdGVycyIsImRlc2NyaXB0aW9uIjoiPHA+Rkogbm8gbG9uZ2VyIHVzZXMgdGhlIGJhcmJhcmljIGN1c3RvbSBvZiBicmFuZGluZyB0byBtYXJrIHRoZSBjb3dzIHRoYXQgaGUgb3ducy4gSW5zdGVhZCwgaGUgY3JlYXRlcyBhIGJpbmFyeSBjb2RlIG9mIEIgKDEgJmx0Oz0gQiAmbHQ7PSAxNikgYml0cyBmb3IgZWFjaCBjb3cgYW5kIGVtYm9zc2VzIGl0IG9udG8gYSBtZXRhbCBzdHJpcCB0aGF0IGlzIGZhc3RlbmVkIHRvIGVhY2ggY293JiMzOTtzIGVhci48XC9wPlxyXG5cclxuPHA+VGhlIGNvd3MgaGF2ZSB0YWtlbiBpbiBhIHN0cmF5IGFuZCB3aXNoIHRvIGNyZWF0ZSBhbiBJRCBzdHJpcCBmb3IgaXQuIFVua25vd24gdG8gRkosIHRoZXkgaGF2ZSBjcmVhdGVkIGEgbWFjaGluZSB0aGF0IGNhbiBtYWtlIGEgbmV3IElEIHN0cmlwIGJ5IGNvbWJpbmluZyB0d28gZXhpc3RpbmcgSUQgc3RyaXBzIHVzaW5nIHRoZSBYT1Igb3BlcmF0aW9uIChJRCBzdHJpcHMgYXJlIG5vdCBjb25zdW1lZCBieSB0aGlzIG1hY2hpbmUsIGFuZCB0aGUgc2FtZSBJRCBzdHJpcCBjYW4gYmUgdXNlZCBmb3IgYm90aCBpbnB1dHMpLjxcL3A+XHJcblxyXG48cD5UaGUgY293cyB3aXNoIHRvIGNyZWF0ZSBhIHNwZWNpZmljIElEIHN0cmlwIGZvciB0aGUgc3RyYXkgb3IgYXQgbGVhc3QgZ2V0IGFzIGNsb3NlIHRvIGEgZGVzaXJlZCBJRCBhcyBwb3NzaWJsZSAtLSB3aXRoIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSBudW1iZXIgb2YgYml0cyBkaWZmZXJpbmcgYmV0d2VlbiB0aGUgZ29hbCBJRCBzdHJpcCBhbmQgdGhlIGJlc3QgcG9zc2libGUgbmV3IElEIHN0cmlwLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHNldCBvZiBFICgxICZsdDs9IEUgJmx0Oz0gMTAwKSBleGlzdGluZyBJRCBzdHJpcHMsIHRoZSBnb2FsIElEIHN0cmlwLCBhbmQgYSBsYXJnZSBudW1iZXIgb2YgYmxhbmsgSUQgc3RyaXBzIHRvIGhvbGQgaW50ZXJtZWRpYXRlIHJlc3VsdHMsIGNhbGN1bGF0ZSB0aGUgY2xvc2VzdCBwb3NzaWJsZSBJRCBzdHJpcCB0aGF0IGNhbiBiZSBjcmVhdGVkIGZyb20gdGhlIGV4aXN0aW5nIElEIHN0cmlwcy48XC9wPlxyXG5cclxuPHA+SWYgbW9yZSB0aGFuIG9uZSBJRCBpcyBjbG9zZXN0LCBjaG9vc2UgdGhlIG9uZSB0aGF0IGNhbiBiZSBjcmVhdGVkIGluIHRoZSBmZXdlc3Qgc3RlcHMuIElmIHRoZXJlIGlzIHN0aWxsIGEgdGllLCBjaG9vc2UgdGhlIGBzbWFsbGVzdCYjMzk7IElEIChpLmUuLCBpZiB5b3Ugc29ydGVkIGFsbCB0aGUgSURzLCB0aGUgb25lIHRoYXQgaXMgZmlyc3QpLjxiciBcLz5cclxuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogQiBhbmQgRS48XC9saT5cclxuXHQ8bGk+TGluZSAyOiBUaGUgZ29hbCBJRCBzdHJpbmcsIHJlcHJlc2VudGVkIGFzIGEgc3RyaW5nIG9mIEIgMCYjMzk7cyBhbmQgMSYjMzk7cyAod2l0aCBubyBzcGFjZXMpLjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAzLi5FKzI6IEVhY2ggbGluZSBjb250YWlucyBhbiBleGlzdGluZyBJRCBzdHJpbmcsIHJlcHJlc2VudGVkIGFzIGEgc3RyaW5nIG9mIEIgMCYjMzk7cyBhbmQgMSYjMzk7cyAod2l0aCBubyBzcGFjZXMpLjxiciBcLz5cclxuXHQmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0ZXBzIHJlcXVpcmVkIHRvIGNyZWF0ZSB0aGUgYmVzdCBwb3NzaWJsZSBJRCBzdHJpcC48XC9saT5cclxuXHQ8bGk+TGluZSAyOiBBIHNpbmdsZSBsaW5lIHdpdGggdGhlIGJlc3QgcG9zc2libGUgSUQgc3RyaXAgdGhhdCBjYW4gYmUgY3JlYXRlZCBmcm9tIHRoZSBFIGV4aXN0aW5nIElEIHN0cmlwczxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO February 2003 Contest > Green 2번

  • 빠진 조건을 찾은 사람: ntopia