2060번 - 염소 줄서기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 129 | 27 | 20 | 25.316% |
문제
거액 사기도박 혐의로 체포된 아기염소들은 구치소에서 저녁밥을 먹기 위해 줄을 선다. 아기염소들은 각각 저마다의 번호판을 달고 있고, 줄 서는 순서는 이 번호판의 번호에 의해 정해진다. 아기염소들은 그다지 영리하지 않기 때문에, 번호는 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번이다)
출력
첫째 줄에, 해당 위치에 있는 아기염소의 번호를 출력한다.
예제 입력 1
100 1111 5
예제 출력 1
1001
출처
Olympiad > USA Computing Olympiad > 2003-2004 Season > USACO December 2003 Contest > Green 4번
- 잘못된 번역을 찾은 사람: doju
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호