Limak y la Compañía


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C++, Java, Python

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 S 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 S.

¿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 n (1 \leq n \leq 75) - la longitud de la cadena.

La segunda línea contiene una cadena S, que consiste en letras mayúsculas en inglés. La longitud de la cadena es igual a n.

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

There are no comments at the moment.