Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
Localhost

Problem 99: Broken Necklace - Usaco

Recommended Posts

Localhost

Bem, decidi voltar à Usaco. Eu estava parado neste problema e ainda não percebi o que é que é pedido. Qual é a lógica deste problema?


here since 2009

Share this post


Link to post
Share on other sites
Tharis

Tens um colar com pecinhas 'b', 'r', 'w'. O que tu queres é determinar onde deves partir o colar, de modo a que, se começares numa das peças onde partiste o colar e começares a andar para a frente no colar a partir dessa posição, consigas o maior número de peças antes de encontrares uma peça da cor diferente da inicial.

BTW, devias ter postado isto no tópico da USACO.

Share this post


Link to post
Share on other sites
Localhost

Então não consigo perceber o output do exemplo deles.

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

                                                  ******* ******

Ali para o meio tem peças 'r' e peças 'b'.


here since 2009

Share this post


Link to post
Share on other sites
Warrior

O exemplo não ficou bem aqui no forum que não usa uma font monospace..

A ideia é que se partires o colar entre o r e o b (28ª e 29ª bead) consegues recolher 5 reds para o lado esquerdo e 6 blues para o lado direito. O teu objectivo é descobrir qual o número máximo de peças que consegues recolher se após partires num determinado sítio (que maximize o número anterior) só recolhas peças de uma cor para um lado e da outra cor para o outro.

Share this post


Link to post
Share on other sites
Cynary

Ainda não fiz esse problema, mas é simples.

É assim:

Segues o colar, e juntas as peças em grupos:

bs e ws sequenciais juntos

e rs e ws sequenciais juntos

O output do exemplo deles está lá explicado. É para imaginares o colar como estando duplicado, pois passa do fim para o início (já que é circular :) ).

Amanhã vou ver isso com mais calma.

Share this post


Link to post
Share on other sites
Cynary

Vou nesse mesmo problema :)

Ainda só tive umas duas horas livres para estar na USACO (tenho estado obcecado com o problema da final no mooshak xD). Vou ver se hoje avanço mais um pouco.

No entanto, o problema não parece muito complicado. Basta ver se o início da string é w ou igual ao caracter final, e caso seja, avançar até chegarmos a um caracter diferente de w e do caracter final, e começar daí (um simples while). Depois, é contar os grupos diferentes e ver qual o mais longo.

Como disse, simples xD

Share this post


Link to post
Share on other sites
Localhost

Lol, ok. Ainda bem :)

p.s. já resolveste o resto dessa secção?


here since 2009

Share this post


Link to post
Share on other sites
Cynary

Lol, ok. Ainda bem :P

p.s. já resolveste o resto dessa secção?

Sim, essa secção era fácil :) (também para primeira, não é suposto ser difícil xD).

Share this post


Link to post
Share on other sites
Localhost

Boa. Ainda bem que já tenho competição (alguém a fazer os execícios que eu tou mais ou menos a fazer, eu vou na secção 1.2., tens de ter em atenção que só posso ao fim de semana  :) ). Vai dar mais pica agora  :P


here since 2009

Share this post


Link to post
Share on other sites
Cynary

Boa. Ainda bem que já tenho competição (alguém a fazer os execícios que eu tou mais ou menos a fazer, eu vou na secção 1.2., tens de ter em atenção que só posso ao fim de semana  :) ). Vai dar mais pica agora  :)

Hehe.

Parece que vai ser divertido :P

Infelizmente tenho uma vantagem injusta contra ti, pois apesar desta e da próxima semana ter pouco tempo, depois começam as férias, e tenho pouco mais para fazer xD.

EDIT: Subestimei o problema, mas acabei por conseguir fazê-lo hehe. Mas ainda demorou um pouco xD

Agora já estou na secção 1.2.

Share this post


Link to post
Share on other sites
Localhost

Eu nas férias também tenho muito mais tempo. Estava a dizer que não tinha tempo à semana porque como podes ver só venho ao pc a estas horas e estou cansado para resolver problemas. A partir de amanhã que é o meu último teste já vou ter mais tempo  :)


here since 2009

Share this post


Link to post
Share on other sites
Cynary

Então óptimo :)

Hoje já fiz dois problemas da 1.2 :P

Também me canso xD

Então a competição está justa hehe.

Boa sorte a ambos!

Share this post


Link to post
Share on other sites
Cynary

Bom, agora vais ter de me acompanhar.

Acabei hoje a 1.2 ;)

Uma sugestão: faz os dois problemas dos palíndromes no mesmo dia, já que usas muito código de um no outro (se o programa for modular), e assim despachas tudo facilmente, enquanto está "fresco" xD (isto se já não tiveres feito estes problemas ;)).

Share this post


Link to post
Share on other sites
Localhost

Já tiveste experiência disto antes? Parece-me que estás a resolver os problemas muito rapidamente 🤔


here since 2009

Share this post


Link to post
Share on other sites
Cynary

Como referi na minha apresentação, já programo há alguns anos, portanto já tenho alguma experiência.

Como comecei a aprender com C, e depois usei principalmente PHP para desenvolvimento web (muito parecido com C, apenas com mais alguma liberdade em termos de organização de código), consigo orientar-me bem no C, e sei fazer algoritmos bem (acho eu xD).

Mas em termos de experiência de código para concursos deste tipo, é perto de nula até há uns dias.

Já participei em alguns problemas do UVA online judge há um ou dois anos, mas fiquei sem pachorra xD (dava-me sempre errado, e não tinha muita pachorra para estudar porquê, apesar de me dar constantemente certo ;)).

Este ano fiquei a saber das olimpíadas (gostava de ter sabido antes :/), e isso motivou-me. Foi assim que encontrei este site, e consequentemente o USACO ;)

Mas ainda estás a tempo de me ultrapassar xD. Aproveita que vou estar uns dias sem tempo nenhum na próxima semana lol.

Share this post


Link to post
Share on other sites
Localhost

O dominio que tens sobre uma determinada acho que não tem nada a ver com a facilidade com que resolves os problemas.

Pelo menos isto é a minha opinião.

É certo que se tiveres controlo sobre uma linguagem é muito mais fácil de resolveres porque já conheces os recursos que ela te pode oferecer, no entanto, acho que neste tipo de concursos e de problemas presupõe-se que a pessoa que vai resolver os problemas já conhecem bem a linguagem com que os vão resolver e que tenham domínio sobre ela.

Acho que o que disse está correcto mas já disse que este é o meu 1º ano nestas andanças. Peço a alguém com mais experiência que me corrija se estiver errado  ;)


here since 2009

Share this post


Link to post
Share on other sites
Warrior

Tens razão no que dizes, mas experiência em várias linguagens pode-se traduzir num treino em diferentes maneiras de pensar, o que é sempre benéfico.

De qualquer forma, conhecer a linguagem que estás a usar é essencial.

Share this post


Link to post
Share on other sites
Cynary

Acho que o que contribui mais para a minha capacidade de resolver estes problemas rapidamente é o meu conhecimento da linguagem, experiência que tenho a programar (pois assim já sistematizei algumas técnicas que estou sempre a reutilizar no meu código) e também nunca tive problemas em utilizar lógica/matemática, que contribuem muito.

Tens razão que o conhecimento da linguagem não contribui muito, mas o uso ao longo do tempo com diferentes problemas, obriga-te a aprender e desenvolver técnicas que te podem ser úteis de várias formas noutros problemas completamente diferentes. Quanta mais experiência fores acumulando em problemas diferentes, mais facilmente resolves qualquer problema de programação (mesmo que treines numa área completamente diferente de problemas de concursos).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.