Limak y la Compañía
Bear Limak prepara problemas para una competición de programación. Por supuesto, sería poco profesional mencionar el nombre del patrocinador en la declaración. Limak lo toma en serio y va a cambiar algunas palabras. Para que sea aún posible leer, intentará modificar cada palabra lo menos posible.
Limak tiene una cadena que consiste en letras mayúsculas en inglés. En un movimiento puede intercambiar dos letras adyacentes de la cadena. Por ejemplo, puede transformar una cadena "ABBC" en "BABC" o "ABCB" en un movimiento.
Limak quiere obtener una cadena sin una subcadena "VK" (es decir, no debe haber ninguna letra "V" seguida inmediatamente por la letra "K"). Se puede demostrar fácilmente que es posible para cualquier cadena inicial .
¿Cuál es el mínimo número posible de movimientos que Limak puede hacer?
Entrada
La primera línea de la entrada contiene un entero
- la longitud de la cadena.
La segunda línea contiene una cadena , que consiste en letras mayúsculas en inglés. La longitud de la cadena es igual a
.
Salida
Imprime un entero, denotando el mínimo número posible de movimientos que Limak puede hacer, para obtener una cadena sin una subcadena "VK".
Ejemplo de Entrada #1
4
VKVK
Ejemplo de Salida #1
3
Ejemplo de Entrada #2
5
BVVKV
Ejemplo de Salida #2
2
Ejemplo de Entrada #3
7
VVKEVKK
Ejemplo de Salida #3
3
Ejemplo de Entrada #4
20
VKVKVVVKVOVKVQKKKVVK
Ejemplo de Salida #4
8
Ejemplo de Entrada #5
5
LIMAK
Ejemplo de Salida #5
0
Explicación
En el primer ejemplo, la cadena inicial es "VKVK". El número mínimo posible de movimientos es 3. Una secuencia óptima de movimientos es:
• Cambia las dos últimas letras. La cadena se convierte en "VKKV".
• Cambiar las dos primeras letras. La cadena se convierte en "KVKV".
• Cambia la segunda y la tercera letra. La cadena se convierte en "KKVV". Esta cadena no tiene una subcadena "VK".
En el ejemplo dos, hay dos secuencias óptimas de movimientos. Uno es "BVVKV" → "VBVKV" → "VVBKV". El otro es "BVVKV" → "BVKVV" → "BKVVV".
En la quinta muestra, no son necesarios intercambios.
Comments