Cultivar hortalizas PSN
Descripcion
OCI-cub, un experto en huertos domésticos, cultiva hortalizas de hierba PSN en su huerto casero. En su jardín hay macetas alineadas en dirección este-oeste. Estas macetas están numeradas por desde el extremo oeste.
Hay gramíneas PSN. En cada maceta hay plantada una hierba PSN.
En primavera, OCI-cub se dio cuenta de que, en contra de sus expectativas, las gramíneas PSN habían producido hojas de varios colores.
Además, descubrió que las hierbas PSN no habían crecido tanto como esperaba. Buscó en los libros y encontró los siguientes datos:
- Hay tres tipos de hierba PSN, con hojas rojas, verdes o amarillas.
- Si las hierbas PSN con el mismo color de hoja se colocan cerca, se impide su crecimiento.
Por lo tanto, OCI-cub decidió reorganizar las macetas para que no se junten hierbas PSN con el mismo color de hoja.
Las macetas son tan pesadas que JOI-kun sólo puede cambiar dos hierbas PSN en macetas vecinas en una sola operación. En otras palabras, lo que OCI-cub puede hacer en una sola operación es elegir una maceta arbitraria () y luego intercambiar las hierbas PSN en las macetas e .
Tarea
Escribe un programa que, dado el número de hierbas PSN y los colores de las mismas, calcule el mínimo número de operaciones necesarias para reordenar las hierbas PSN de forma que no se junten hierbas PSN con el mismo color de hoja.
Entrada
Lea los siguientes datos de la entrada estándar.
es una cadena de longitud . Su i-ésimo () carácter es , , e si el color de la hoja de la hierba PSN en el macetero es rojo, verde y amarillo, respectivamente.
Salida
Escriba una línea que contenga el número mínimo de operaciones requeridas en la salida estándar. Si es imposible reordenar las hierbas PSN para que no se junten hierbas PSN con el mismo color de hoja, escriba en su lugar.
Restricciones
- es una cadena de longitud .
- Cada carácter de es , o .
Subtareas
- (5 puntos) .
- (55 puntos) .
- (15 puntos) Cada carácter de es o .
- (25 puntos) No hay restricciones adicionales.
Ejemplos de entrada y salida
Ejemplos de Entrada #1
5
RRGYY
Ejemplos de Salida #1
2
La siguiente es una forma de reorganizar las gramíneas PSN para que no haya gramíneas PSN con el mismo color de hoja contiguas:
- Primero, intercambia las gramíneas PSN de las macetas y .
- En segundo lugar, intercambia las gramíneas PSN de las macetas y .
Después de esto, el orden de las hierbas Joy será . Dado que es imposible reordenar las hierbas PSN con un máximo de
la respuesta es .
Ejemplos de Entrada #2
6
RRRRRG
Ejemplos de Salida #2
-1
En este ejemplo, independientemente de las operaciones, es imposible reorganizar las gramíneas PSN de modo que ninguna gramínea PSN con el mismo color de hoja
Ejemplos de Entrada #3
20
YYGYYYGGGGRGYYGRGRYG
Ejemplos de Salida #3
8
Comments