2010년 정보 올림피아드 지역 본선 고등부 문제 5번 임
c언어 소스 짜는 사람 진짜 천재임..

그레이 코드

 

이진 코드 중에서 모든 인접한 코드가 한 비트만 서로 다르면 그레이(Gray) 코드라고 말한다. 첫째 코드와 마지막 코드도 인접하다고 보고 한 비트만 달라야 한다. 아래에 3-비트 그레이 코드가 있다. 첫 번째 코드와 둘째 코드, 둘째와 셋째, …, 그리고 마지막 코드 100은 첫째 코드 000과 1비트만 다르다.

 

000 - 001 - 011 - 010 - 110 - 111 - 101 - 100

 

그레이 코드에서, 111과 한 비트가 다른 110, 101은 코드에서 인접하게 나타나지만, 역시 한 비트가 다른 011은 그렇지 않다. 이 사실을 관찰한 철희군은 111과 011이 인접한 그레이 코드가 존재하는가 하는 문제에 호기심이 발동하였고, 그런 코드가 있다는 것을 손으로 확인하였다. 비트 수  이 더 큰 경우에는 손으로 확인하기가 어려워, 컴퓨터 프로그램을 작성하기로 하였다.

한 비트가 다른 쌍들이 하나 혹은 둘 주어질 때, 그 쌍이 인접하다는 조건을 만족하는 그레이 코드가 존재하는가를 확인하고, 존재하면 조건을 만족하는 그레이 코드를 출력하는 프로그램을 작성하라.

실행파일의 이름은 GRAY.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

 

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 입력 파일의 첫째 줄에 코드에서 비트의 수를 나타내는 M (3≤ M≤15)과 인접해야 하는 코드 쌍의 수K (1≤ K ≤2)가 주어진다. 이어서  개의 줄에 한 줄에 하나씩 인접하기를 원하는 코드 쌍이 빈칸을 사이에 두고 입력된다.

 

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 조건을 만족하는 그레이 코드가 존재하면, 그레이 코드를 000…0부터 시작하여 차례로 한 줄에 코드 8개씩 2의 (M-3)승 줄에 걸쳐서 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력하면 된다. 조건을 만족하는 그레이 코드가 존재하지 않으면 -1을 출력한다.

 

입력과 출력의 예 (1)


입력 (INPUT.TXT)

3 2

000 001

100 101




출력 (OUTPUT.TXT)

000 001 011 010 110 111 101 100



 

입력과 출력의 예 (2)


입력 (INPUT.TXT)

3 2

000 001

011 001




출력 (OUTPUT.TXT)

000 001 011 010 110 111 101 100