UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1310. [Baltic2008]Magic Stone

统计 下载数据

Description

给定某个字符串,长度为N,它只由"I"和"X"组成.并且有不超过K对"I"与"X"是相邻的. 例如对于字符串"IXXIIXXX",它就是XI-8-3,即长度为8,"I"与"X"相邻的对数不超过3. 当然你要说它是XI-8-4也行,甚至于XI-8-K(K>=3).值得注意的是:由于字符串的首尾不 固定,"IXXIIXXX"也可以看成"XXXIIXXI",但由于每个字符串只有一个序号,因而我们对 这种由于颠倒首尾所产生的字符串,取两者之中字典序较小的那个为基准,当然如果一个 字符串它是回文串的话,那就无所谓了. 现在给定N,K的值,我们可以找到许多满足条件的字符串,现在希望能找出排在第i个的是 哪个字符串,例如N=3,K=2,i=5时,我们可以按字典序找出如下的字符串:"III", "IIX", "IXI", "IXX", "XIX","XXX".那么排在第5个位置的为"XIX"

Input

每行给定N,K,i,含义如上所述 规定:0<=K

Output

希望你能找出相应的字符串,如果找不出来就输出"NO SUCH STONE" input data1: 3 2 5 input data2: 3 2 7

Sample Input

output data1:
XIX

output data2:
NO SUCH STONE

Sample Output

Hint

0 <= k < n<= 60 0 < i < 10^18


题解:JudgeOnline/upload/201603/dsyoj1310《Magical stones》解题报告.rar

Source