시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB110231625.397%

문제

거액 사기도박 혐의로 체포된 아기염소들은 구치소에서 저녁밥을 먹기 위해 줄을 선다. 아기염소들은 각각 저마다의 번호판을 달고 있고, 줄 서는 순서는 이 번호판의 번호에 의해 정해진다. 아기염소들은 그다지 영리하지 않기 때문에, 번호는 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
W3sicHJvYmxlbV9pZCI6IjIwNjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZmNcdWMxOGMgXHVjOTA0XHVjMTFjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjNzBcdWM1NjEgXHVjMGFjXHVhZTMwXHViM2M0XHViYzE1IFx1ZDYxMFx1Yzc1OFx1Yjg1YyBcdWNjYjRcdWQzZWNcdWI0MWMgXHVjNTQ0XHVhZTMwXHVjNWZjXHVjMThjXHViNGU0XHVjNzQwIFx1YWQ2Y1x1Y2U1OFx1YzE4Y1x1YzVkMFx1YzExYyBcdWM4MDBcdWIxNDFcdWJjMjVcdWM3NDQgXHViYTM5XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM5MDRcdWM3NDQgXHVjMTIwXHViMmU0LiBcdWM1NDRcdWFlMzBcdWM1ZmNcdWMxOGNcdWI0ZTRcdWM3NDAgXHVhYzAxXHVhYzAxIFx1YzgwMFx1YjljOFx1YjJlNFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWQzMTBcdWM3NDQgXHViMmVjXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjOTA0IFx1YzExY1x1YjI5NCBcdWMyMWNcdWMxMWNcdWIyOTQgXHVjNzc0IFx1YmM4OFx1ZDYzOFx1ZDMxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YzgxNVx1ZDU3NFx1YzljNFx1YjJlNC4gXHVjNTQ0XHVhZTMwXHVjNWZjXHVjMThjXHViNGU0XHVjNzQwIFx1YWRmOFx1YjJlNFx1YzljMCBcdWM2MDFcdWI5YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViYzg4XHVkNjM4XHViMjk0IDBcdWFjZmMgMVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjNzc0XHVjOWM0XHVjMjE4IFx1ZDYxNVx1ZDBkY1x1Yjk3YyBcdWI3NjRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDMxXHViZTQ0XHVkMmI4XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1YWUzMFx1YzVmY1x1YzE4Y1x1YjRlNFx1Yzc0MCBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjNjA4XHVjMGMxXHVkNTU4XHViMjk0IFx1Yzc3NFx1YjdmMCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjOTA0XHVjNzQ0IFx1YzExY1x1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuJm5ic3A7MCwgMSwgMTAsIDExLCAxMDAsIC4uLi4uLjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMzAwXHVjMmUwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWM3NThcdWQ1NWMgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHVjNWQwIFx1YjUzMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJjODhcdWQ2MzhcdWQzMTBcdWM1ZDBcdWMxMWMgMVx1Yzc1OCBcdWNkMWQgXHVhYzFjXHVjMjE4XHVhYzAwIFx1YjM1NCBcdWM4MDFcdWM3NDAgXHVjNTQ0XHVhZTMwXHVjNWZjXHVjMThjXHVhYzAwIFx1YmMyNVx1Yzc0NCBcdWJhM2NcdWM4MDAgXHViYTM5XHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4xXHVjNzU4IFx1Y2QxZCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjMTFjXHViODVjIFx1YWMxOVx1Yzc0NCBcdWFjYmRcdWM2YjAsIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM3NzRcdWM5YzRcdWMyMThcdWI4NWMgXHViY2Y0XHVjNTU4XHVjNzQ0IFx1YjU0YyBcdWIzNTQgXHVjNzkxXHVjNzQwIFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWM1NDRcdWFlMzBcdWM1ZmNcdWMxOGNcdWFjMDAgXHViYzI1XHVjNzQ0IFx1YmEzY1x1YzgwMCBcdWJhMzlcdWIyOTRcdWIyZTQuIChcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzYwOFx1YzBjMVx1ZDU4OFx1YjM1OCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVhYzE5XHViMmU0KTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYyAxMDAwICgxXHVjNzc0IDFcdWFjMWMpXHVjNzQwIDExMCAoMVx1Yzc3NCAyXHVhYzFjKSBcdWJjZjRcdWIyZTQgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHVhYzAwIFx1YmEzY1x1YzgwMFx1YjJlNC4gMTAwXHViYzg4XHViZDgwXHVkMTMwIDExMTFcdWJjODhcdWFlNGNcdWM5YzBcdWM3NTggXHViYWE4XHViNGUwIFx1YzU0NFx1YWUzMFx1YzVmY1x1YzE4Y1x1YjRlNFx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMDk4XHVjNWY0XHVkNTc0XHViY2Y0XHViYTc0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjEwMCwgMTAwMCwgMTAxLCAxMTAsIDEwMDEsIDEwMTAsIDExMDAsIDExMSwgMTAxMSwgMTEwMSwgMTExMCwgMTExMTxcL3A+XHJcblxyXG48cD5cdWJjODhcdWQ2MzhcdWFjMDAgXHVjODE1XHVkNjU1XHVkNzg4IDBcdWJjODhcdWM3NzggXHVjNTQ0XHVhZTMwXHVjNWZjXHVjMThjXHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMFx1YjI5NCwgXHVjNWI0XHViNWE0IFx1YzU0NFx1YWUzMFx1YzVmY1x1YzE4Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWIzYzQgMFx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+QVx1YmM4OFx1YmQ4MFx1ZDEzMCBCXHViYzg4XHVhZTRjXHVjOWMwIFx1YzVmY1x1YzE4Y1x1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWM2YjBcdWMxMjBcdWMyMWNcdWM3MDRcdWM1ZDAgXHViNTMwXHViNzdjIFx1YzgxNVx1YjgyY1x1ZDU4OFx1Yzc0NCBcdWI1NGMsIFhcdWJjODhcdWM5ZjggXHVjNWZjXHVjMThjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEFcdWFjMDAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG5cclxuPHA+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1YzZiMFx1YjlhY1x1YWMwMCBcdWFkZjggXHViYzg4XHVkNjM4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NThcdWIyOTQgXHVjNTQ0XHVhZTMwXHVjNWZjXHVjMThjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChcdWJiM2NcdWI4NjAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM1NDRcdWFlMzBcdWM1ZmNcdWMxOGNcdWIyOTQgMVx1YmM4OFx1Yzc3NFx1YjJlNCk8XC9zcGFuPjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1ZDU3NFx1YjJmOSBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzU0NFx1YWUzMFx1YzVmY1x1YzE4Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIwNjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3cgUXVldWVpbmciLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjb3dzIGFyZSBsaW5pbmcgdXAgZm9yIGRpbm5lci4gVGhleSB1c2UgYW4gb3JkZXIgZGV0ZXJtaW5lZCBieSB0aGUgbnVtZXJpY2FsIGJyYW5kcyBvbiB0aGVpciBoaWRlLiBGSiBrbmV3IHRoZSBjb3dzIHdlcmVuJiMzOTt0IHRvbyBicmlnaHQsIHNvIGhlIHVzZWQgYnJhbmRzIHdpdGggb25seSAmIzM5OzAmIzM5O3MgYW5kICYjMzk7MSYjMzk7cy4gRWFjaCBjb3cgcmVjZWl2ZWQgYSBicmFuZCB3aG9zZSBsZW5ndGggd2FzIG5vIGxvbmdlciB0aGFuIDMxIGJpdHMuPFwvcD5cclxuXHJcbjxwPlRoZSBub3Qtc28tYnJpZ2h0IGNvd3MgZG9uJiMzOTt0IGxpbmUgdXAgaW4gdGhlIG9yZGVyIHdlIG1pZ2h0IGV4cGVjdDogMCwgMSwgMTAsIDExLCAxMDAsIGV0Yy48XC9wPlxyXG5cclxuPHA+SW5zdGVhZCwgdGhleSBsaW5lIHVwIGluIGFuIG9yZGVyIHdoZXJlIHRoZSBicmFuZHMgYXJlIHNvcnRlZCBieSB0aGVzZSBydWxlczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIGJyYW5kIHdpdGggZmV3ZXIgJiMzOTsxJiMzOTtzIHByZWNlZGVzIGEgYnJhbmQgd2l0aCBtb3JlICYjMzk7MSYjMzk7czxcL2xpPlxyXG5cdDxsaT5Gb3IgYnJhbmRzIHdpdGggdGhlIHNhbWUgbnVtYmVyIG9mICYjMzk7MSYjMzk7cywgdGhlIGJyYW5kIHdpdGggdGhlIHNtYWxsZXN0IG1hZ25pdHVkZSAoY2FsY3VsYXRlZCB0cmFkaXRpb25hbGx5KSBjb21lcyBmaXJzdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRodXMsIHRoZSBjb3cgd2l0aCBicmFuZCAxMDAwIChhIHNpbmdsZSAmIzM5OzEmIzM5OykgbGluZXMgdXAgYmVmb3JlIHRoZSBjb3cgd2l0aCBicmFuZCAxMTAgKHR3byAmIzM5OzEmIzM5O3MpLiBUaGUgb3JkZXIgb2YgdGhlIDEyIGNvd3MgbnVtYmVyZWQgMTAwIHRocm91Z2ggMTExMSBpczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xMDA8XC9saT5cclxuXHQ8bGk+MTAwMDxcL2xpPlxyXG5cdDxsaT4xMDE8XC9saT5cclxuXHQ8bGk+MTEwPFwvbGk+XHJcblx0PGxpPjEwMDE8XC9saT5cclxuXHQ8bGk+MTAxMDxcL2xpPlxyXG5cdDxsaT4xMTAwPFwvbGk+XHJcblx0PGxpPjExMTxcL2xpPlxyXG5cdDxsaT4xMDExPFwvbGk+XHJcblx0PGxpPjExMDE8XC9saT5cclxuXHQ8bGk+MTExMDxcL2xpPlxyXG5cdDxsaT4xMTExPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RXhjZXB0IGZvciB0aGUgJiMzOTswJiMzOTsgYnJhbmQsIGJyYW5kcyBkb24mIzM5O3QgaGF2ZSBsZWFkaW5nIHplcm9lcy4gSGFwcGlseSwgaWYgYnJhbmQgTSBpcyBwcmVzZW50IGluIGxpbmUgYW5kIGJyYW5kIE4gaXMgcHJlc2VudCBpbiBsaW5lLCB0aGVuIGFsbCBicmFuZHMgd2hvc2UgbWFnbml0dWRlIGZhbGxzIGJldHdlZW4gTSBhbmQgTiBpcyBwcmVzZW50IGluIGxpbmUuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBmaW5kIHdoaWNoIGNvdyBpcyBpbiBhIGdpdmVuIHBsYWNlIGluIGxpbmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgYmluYXJ5IGludGVnZXI6IHRoZSBjb3cgYnJhbmQgd2hvc2UgbWFnbml0dWRlIGlzIHRoZSBzbWFsbGVzdCBvZiBhbGwgdGhvc2Ugc3RhbmRpbmcgaW4gbGluZTxcL2xpPlxyXG5cdDxsaT5MaW5lIDI6IEEgc2luZ2xlIGJpbmFyeSBpbnRlZ2VyOiB0aGUgY293IGJyYW5kIHdob3NlIG1hZ25pdHVkZSBpcyB0aGUgbGFyZ2VzdCBvZiBhbGwgdGhvc2Ugc3RhbmRpbmcgaW4gbGluZTxcL2xpPlxyXG5cdDxsaT5MaW5lIDM6IEEgc2luZ2xlIGRlY2ltYWwgaW50ZWdlcjogdGhlIHBvc2l0aW9uIGluIHRoZSBsaW5lIHdob3NlIGNvdyBicmFuZCBpcyB0byBiZSByZXBvcnRlZC4gVGhlIGZpcnN0IGNvdyBpbiBsaW5lIGlzIGluIHBvc2l0aW9uIDEuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIGludGVnZXIgdGhhdCBpcyB0aGUgYnJhbmQgb2YgdGhlIGNvdyBzdGFuZGluZyBpbiB0aGUgbGluZSBwb3NpdGlvbiBuYW1lZCBpbiB0aGUgaW5wdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2003-2004 Season > USACO December 2003 Contest > Green 4번

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