QOJ.ac

QOJ

시간 제한: 1 s 메모리 제한: 32 MB 총점: 100

#16938. Magical stones

통계

著名的 Xi-n-k 石头只能在奇境(Wonderland)中找到。这样的一块石头实际上是一块花岗岩板,上面刻有仅由字母 XI 组成的铭文。每块板上恰好有 $n$ 个字母。在每块板中,字母 XI 相邻的位置不超过 $k$ 处。

石头的上下两面没有固定,因此石头可以颠倒旋转(即首尾翻转)。例如,下面两幅图描绘的是完全相同的石头:

IXXIIXXX XXXIIXXI

图 1:看同一块石头的两种方式。这块石头的类型是 Xi-8-3,但也是 Xi-8-4(以及任何 $k \ge 3$ 的 Xi-8-k 类型)。

奇境中没有两块魔法石头是相同的,也就是说,没有两块石头包含相同的铭文(请记住,石头允许颠倒旋转)。

如果可以通过两种不同的方式(利用颠倒旋转)来读取某块石头的铭文,那么该石头的标准表示(canonical representation)定义为这两种读取方式中字典序较小*的那一个。

如果一块石头的铭文是对称的,即颠倒旋转不会改变它,那么它的标准表示就定义为读取该铭文的唯一方式。

* 我们称铭文 $A$ 在字典序上小于 $B$(假设 $A$ 和 $B$ 长度相同),如果在它们第一个不同的位置上,$A$ 包含字母 I 且 $B$ 包含字母 X

示例:恰好有 6 块类型为 Xi-3-2 的石头。按字典序排列,它们的标准表示依次为:IIIIIXIXIIXXXIXXXX

爱丽丝是奇境中 Xi-n-k 石头方面的著名专家。她想为所有类型为 Xi-n-k 的石头(对于给定的 $n$ 和 $k$)的标准表示建立一个字典序索引。

对于给定的 $i$ 值,索引中第 $i$ 个位置应该写什么铭文?

请编写一个程序:

  • 从标准输入读取数字 $n$,$k$ 和 $i$,
  • 确定类型为 Xi-n-k 的石头按字典序排列的第 $i$ 个标准表示,
  • 将结果写入标准输出。

输入格式

输入只有一行,包含三个整数 $n$,$k$ 和 $i$($0 \le k < n \le 60$,$0 < i < 10^{18}$),它们之间用单个空格分隔。

输出格式

输出只有一行,包含类型为 Xi-n-k 的石头按字典序排列的第 $i$ 个标准表示。

如果 Xi-n-k 石头的数量少于 $i$,则输出唯一的一行应包含 NO SUCH STONE

样例

输入样例 1

3 2 5

输出样例 1

XIX

输入样例 2

3 2 7

输出样例 2

NO SUCH STONE

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.