시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 21 2 2 12.500%

문제

어느날 고고학자 선영이는 미지의 세계에서 신비한 마법의 돌을 찾았다. 그런데 그 마법의 돌에는 X와 I로 이루어진 문자열이 새겨져 있었다. 그래서, 선영이는 마법의 돌을 분류하기 위한 기준을 세웠다.

"n-k-마법의 돌"이란 X와 I의 개수가 합해서 n개이고 X와 I가 붙어 있는 부분이 k개 이하인 마법의 돌이다.

그리고 어떤 마법의 돌이 있을 때 그 돌을 180도 회전해서 나온 돌도 같은 돌으로 보는데 그 2개의 돌 중에서 사전순으로 앞서는 돌만 고려한다.(예를 들면 IXXIIXXX와 XXXIIXXI가 있을 때 IXXIIXXX만 쓰인다.)

이때 "n-k-마법의 돌"을 사전순으로 정렬했다고 할 때 그 중 i번째 "n-k-마법의 돌"을 알고 싶다.

입력

첫줄에 n, k, i가 주어진다. (0<=k<n<=60, 0<i<10^18)

출력

i번째 "n-k-마법의 돌"이 있다면 그것을 출력하고 없다면 NO SUCH STONE을 출력한다.

예제 입력 1

3 2 5

예제 출력 1

XIX

힌트

3-2-마법의 돌은 III, IIX, IXI, IXX, XIX, XXX 이렇게 6개가 있다.

