투 명 테 잎

길이가 같은 두 개의 이진수 코드 A 와 B 가 있다고 하자.

이 두 코드 사이의 해밍 거리는 A 와 B 의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다.

예를 들어, A= 010010 , B= 011011 이라고 하면, 세 번째 비트와 여섯 번째 비트만 서로 다르므로 이 두 코드 사이의 해밍 거리는 2이다.

우리는 총 N 개의 이진 코드를 가지고 있고, 각 코드의 길이는 K 로 같다.

예를 들어, 다음과 같이 길이가 3 인 5 개의 이진 코드들이 있다.

• A=000
• B=111
• C=010
• D=110
• E=001

두 코드 A 와 B 사이의 해밍 거리를 로 H(A,B)로표현한다. 그러면, H(A,B) =3, H(A,C)=1,H(A,D) =2,H(A,E) =1 이다.

우리는 이진 코드들에 대해 해밍 경로를 찾고자 한다.

해밍 경로는 모든 인접한 두 코드사이의 해밍 거리가 1인 경로이다. 위의 예에서 (A,C,D)는 코드 A 와 C의 해밍 거리가 1이고, 코드 C 와 D 의 해밍 거리가 1이므로 해밍 경로이다. (A,E,B)는 코드 A 와 E 의 해밍 거리는 1이지만, 코드 E 와 B 의 해밍 거리가 2이므로 해밍 경로가 아니다.

이 문제는 주어진 두 코드 사이에 가장 짧은 해밍 경로를 구하는 프로그램을 작성하는 것이다.

프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력

• 첫째 줄에는 두 개의 정수 N 과 K 가 빈칸을 사이에 두고 주어진다(3≤N≤1,000, 2≤K≤30).
• 둘째 줄부터N 개의 줄에는 각 줄마다 길이가 K 인 이진 코드가 하나씩 주어진다. 하나의 코드는 빈칸이 없이 주어진다. 코드들은 주어진 순서대로 1부터 까지의 번호로 구분된다. 코드가 같은 경우는 없다.
• 그 다음 줄에는 해밍 경로를 찾고자 하는 서로 다른 두 개의 코드 A 와B 가 각각의 코드번호로 주어진다.

출력

만약 답이 여러 개 있으면 그 중에 하나만 출력하고, 경로가 존재하지 않으면 -1 을 출력한다.

입출력 예

입력

5 3
000
111
010
110
001
1 2

출력

1 3 4 2

출처:koi 초등지역기출
special judge:Fate

KOI 보안회사에서는 자동으로 비밀번호를 만드는 시스템을 연구하고 있다. 주어진 하나의 양의 정수에 대하여 다음의 원칙에 따라 두 수를 만들어 비밀번호를 정하려고 한다.

하나의 주어진 양의 정수 A 에 대하여 비밀번호를 위한 두 수를 만드는 방법은 다음과 같다.

1. A 의 이진수 표현에서 나오는 1의 개수 x 를 찾는다.
2. A 보다 작은수 중에서 그 수의 이진수 표현에서 1의 개수가 x 와 같고 A 에 가장 가까운 수를 하나 찾는다.
3. A 보다 큰수 중에서 그 수의 이진수 표현에서 1의 개수가 x 와 같고 A 에 가장 가까운 수를 하나 찾는다.

예를 들어, 주어진 수 A 가 43이면, 이 수의 이진수 표현은 101011₂ 이다. 이 이진수는 1의 개수가 4이다. 그러므로 43보다 작고 43에 가장 가까우며 이진수 표현에서 1의 개수가 4인 수는 39=100111₂이다. 또한 43보다 크고 43에 가장 가까우며 이진수 표현에서 1의 개수가 4인 수는 45=101101₂이다.

이 두 수를 찾아 출력하는 프로그램을 작성하시오. 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.

입력 형식

출력 형식

입력과 출력의 예

입력 

43

출력

39 45

입력 

7

출력 

0 11

출처:koi 2011 지역본선 고등 2

제목을 번역하는게 참 애매해서 영어도 같이 써놨습니다.

5 (101) 를 예로 들면

다음 큰 수는 6이고 (110)

이전 작은 수는  3이 됩니다. (11)

알고리즘 설명은 따로 안하겠습니다.

위의 프리젠테이션을 보시면 이해하실 수 있습니다.

저 프리젠테이션에 추가적으로 내용을 덧붙이자면

x의 Next Higher Number를 구하는 함수를

snoob(x)라고하면

x의 Next Lower Number는 ~snoob(~x) 를 쓰면 나옵니다.

(단, 1,3,7,15,31 과 같이 구할 수 없는 수 같은 경우는 -1이 나오게 됩니다.)

그리고 프리젠테이션에 나온 함수를

줄여 쓰고 싶다면 다음과 같이 쓸 수 있습니다.