시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 531 | 84 | 66 | 17.010% |
길이 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 연산은 적어도 한 번 해야 한다.
5 3 11100 10000 01000 00100
2 11100
Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO February 2003 Contest > Green 2번