W3sicHJvYmxlbV9pZCI6IjEyMjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWIyOTBcdWIwYTAgXHVhY2UwXHVhY2UwXHVkNTU5XHVjNzkwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWJiZjhcdWM5YzBcdWM3NTggXHVjMTM4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YzJlMFx1YmU0NFx1ZDU1YyBcdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjXHVjNzQ0IFx1Y2MzZVx1YzU1OFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YWRmOCBcdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjXHVjNWQwXHViMjk0IFhcdWM2NDAgSVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzBjOFx1YWNhOFx1YzgzOCBcdWM3ODhcdWM1YzhcdWIyZTQuJm5ic3A7XHVhZGY4XHViNzk4XHVjMTFjLCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjY1x1Yzc0NCBcdWJkODRcdWI5NThcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YWUzMFx1YzkwMFx1Yzc0NCBcdWMxMzhcdWM2ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZxdW90O24tay1cdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjJnF1b3Q7XHVjNzc0XHViNzgwIFhcdWM2NDAgSVx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVkNTY5XHVkNTc0XHVjMTFjIG5cdWFjMWNcdWM3NzRcdWFjZTAgWFx1YzY0MCBJXHVhYzAwIFx1YmQ5OVx1YzViNCBcdWM3ODhcdWIyOTQgXHViZDgwXHViZDg0XHVjNzc0IGtcdWFjMWMgXHVjNzc0XHVkNTU4XHVjNzc4IFx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2NcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWM1YjRcdWI1YTQgXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjY1x1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjIFx1YWRmOCBcdWIzY2NcdWM3NDQgMTgwXHViM2M0IFx1ZDY4Y1x1YzgwNFx1ZDU3NFx1YzExYyBcdWIwOThcdWM2MjggXHViM2NjXHViM2M0IFx1YWMxOVx1Yzc0MCBcdWIzY2NcdWM3M2NcdWI4NWMgXHViY2Y0XHViMjk0XHViMzcwIFx1YWRmOCAyXHVhYzFjXHVjNzU4IFx1YjNjYyZuYnNwO1x1YzkxMVx1YzVkMFx1YzExYyBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjNTVlXHVjMTFjXHViMjk0IFx1YjNjY1x1YjljYyBcdWFjZTBcdWI4MjRcdWQ1NWNcdWIyZTQuKFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgSVhYSUlYWFhcdWM2NDAgWFhYSUlYWElcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0YyBJWFhJSVhYWFx1YjljYyBcdWM0ZjBcdWM3NzhcdWIyZTQuKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMgJnF1b3Q7bi1rLVx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2MmcXVvdDtcdWM3NDQgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU4OFx1YjJlNFx1YWNlMCBcdWQ1NjAgXHViNTRjIFx1YWRmOCBcdWM5MTEgaVx1YmM4OFx1YzlmOCAmcXVvdDtuLWstXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjYyZxdW90O1x1Yzc0NCBcdWM1NGNcdWFjZTAgXHVjMmY2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOTA0XHVjNWQwIG4sIGssIGlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCZsdDs9ayZsdDtuJmx0Oz02MCwgMCZsdDtpJmx0OzEwXjE4KTxcL3A+XHJcblxyXG5cclxuIiwib3V0cHV0IjoiPHA+aVx1YmM4OFx1YzlmOCAmcXVvdDtuLWstXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjYyZxdW90O1x1Yzc3NCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4XHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCBcdWM1YzZcdWIyZTRcdWJhNzQgTk8gU1VDSCBTVE9ORVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjMtMi1cdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjXHVjNzQwIElJSSwgSUlYLCBJWEksIElYWCwgWElYLCBYWFggXHVjNzc0XHViODA3XHVhYzhjIDZcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTIyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1hZ2ljYWwgc3RvbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5GYW1vdXMgc3RvbmVzIFhpLW4tayBjYW4gb25seSBiZSBmb3VuZCBpbiBXb25kZXJsYW5kLiBTdWNoIGEgc3RvbmUgaXMgc2ltcGx5IGEgZ3Jhbml0ZSBib2FyZCB3aXRoIGFuIGluc2NyaXB0aW9uIGNvbnNpc3Rpbmcgb25seSBvZiBsZXR0ZXJzIFggYW5kIEkuIEVhY2ggYm9hcmQgY29udGFpbnMgZXhhY3RseSBuIGxldHRlcnMuIFRoZXJlIGFyZSBub3QgbW9yZSB0aGFuIGsgcG9zaXRpb25zIGluIGVhY2ggYm9hcmQgd2hlcmUgbGV0dGVycyBYIGFuZCBJIGFyZSBuZXh0IHRvIGVhY2ggb3RoZXIuPFwvcD5cclxuXHJcbjxwPlRoZSB0b3AgYW5kIGJvdHRvbSBzaWRlcyBvZiB0aGUgc3RvbmVzIGFyZSBub3QgXHVmYjAxeGVkLCBzbyB0aGUgc3RvbmVzIGNhbiBiZSByb3RhdGVkIHVwc2lkZS1kb3duLiBGb3IgaW5zdGFuY2UgdHdvIFx1ZmIwMWd1cmVzIGJlbG93IGRlcGljdCBleGFjdGx5IHRoZSBzYW1lIHN0b25lOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21zdG9uZS5wbmdcIiBzdHlsZT1cImhlaWdodDozMnB4OyB3aWR0aDoyMDFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWcuIDE6IFR3byB3YXlzIG9mIGxvb2tpbmcgYXQgdGhlIHNhbWUgc3RvbmUuIFRoaXMgc3RvbmUgaXMgb2YgdHlwZSBYaS04LTMsIGJ1dCBhbHNvIFhpLTgtNCAoYW5kIGFsc28gb2YgYW55IHR5cGUgWGktOC1rIGZvciBrICZnZTsgMykuPFwvcD5cclxuXHJcbjxwPk5vIHR3byBtYWdpYyBzdG9uZXMgaW4gV29uZGVybGFuZCBhcmUgdGhlIHNhbWUsIGkuZS4gbm8gdHdvIHN0b25lcyBjb250YWluIHRoZSBzYW1lIGluc2NyaXB0aW9uIChyZW1lbWJlciB0aGF0IHRoZSB1cHNpZGUtZG93biByb3RhdGlvbiBvZiBhIHN0b25lIGlzIGFsbG93ZWQpLjxcL3A+XHJcblxyXG48cD5JZiBpdCBpcyBwb3NzaWJsZSB0byByZWFkIHRoZSBpbnNjcmlwdGlvbiBvZiBzb21lIHN0b25lIGluIHR3byBkaVx1ZmIwMGVyZW50IHdheXMgKHVzaW5nIHRoZSB1cHNpZGUtZG93biByb3RhdGlvbikgdGhlbiB0aGUgY2Fub25pY2FsIHJlcHJlc2VudGF0aW9uIG9mIHRoZSBzdG9uZSBpcyBkZVx1ZmIwMW5lZCBhcyB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgbGVzczEgb2YgdGhlc2UgdHdvIHdheXMgb2YgcmVhZGluZyB0aGUgaW5zY3JpcHRpb24uPFwvcD5cclxuXHJcbjxwPklmIGEgc3RvbmUmcnNxdW87cyBpbnNjcmlwdGlvbiBpcyBzeW1tZXRyaWNhbCwgaS5lLiB0aGUgdXBzaWRlLWRvd24gcm90YXRpb24gZG9lcyBub3QgY2hhbmdlIGl0LCB0aGVuIGl0cyBjYW5vbmljYWwgcmVwcmVzZW50YXRpb24gaXMgZGVcdWZiMDFuZWQgYXMgdGhlIHVuaXF1ZSB3YXkgb2YgcmVhZGluZyB0aGlzIGluc2NyaXB0aW9uLjxcL3A+XHJcblxyXG48cD5FeGFtcGxlOiBUaGVyZSBhcmUgZXhhY3RseSA2IHN0b25lcyBvZiB0eXBlIFhpLTMtMi4gVGhlaXIgY2Fub25pY2FsIHJlcHJlc2VudGF0aW9ucyB3cml0dGVuIGluIGxleGljb2dyYXBoaWNhbCBvcmRlciBhcmU6IElJSSwgSUlYLCBJWEksIElYWCwgWElYIGFuZCBYWFguPFwvcD5cclxuXHJcbjxwPkFsaWNlIGlzIGEgd2VsbC1rbm93biBleHBlcnQgb24gdGhlIFhpLW4tayBzdG9uZXMgZnJvbSBXb25kZXJsYW5kLiBTaGUgd291bGQgbGlrZSB0byBjcmVhdGUgYSBsZXhpY29ncmFwaGljYWwgaW5kZXggb2YgdGhlIGNhbm9uaWNhbCByZXByZXNlbnRhdGlvbnMgb2YgYWxsIHN0b25lcyBvZiB0eXBlIFhpLW4tayAoZm9yIHNvbWUgc3BlY2lcdWZiMDFjIHZhbHVlcyBvZiBuIGFuZCBrKS4gV2hhdCBpbnNjcmlwdGlvbiBzaG91bGQgYmUgd3JpdHRlbiBhdCBwb3NpdGlvbiBpIG9mIHRoZSBpbmRleCwgZm9yIGEgZ2l2ZW4gdmFsdWUgb2YgaT88XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtbWUgd2hpY2g6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgbnVtYmVycyBuLCBrIGFuZCBpIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LDxcL2xpPlxyXG5cdDxsaT5kZXRlcm1pbmVzIHRoZSBpLXRoIChpbiB0aGUgbGV4aWNvZ3JhcGhpY2FsIG9yZGVyKSBjYW5vbmljYWwgcmVwcmVzZW50YXRpb24gb2YgYSBYaS1uLWsgc3RvbmUsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgbiwgayBhbmQgaSAoMCAmbGU7IGsgJmx0OyBuICZsZTsgNjAsIDAgJmx0OyBpICZsdDsgMTA8c3VwPjE4PFwvc3VwPikgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGktdGggKGluIHRoZSBsZXhpY29ncmFwaGljYWwgb3JkZXIpIGNhbm9uaWNhbCByZXByZXNlbnRhdGlvbiBvZiBhIFhpLW4tayBzdG9uZS48XC9wPlxyXG5cclxuPHA+SWYgdGhlIG51bWJlciBvZiBYaS1uLWsgc3RvbmVzIGlzIGxlc3MgdGhhbiBpIHRoZW4gdGhlIFx1ZmIwMXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBleHByZXNzaW9uIE5PIFNVQ0ggU1RPTkUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 7번

  • 문제를 번역한 사람: author4