Matcom Online Grader
MOG Round #14Ended |
F - Palíndromos otra vez
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Un palíndromo es una cadena que se lee igual de izquierda a derecha que de derecha a izquierda. Por ejemplo, las cadenas "abba" y "madam" son palíndromos pero "ab" no lo es. Para cualquier cadena s vamos a introducir una operación llamada bisección, y se denota por half(s). El valor de half(s) se determina por las siguientes reglas:
I. Si s no es un palíndormo, el valor de half(s) no está determinado.
II. Si la longitud de s es igual a 1, el valor de half(s) tampoco está determinado.
III. Si s es un palíndromo de longitud par igual a 2m, entonces half(s) es la cadena que contiene exactamente los primeros m caracteres de s.
IV. Si s es un palindrome de longitud impar igual a 2m - 1, mayor que 1, entonces half(s) es la cadena que contiene los primeros m caracteres de s.
Por ejemplo, los valores de half("inforamatics") y half ("i") no están definidos, half("abba") = "ab" y half("madam") = "mad".
El grado de palindromicidad de una cadena s es el mayor número de veces que se le puede aplicar la operación de bisección y el resultado es determinado.
Por ejemplo, el grado de palindromicidad de "informatics" y "i" es 0, ya que no es posible applicarles la operación half ni siquiera una vez. Para "abba" y "madam" el valor es 1 y para "totottotot" es 3, ya que se le puede aplicar la operación 3 veces: "totottotot" –> "totot" –> "tot" –> "to".
Considera todas las cadenas de longitud n, que consisten solamente de letras minúsculas y que tienen grado de palindromicidad igual a p. Tu tarea consiste en encontrar la k-ésima de estas cadenas en orden lexicográfico.
Input
La única línea de la entrada contiene tres enteros n (la longitud requerida de la cadena), p (el grado de palindromicidad de la cadena) y k (el número correspondiente de la cadena que se quiere buscar) (1 <= n <= 200, 0 <= p <= 8, 1 <= k <= 10 9 )
Se garantiza que la cadena que se busca siempre existe.
Output
Imprima la k-ésima cadena en orden alfabético del conjunto de cadenas de longitud n y grado de palindromicidad igual a p.