Difference between revisions of "Problema da quebra do colar (USACO)"

Latest revision as of 14:05, 10 November 2008

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
                       ****** *****