시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 58 13 9 32.143%

문제

거액 사기도박 혐의로 체포된 아기염소들은 구치소에서 저녁밥을 먹기 위해 줄을 선다. 아기염소들은 각각 저마다의 번호판을 달고 있고, 줄 서는 순서는 이 번호판의 번호에 의해 정해진다. 아기염소들은 그다지 영리하지 않기 때문에, 번호는 0과 1로만 이루어진 이진수 형태를 띤다. 각각의 번호의 길이는 31비트를 넘지 않는다.

아기염소들은 우리가 예상하는 이런 순서로 줄을 서지 않는다. 0, 1, 10, 11, 100, ......

그 대신, 다음과 같은 규칙에 의한 우선순위에 따른다.

  • 번호판에서 1의 총 개수가 더 적은 아기염소가 밥을 먼저 먹는다.
  • 1의 총 개수가 서로 같을 경우, 번호를 이진수로 보았을 때 더 작은 번호의 아기염소가 밥을 먼저 먹는다. (위에서 우리가 예상했던 순서와 같다)

따라서 1000 (1이 1개)은 110 (1이 2개) 보다 우선순위가 먼저다. 100번부터 1111번까지의 모든 아기염소들을 순서대로 나열해보면 다음과 같다.

100, 1000, 101, 110, 1001, 1010, 1100, 111, 1011, 1101, 1110, 1111

번호가 정확히 0번인 아기염소를 제외하고는, 어떤 아기염소의 번호도 0으로 시작할 수 없다.

A번부터 B번까지 염소가 있을 때, 우선순위에 따라 정렬했을 때, X번째 염소의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A가, 둘째 줄에 B가 주어진다.

셋째 줄에, 우리가 그 번호를 구하고자 하는 아기염소의 위치가 주어진다. (물론 첫번째 아기염소는 1번이다)

출력

첫째 줄에, 해당 위치에 있는 아기염소의 번호를 출력한다.

예제 입력

100
1111
5

예제 출력

1001

힌트

출처

  • 잘못된 번역을 찾은 사람: doju