Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Localhost

Problem 99: Broken Necklace - Usaco

Mensagens Recomendadas

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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 ;)).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.