View source for Problema da quebra do colar (USACO)

 Tradução '''com adaptações textuais''' de Broken Necklace da USACO (http://ace.delos.com/usacoprob2?a=rRnbNp27COM&S=beads).

== Dificuldade Única ==
Você tem um colar de N (3<=N<=250) pedras, algumas das quais são vermelhas, outras azuis e outras brancas ordenadas de forma aleatória.

Uma configuração pode ser representada como uma cadeia de caracteres (string) em uma seqüência de letras b, r e w, onde b representa uma pedra azul, r uma pedra vermelha e w uma pedra branca. Exemplo: brbrrrbbbrrrrrbrrbbrbbbbrrrrb.

Suponha que você tem que quebrar este colar em algum ponto e então coletar as pedras da mesma cor de uma ponta até que encontre uma pedra de outra cor e fazer o mesmo para a outra ponta (a qual pode ou não ter a mesma cor das pedras coletadas na outra ponta).

Durante a contagem cada pedras braca pode ser tratadas como vermelhas ou azuis, já que pode posteriormente ser pintada de vermelho ou de azul (a que for mais vantajosa para maximizar o número de pedras coletadas).

Determine um ponto de quebra que permitirá, conforme a regra acima, coletar o maior números de peças.

=== Formato de entrada ===
*Linha 1: N, número de pedras.
*Linha 2: Uma string contendo N caracteres, cada um sendo r, b ou w conforme descrito acima.

 Nome do arquivo de entrada: beads.in.

==== Exemplo de entrada ====
 29
 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

=== Formato de saída ===
Uma única linha contendo o número máximo de pedra que podem ser coletadas com o colar informado e seguindo a regra de quebra descrita.

 Nome do arquivo de saída: beads.out.

==== Exemplo de saída ====
 11

==== Explicação da saída ====
Considerando que o colar é cíclico (somente a representação feita que é linear). A string com as 11 pedras capazes de ser recuperadas está marcada abaixo (Duas string postas lado a lado para emular o formato cíclica de um colar).  

 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
                        ****** *****