시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 9 1 1 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을 출력한다.

예제 입력

3 2 5

예제 출력

XIX

힌트

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

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 7번

  • 문제를 번역한 사람: author4