https://www.adonaimedrado.pro.br/wiki/index.php?action=history&feed=atom&title=Problema_da_quebra_do_colar_%28USACO%29 2026-05-27T20:10:30Z Revision history for this page on the wiki MediaWiki 1.26.2 https://www.adonaimedrado.pro.br/wiki/index.php?title=Problema_da_quebra_do_colar_(USACO)&diff=745&oldid=prev 2008-11-10T14:05:21Z

<p>New page: Tradução &#039;&#039;&#039;com adaptações textuais&#039;&#039;&#039; de Broken Necklace da USACO (http://ace.delos.com/usacoprob2?a=rRnbNp27COM&amp;S=beads). == Dificuldade Única == Você tem um colar de N (3&lt;=N&lt;=25...</p> <p><b>New page</b></p><div> Tradução '''com adaptações textuais''' de Broken Necklace da USACO (http://ace.delos.com/usacoprob2?a=rRnbNp27COM&amp;S=beads).<br /> <br /> == Dificuldade Única ==<br /> Você tem um colar de N (3&lt;=N&lt;=250) pedras, algumas das quais são vermelhas, outras azuis e outras brancas ordenadas de forma aleatória.<br /> <br /> 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.<br /> <br /> 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).<br /> <br /> 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).<br /> <br /> Determine um ponto de quebra que permitirá, conforme a regra acima, coletar o maior números de peças.<br /> <br /> === Formato de entrada ===<br /> *Linha 1: N, número de pedras.<br /> *Linha 2: Uma string contendo N caracteres, cada um sendo r, b ou w conforme descrito acima.<br /> <br /> Nome do arquivo de entrada: beads.in.<br /> <br /> ==== Exemplo de entrada ====<br /> 29<br /> wwwbbrwrbrbrrbrbrwrwwrbwrwrrb<br /> <br /> === Formato de saída ===<br /> 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.<br /> <br /> Nome do arquivo de saída: beads.out.<br /> <br /> ==== Exemplo de saída ====<br /> 11<br /> <br /> ==== Explicação da saída ====<br /> 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). <br /> <br /> wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb<br /> ****** *****</div>

Adonaimedrado