Collar Roto
Usted tiene un collar de cuentas algunas de las cuales son rojas, otras azules, y otras blancas, arregladas de manera aleatoria. Aquí hay dos ejemplos para :
1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figura A Figura B
r cuenta roja
b cuenta azul
w cuenta blanca
Las cuentas consideradas primera y segunda en el texto que sigue han sido marcadas en las figuras.
La configuración en la Figura A puede ser representada como una cadena de y , donde representa una cuenta azul y representa una cuenta roja, como sigue: brbrrrbbbrrrrrbrrbbrbbbbrrrrb.
Suponga que usted debe romper el collar en algún punto, estirarlo, y luego recolectar las cuentas del mismo color de un extemo hasta que usted encuentre una cuenta de diferente color, y hacer lo mismo con el otro extremo (el cual podría no ser del mismo color de las cuentas previamente recolectadas).
Determine el punto donde el collar debería ser cortado de tal manera que sea recolectado el número máximo de cuentas.
Por ejemplo, para el collar en la Figura A, puden ser recolectadas 8 cuentas, con el punto de rompimiento entre las cuentas 9 y 10 o también entre la cuenta 24 y la cuenta 25.
En algunos collares, se han incluido cuentas blancas como se muestra en la figura B. Cuando se recolecta cuentas, una cuenta blanca que es encontrada puede ser tratada como roja o azul y luego pintada con el color deseado. La cadena que representa esta configuración incluirá cuentas de los tres símbolos y .
Escriba un programa que determine la cantidad más grande de cuentas que pueden ser recolectadas de un collar dado.
Entrada
Línea 1: , el nùmero de cuentas Línea 2: una cadena de caracteres, cada uno de los cuales es o
Salida
Una sola lìnea que contiene el máximo número de cuentas que pueden ser recolectadas del collar dado.
Ejemplo de Entrada
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
Ejemplo de Salida
11
Comments