시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 131 19 15 20.833%

문제

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

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

C에서 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 연산은 적어도 한 번 해야 한다.

예제 입력

5 3
11100
10000
01000
00100

예제 출력

2
11100

힌트

출처

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