시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB1562212.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 < 1018)

출력

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

예제 입력 1

3 2 5

예제 출력 1

XIX

예제 입력 2

3 2 7

예제 출력 2

NO SUCH STONE

힌트

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

W3sicHJvYmxlbV9pZCI6IjEyMjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWIyOTAgXHViMGEwIFx1YWNlMFx1YWNlMFx1ZDU1OVx1Yzc5MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViYmY4XHVjOWMwXHVjNzU4IFx1YzEzOFx1YWNjNFx1YzVkMFx1YzExYyBcdWMyZTBcdWJlNDRcdWQ1NWMgXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjY1x1Yzc0NCBcdWNjM2VcdWM1NThcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWFkZjggXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjY1x1YzVkMFx1YjI5NCBYXHVjNjQwIElcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWMwYzhcdWFjYThcdWM4MzggXHVjNzg4XHVjNWM4XHViMmU0LiZuYnNwO1x1YWRmOFx1Yjc5OFx1YzExYywgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2NcdWM3NDQgXHViZDg0XHViOTU4XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWFlMzBcdWM5MDBcdWM3NDQgXHVjMTM4XHVjNmUwXHViMmU0LjxcL3A+XHJcblxyXG48cD4mcXVvdDtuLWstXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjYyZxdW90O1x1Yzc3NFx1Yjc4MCBYXHVjNjQwIElcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1ZDU2OVx1ZDU3NFx1YzExYyBuXHVhYzFjXHVjNzc0XHVhY2UwIFhcdWM2NDAgSVx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NCBrXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc3OCBcdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHVjNWI0XHViNWE0IFx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2NcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWFkZjggXHViM2NjXHVjNzQ0IDE4MFx1YjNjNCBcdWQ2OGNcdWM4MDRcdWQ1NzRcdWMxMWMgXHViMDk4XHVjNjI4IFx1YjNjY1x1YjNjNCBcdWFjMTlcdWM3NDAgXHViM2NjXHVjNzNjXHViODVjIFx1YmNmNFx1YjI5NFx1YjM3MCBcdWFkZjggMlx1YWMxY1x1Yzc1OCBcdWIzY2MmbmJzcDtcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzExY1x1YjI5NCBcdWIzY2NcdWI5Y2MgXHVhY2UwXHViODI0XHVkNTVjXHViMmU0LihcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0IElYWElJWFhYXHVjNjQwIFhYWElJWFhJXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMgSVhYSUlYWFhcdWI5Y2MgXHVjNGYwXHVjNzc4XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjICZxdW90O24tay1cdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjJnF1b3Q7XHVjNzQ0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1ODhcdWIyZTRcdWFjZTAgXHVkNTYwIFx1YjU0YyBcdWFkZjggXHVjOTExIGlcdWJjODhcdWM5ZjggJnF1b3Q7bi1rLVx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2MmcXVvdDtcdWM3NDQgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzkwNFx1YzVkMCBuLCBrLCBpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBrICZsdDsgbiAmbGU7IDYwLCAwICZsdDsgaSAmbHQ7IDEwPHN1cD4xODxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+aVx1YmM4OFx1YzlmOCAmcXVvdDtuLWstXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjYyZxdW90O1x1Yzc3NCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4XHVhYzgzXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCBcdWM1YzZcdWIyZTRcdWJhNzQgTk8gU1VDSCBTVE9ORVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjMtMi1cdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjXHVjNzQwIElJSSwgSUlYLCBJWEksIElYWCwgWElYLCBYWFggXHVjNzc0XHViODA3XHVhYzhjIDZcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTIyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1hZ2ljYWwgc3RvbmVzIiwiZGVzY3JpcHRpb24iOiI8cD5GYW1vdXMgc3RvbmVzIFhpLW4tayBjYW4gb25seSBiZSBmb3VuZCBpbiBXb25kZXJsYW5kLiBTdWNoIGEgc3RvbmUgaXMgc2ltcGx5IGEgZ3Jhbml0ZSBib2FyZCB3aXRoIGFuIGluc2NyaXB0aW9uIGNvbnNpc3Rpbmcgb25seSBvZiBsZXR0ZXJzIFggYW5kIEkuIEVhY2ggYm9hcmQgY29udGFpbnMgZXhhY3RseSBuIGxldHRlcnMuIFRoZXJlIGFyZSBub3QgbW9yZSB0aGFuIGsgcG9zaXRpb25zIGluIGVhY2ggYm9hcmQgd2hlcmUgbGV0dGVycyBYIGFuZCBJIGFyZSBuZXh0IHRvIGVhY2ggb3RoZXIuPFwvcD5cclxuXHJcbjxwPlRoZSB0b3AgYW5kIGJvdHRvbSBzaWRlcyBvZiB0aGUgc3RvbmVzIGFyZSBub3QgXHVmYjAxeGVkLCBzbyB0aGUgc3RvbmVzIGNhbiBiZSByb3RhdGVkIHVwc2lkZS1kb3duLiBGb3IgaW5zdGFuY2UgdHdvIFx1ZmIwMWd1cmVzIGJlbG93IGRlcGljdCBleGFjdGx5IHRoZSBzYW1lIHN0b25lOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48Y29kZT5JWFhJSVhYWDxcL2NvZGU+Jm5ic3A7PGNvZGU+WFhYSUlYWEk8XC9jb2RlPjxcL3A+XHJcblxyXG48cD5GaWcuIDE6IFR3byB3YXlzIG9mIGxvb2tpbmcgYXQgdGhlIHNhbWUgc3RvbmUuIFRoaXMgc3RvbmUgaXMgb2YgdHlwZSBYaS04LTMsIGJ1dCBhbHNvIFhpLTgtNCAoYW5kIGFsc28gb2YgYW55IHR5cGUgWGktOC1rIGZvciBrICZnZTsgMykuPFwvcD5cclxuXHJcbjxwPk5vIHR3byBtYWdpYyBzdG9uZXMgaW4gV29uZGVybGFuZCBhcmUgdGhlIHNhbWUsIGkuZS4gbm8gdHdvIHN0b25lcyBjb250YWluIHRoZSBzYW1lIGluc2NyaXB0aW9uIChyZW1lbWJlciB0aGF0IHRoZSB1cHNpZGUtZG93biByb3RhdGlvbiBvZiBhIHN0b25lIGlzIGFsbG93ZWQpLjxcL3A+XHJcblxyXG48cD5JZiBpdCBpcyBwb3NzaWJsZSB0byByZWFkIHRoZSBpbnNjcmlwdGlvbiBvZiBzb21lIHN0b25lIGluIHR3byBkaVx1ZmIwMGVyZW50IHdheXMgKHVzaW5nIHRoZSB1cHNpZGUtZG93biByb3RhdGlvbikgdGhlbiB0aGUgY2Fub25pY2FsIHJlcHJlc2VudGF0aW9uIG9mIHRoZSBzdG9uZSBpcyBkZVx1ZmIwMW5lZCBhcyB0aGUgbGV4aWNvZ3JhcGhpY2FsbHkgbGVzczEgb2YgdGhlc2UgdHdvIHdheXMgb2YgcmVhZGluZyB0aGUgaW5zY3JpcHRpb24uPFwvcD5cclxuXHJcbjxwPklmIGEgc3RvbmUmcnNxdW87cyBpbnNjcmlwdGlvbiBpcyBzeW1tZXRyaWNhbCwgaS5lLiB0aGUgdXBzaWRlLWRvd24gcm90YXRpb24gZG9lcyBub3QgY2hhbmdlIGl0LCB0aGVuIGl0cyBjYW5vbmljYWwgcmVwcmVzZW50YXRpb24gaXMgZGVcdWZiMDFuZWQgYXMgdGhlIHVuaXF1ZSB3YXkgb2YgcmVhZGluZyB0aGlzIGluc2NyaXB0aW9uLjxcL3A+XHJcblxyXG48cD5FeGFtcGxlOiBUaGVyZSBhcmUgZXhhY3RseSA2IHN0b25lcyBvZiB0eXBlIFhpLTMtMi4gVGhlaXIgY2Fub25pY2FsIHJlcHJlc2VudGF0aW9ucyB3cml0dGVuIGluIGxleGljb2dyYXBoaWNhbCBvcmRlciBhcmU6IDxjb2RlPklJSTxcL2NvZGU+LCA8Y29kZT5JSVg8XC9jb2RlPiwgPGNvZGU+SVhJPFwvY29kZT4sIDxjb2RlPklYWDxcL2NvZGU+LCA8Y29kZT5YSVg8XC9jb2RlPiBhbmQgPGNvZGU+WFhYPFwvY29kZT4uPFwvcD5cclxuXHJcbjxwPkFsaWNlIGlzIGEgd2VsbC1rbm93biBleHBlcnQgb24gdGhlIFhpLW4tayBzdG9uZXMgZnJvbSBXb25kZXJsYW5kLiBTaGUgd291bGQgbGlrZSB0byBjcmVhdGUgYSBsZXhpY29ncmFwaGljYWwgaW5kZXggb2YgdGhlIGNhbm9uaWNhbCByZXByZXNlbnRhdGlvbnMgb2YgYWxsIHN0b25lcyBvZiB0eXBlIFhpLW4tayAoZm9yIHNvbWUgc3BlY2lcdWZiMDFjIHZhbHVlcyBvZiBuIGFuZCBrKS4gV2hhdCBpbnNjcmlwdGlvbiBzaG91bGQgYmUgd3JpdHRlbiBhdCBwb3NpdGlvbiBpIG9mIHRoZSBpbmRleCwgZm9yIGEgZ2l2ZW4gdmFsdWUgb2YgaT88XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtJm5ic3A7d2hpY2g6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgbnVtYmVycyBuLCBrIGFuZCBpIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LDxcL2xpPlxyXG5cdDxsaT5kZXRlcm1pbmVzIHRoZSBpLXRoIChpbiB0aGUgbGV4aWNvZ3JhcGhpY2FsIG9yZGVyKSBjYW5vbmljYWwgcmVwcmVzZW50YXRpb24gb2YgYSBYaS1uLWsgc3RvbmUsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgbiwgayBhbmQgaSAoMCAmbGU7IGsgJmx0OyBuICZsZTsgNjAsIDAgJmx0OyBpICZsdDsgMTA8c3VwPjE4PFwvc3VwPikgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBzdGFuZGFyZCBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGktdGggKGluIHRoZSBsZXhpY29ncmFwaGljYWwgb3JkZXIpIGNhbm9uaWNhbCByZXByZXNlbnRhdGlvbiBvZiBhIFhpLW4tayBzdG9uZS48XC9wPlxyXG5cclxuPHA+SWYgdGhlIG51bWJlciBvZiBYaS1uLWsgc3RvbmVzIGlzIGxlc3MgdGhhbiBpIHRoZW4gdGhlIFx1ZmIwMXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBleHByZXNzaW9uIDxjb2RlPk5PIFNVQ0ggU1RPTkU8XC9jb2RlPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 3번

  • 문제를 번역한 사람: author4