Magic Stone
Time limit2sMemory limit128 MB
Given n, k, and i, find the i-th lexicographically smallest length-n I/X string with at most k differing adjacent pairs, treating a string and its reverse as identical.
- Level
Hard8 of 10
- Topics
- Combinatorics, Dynamic programming, Math, String
- Solved
- No attempts yet
Problem
Archaeologist Seonyeong found a mysterious magic stone in an unknown world. A string made only of the characters I and X is engraved on the stone.
For given n and k, an n-k magic stone is a stone whose string has length n and has at most k adjacent pairs whose two characters are different. In other words, count the positions j where the j-th and (j+1)-st characters are one I and one X; this count must be at most k.
Rotating a stone by 180 degrees reverses the string, and the rotated stone is considered the same stone. Therefore, for each pair of a string and its reverse, only the lexicographically smaller string is considered. The character I comes before X.
After all n-k magic stones are sorted in lexicographic order, find the i-th stone.
Input
The first line contains n, k, and i (0 <= k < n <= 60, 0 < i < 10^18).
Output
If the i-th n-k magic stone exists, print it. Otherwise, print NO SUCH STONE.
Hint
The 3-2 magic stones are III, IIX, IXI, IXX, XIX, and XXX, for a total of 6 stones.