시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 26 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개가 있다.

W3sicHJvYmxlbV9pZCI6IjEyMjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWIyOTAgXHViMGEwIFx1YWNlMFx1YWNlMFx1ZDU1OVx1Yzc5MCBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViYmY4XHVjOWMwXHVjNzU4IFx1YzEzOFx1YWNjNFx1YzVkMFx1YzExYyBcdWMyZTBcdWJlNDRcdWQ1NWMgXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjY1x1Yzc0NCBcdWNjM2VcdWM1NThcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWFkZjggXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjY1x1YzVkMFx1YjI5NCBYXHVjNjQwIElcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWMwYzhcdWFjYThcdWM4MzggXHVjNzg4XHVjNWM4XHViMmU0LiZuYnNwO1x1YWRmOFx1Yjc5OFx1YzExYywgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2NcdWM3NDQgXHViZDg0XHViOTU4XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWFlMzBcdWM5MDBcdWM3NDQgXHVjMTM4XHVjNmUwXHViMmU0LjxcL3A+XHJcblxyXG48cD4mcXVvdDtuLWstXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjYyZxdW90O1x1Yzc3NFx1Yjc4MCBYXHVjNjQwIElcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1ZDU2OVx1ZDU3NFx1YzExYyBuXHVhYzFjXHVjNzc0XHVhY2UwIFhcdWM2NDAgSVx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NCBrXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc3OCBcdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjhcdWI5YWNcdWFjZTAgXHVjNWI0XHViNWE0IFx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2NcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YjU0YyBcdWFkZjggXHViM2NjXHVjNzQ0IDE4MFx1YjNjNCBcdWQ2OGNcdWM4MDRcdWQ1NzRcdWMxMWMgXHViMDk4XHVjNjI4IFx1YjNjY1x1YjNjNCBcdWFjMTlcdWM3NDAgXHViM2NjXHVjNzNjXHViODVjIFx1YmNmNFx1YjI5NFx1YjM3MCBcdWFkZjggMlx1YWMxY1x1Yzc1OCBcdWIzY2MmbmJzcDtcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzExY1x1YjI5NCBcdWIzY2NcdWI5Y2MgXHVhY2UwXHViODI0XHVkNTVjXHViMmU0LihcdWM2MDhcdWI5N2MgXHViNGU0XHViYTc0IElYWElJWFhYXHVjNjQwIFhYWElJWFhJXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMgSVhYSUlYWFhcdWI5Y2MgXHVjNGYwXHVjNzc4XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjICZxdW90O24tay1cdWI5YzhcdWJjOTVcdWM3NTggXHViM2NjJnF1b3Q7XHVjNzQ0IFx1YzBhY1x1YzgwNFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1ODhcdWIyZTRcdWFjZTAgXHVkNTYwIFx1YjU0YyBcdWFkZjggXHVjOTExIGlcdWJjODhcdWM5ZjggJnF1b3Q7bi1rLVx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2MmcXVvdDtcdWM3NDQgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzkwNFx1YzVkMCBuLCBrLCBpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAmbHQ7PWsmbHQ7biZsdDs9NjAsIDAmbHQ7aSZsdDsxMF4xOCk8XC9wPlxyXG5cclxuXHJcbiIsIm91dHB1dCI6IjxwPmlcdWJjODhcdWM5ZjggJnF1b3Q7bi1rLVx1YjljOFx1YmM5NVx1Yzc1OCBcdWIzY2MmcXVvdDtcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0IFx1YWRmOFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAgXHVjNWM2XHViMmU0XHViYTc0IE5PIFNVQ0ggU1RPTkVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4zLTItXHViOWM4XHViYzk1XHVjNzU4IFx1YjNjY1x1Yzc0MCBJSUksIElJWCwgSVhJLCBJWFgsIFhJWCwgWFhYIFx1Yzc3NFx1YjgwN1x1YWM4YyA2XHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyMjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYWdpY2FsIHN0b25lcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFtb3VzIHN0b25lcyBYaS1uLWsgY2FuIG9ubHkgYmUgZm91bmQgaW4gV29uZGVybGFuZC4gU3VjaCBhIHN0b25lIGlzIHNpbXBseSBhIGdyYW5pdGUgYm9hcmQgd2l0aCBhbiBpbnNjcmlwdGlvbiBjb25zaXN0aW5nIG9ubHkgb2YgbGV0dGVycyBYIGFuZCBJLiBFYWNoIGJvYXJkIGNvbnRhaW5zIGV4YWN0bHkgbiBsZXR0ZXJzLiBUaGVyZSBhcmUgbm90IG1vcmUgdGhhbiBrIHBvc2l0aW9ucyBpbiBlYWNoIGJvYXJkIHdoZXJlIGxldHRlcnMgWCBhbmQgSSBhcmUgbmV4dCB0byBlYWNoIG90aGVyLjxcL3A+XHJcblxyXG48cD5UaGUgdG9wIGFuZCBib3R0b20gc2lkZXMgb2YgdGhlIHN0b25lcyBhcmUgbm90IFx1ZmIwMXhlZCwgc28gdGhlIHN0b25lcyBjYW4gYmUgcm90YXRlZCB1cHNpZGUtZG93bi4gRm9yIGluc3RhbmNlIHR3byBcdWZiMDFndXJlcyBiZWxvdyBkZXBpY3QgZXhhY3RseSB0aGUgc2FtZSBzdG9uZTo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tc3RvbmUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzJweDsgd2lkdGg6MjAxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlnLiAxOiBUd28gd2F5cyBvZiBsb29raW5nIGF0IHRoZSBzYW1lIHN0b25lLiBUaGlzIHN0b25lIGlzIG9mIHR5cGUgWGktOC0zLCBidXQgYWxzbyBYaS04LTQgKGFuZCBhbHNvIG9mIGFueSB0eXBlIFhpLTgtayBmb3IgayAmZ2U7IDMpLjxcL3A+XHJcblxyXG48cD5ObyB0d28gbWFnaWMgc3RvbmVzIGluIFdvbmRlcmxhbmQgYXJlIHRoZSBzYW1lLCBpLmUuIG5vIHR3byBzdG9uZXMgY29udGFpbiB0aGUgc2FtZSBpbnNjcmlwdGlvbiAocmVtZW1iZXIgdGhhdCB0aGUgdXBzaWRlLWRvd24gcm90YXRpb24gb2YgYSBzdG9uZSBpcyBhbGxvd2VkKS48XC9wPlxyXG5cclxuPHA+SWYgaXQgaXMgcG9zc2libGUgdG8gcmVhZCB0aGUgaW5zY3JpcHRpb24gb2Ygc29tZSBzdG9uZSBpbiB0d28gZGlcdWZiMDBlcmVudCB3YXlzICh1c2luZyB0aGUgdXBzaWRlLWRvd24gcm90YXRpb24pIHRoZW4gdGhlIGNhbm9uaWNhbCByZXByZXNlbnRhdGlvbiBvZiB0aGUgc3RvbmUgaXMgZGVcdWZiMDFuZWQgYXMgdGhlIGxleGljb2dyYXBoaWNhbGx5IGxlc3MxIG9mIHRoZXNlIHR3byB3YXlzIG9mIHJlYWRpbmcgdGhlIGluc2NyaXB0aW9uLjxcL3A+XHJcblxyXG48cD5JZiBhIHN0b25lJnJzcXVvO3MgaW5zY3JpcHRpb24gaXMgc3ltbWV0cmljYWwsIGkuZS4gdGhlIHVwc2lkZS1kb3duIHJvdGF0aW9uIGRvZXMgbm90IGNoYW5nZSBpdCwgdGhlbiBpdHMgY2Fub25pY2FsIHJlcHJlc2VudGF0aW9uIGlzIGRlXHVmYjAxbmVkIGFzIHRoZSB1bmlxdWUgd2F5IG9mIHJlYWRpbmcgdGhpcyBpbnNjcmlwdGlvbi48XC9wPlxyXG5cclxuPHA+RXhhbXBsZTogVGhlcmUgYXJlIGV4YWN0bHkgNiBzdG9uZXMgb2YgdHlwZSBYaS0zLTIuIFRoZWlyIGNhbm9uaWNhbCByZXByZXNlbnRhdGlvbnMgd3JpdHRlbiBpbiBsZXhpY29ncmFwaGljYWwgb3JkZXIgYXJlOiBJSUksIElJWCwgSVhJLCBJWFgsIFhJWCBhbmQgWFhYLjxcL3A+XHJcblxyXG48cD5BbGljZSBpcyBhIHdlbGwta25vd24gZXhwZXJ0IG9uIHRoZSBYaS1uLWsgc3RvbmVzIGZyb20gV29uZGVybGFuZC4gU2hlIHdvdWxkIGxpa2UgdG8gY3JlYXRlIGEgbGV4aWNvZ3JhcGhpY2FsIGluZGV4IG9mIHRoZSBjYW5vbmljYWwgcmVwcmVzZW50YXRpb25zIG9mIGFsbCBzdG9uZXMgb2YgdHlwZSBYaS1uLWsgKGZvciBzb21lIHNwZWNpXHVmYjAxYyB2YWx1ZXMgb2YgbiBhbmQgaykuIFdoYXQgaW5zY3JpcHRpb24gc2hvdWxkIGJlIHdyaXR0ZW4gYXQgcG9zaXRpb24gaSBvZiB0aGUgaW5kZXgsIGZvciBhIGdpdmVuIHZhbHVlIG9mIGk/PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbW1lIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIG51bWJlcnMgbiwgayBhbmQgaSBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+ZGV0ZXJtaW5lcyB0aGUgaS10aCAoaW4gdGhlIGxleGljb2dyYXBoaWNhbCBvcmRlcikgY2Fub25pY2FsIHJlcHJlc2VudGF0aW9uIG9mIGEgWGktbi1rIHN0b25lLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIHRocmVlIGludGVnZXJzIG4sIGsgYW5kIGkgKDAgJmxlOyBrICZsdDsgbiAmbGU7IDYwLCAwICZsdDsgaSAmbHQ7IDEwPHN1cD4xODxcL3N1cD4pIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBpLXRoIChpbiB0aGUgbGV4aWNvZ3JhcGhpY2FsIG9yZGVyKSBjYW5vbmljYWwgcmVwcmVzZW50YXRpb24gb2YgYSBYaS1uLWsgc3RvbmUuPFwvcD5cclxuXHJcbjxwPklmIHRoZSBudW1iZXIgb2YgWGktbi1rIHN0b25lcyBpcyBsZXNzIHRoYW4gaSB0aGVuIHRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gZXhwcmVzc2lvbiBOTyBTVUNIIFNUT05FLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 7번

  • 문제를 번역한 사람: author4