MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

ACM 2014 - Round #3

Ended

D - Puzzle

Languages: C, C++, Java, Tiger, Python, Pascal, JavaScript, Haskell, C#
Time & Memory limits: (details)

Los rompecabezas son el juego favorito de los habitantes de IslaGrande. El puzzle de moda en estos días utiliza una palabra formada solamente por las letras del alfabeto inglés. Inicialmente, todas las letras se mezclan y se colocan en un orden determinado de manera lineal. Las posiciones están numeradas de izquierda a derecha, comenzando con 1.

Si una letra es escogida como pivote, se obtienen dos grupos: el Grupo 1 el cual consta de todas las letras ubicadas a la izquierda del pivote, incluyendo a este, mientras que el Grupo 2 lo componen todas aquellas letras a la derecha del pivote.

Después de elegir un pivote en la palabra, todas las letras en el Grupo 1 se desplazan a la izquierda una sola posición, y todas las letras en el Grupo 2, se desplazan a la derecha una sola posición, como se muestra a continuación,


El objetivo del juego es elegir los pivotes adecuados de tal forma que partiendo de una palabra se llegue a la otra.

TAREA 
Hacer un programa que permita:
- Leer de la entrada estándar la longitud y las dos palabras del juego. 
- Determinar los pivotes adecuados para que partiendo de una palabra, se llegue a la otra. 
- Escribir hacia la salida estándar los pivotes en el orden que fueron seleccionados.

Input

Línea 1 : $L$ $(1 \leq L \leq 250)$, el cual representa la longitud de las dos palabras formadas por letras minúsculas y mayúsculas del alfabeto inglés.
Línea 2: La palabra a la cual se quiere llegar en el juego. 
Línea 3: La palabra inicial del juego.

Output

Línea 1 : Enteros separados entre sí por un espacio en blanco, la secuencia de números que representan las posiciones de los pivotes, en el orden que fueron seleccionados. La secuencia termina con el número $0$, que indica que la palabra inicial se convirtió en la palabra final. Si existen múltiples soluciones, la tarea es encontrar una, no necesariamente la óptima. No obstante usted deberá encontrar una solución que no exceda los $200000$ pivotes.

Sample test(s)

Input
3 abc bac
Output
2 0
Input
6 abcabc aabbcc
Output
6 2 2 0

Hints

Caso # 2:

Pivote

Grupos

Nueva Cadena

6

aabbcc |

abbcca

2

ab | bcca

baabcc

2

ba | abcc

abcabc