이진수 XOR
시간 제한2초메모리 제한128 MB
이진 문자열들을 XOR 조합해 목표 문자열에 가장 가까운 값을 찾고, 거리와 연산 수, 사전순으로 동점을 처리하는 문제입니다.
문제
길이가 B인 이진수 E개가 주어진다. (1 <= B <= 16, 1 <= E <= 100)
이미 가지고 있는 이진수나 XOR 연산으로 새로 만든 이진수 중 두 개를 골라 XOR할 수 있다. 같은 이진수를 두 번 골라도 된다.
목표 이진수를 만들 수 있다면 그 이진수를 출력한다. 만들 수 없다면 목표 이진수와 가장 가까운 이진수를 출력한다. 두 이진수의 거리는 서로 다른 비트의 개수이다.
거리가 같은 후보가 여러 개라면, 그 이진수를 만들기 위해 필요한 XOR 연산 횟수가 가장 적은 것을 고른다. 그래도 여러 개라면 사전순으로 가장 앞서는 이진수를 고른다.
XOR 연산자는 ^이다. 각 비트에서 0^0=0, 0^1=1, 1^0=1, 1^1=0이며, 10110 ^ 11101의 결과는 01011이다.
입력
첫째 줄에 B와 E가 주어진다.
둘째 줄에 만들고자 하는 길이 B의 이진수가 주어진다.
다음 E개의 줄에는 사용할 수 있는 길이 B의 이진수가 하나씩 주어진다.
출력
첫째 줄에 선택한 이진수를 만들기 위해 사용한 XOR 연산 횟수를 출력한다.
둘째 줄에 선택한 이진수를 출력한다.
XOR 연산은 적어도 한 번 수행해야 한다.