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

Warrior

USACO

536 mensagens neste tópico

Um novo ano começa.. e nada melhor do que começar a preparação para os concursos que se avizinham nos proximos períodos..

Como tal, deixo-vos uma pérola.

http://train.usaco.org

Esta é a página de selecção dos representantes norte-americanos para as olimpíadas internacionais de informática, mas é útil para todos os outros amantes da programação.

Matéria

-Exercícios

Matéria

-Exercícios

Se querem ficar bem preparados, são 6 capítulos, cada um com 5 secções, cada uma de 3 a 5 problemas..

Precisam de os resolver para avançarem para a fase seguinte.

A "matéria" vai desde Grafos, Números binários (bitwise comparisons, inversions, etc) ou programação dinâmica.

Nota: Tenho resolvido desde que cheguei de férias, ainda só vou na secção 1.5, mas tenho todo o gosto em ajudar quem "encravou".

Nota2: Sem trabalho e persistência.. nada feito. E afinal vocês querem a viajem à Croácia para as IOI 07 ou não?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Obrigado pelo link, vou analizar o material.

Já agora, as linguagens admitidas neste tipo de concursos quais são... C/C++ e Pascal? :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Exactamente. O USACO tambem admite JAVA, mas não é admitido nas IOI.

(Existe uma grande discussão entre substituir Pascal por JAVA, mas grande parte dos países de leste e da america latina ainda usam o pascal em grande escala..)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se fosse permitida uma linguagem dinâmica, digamos que tinha mais piada... :(

Bem, já me registei mas estou há espera do mail com os dados à mais de uma hora. O registo tem de ser avaliado primeiro?

Já agora, enquanto eu não consigo aceder ao sistema, mete aqui o primeiro exercício. ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que eu me lembre não.

Se fosse a ti verificava o mail (se digitaste correctamente) ou voltava a tentar registar.

Não te posso mostrar o primeiro exercício porque é mesmo para ver se consegues perceber como funciona o sistema de submissões.. (a soma de dois numeros acho eu)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu gostava mesmo de vos incentivar para a resolução destes problemas.

Agora nas férias do Natal (para quem as tem) existe mais tempo, portanto não hesitar em dar uma olhada.

http://train.usaco.org

Vou deixar uma dica (retirada da análise) para o primeiro problema:

É bastante directo e simples, o único cuidado a ter é não processar o "newline" no final.

Se existir alguém mais à frente (ou neste capítulo até) com dificuldade, pergunte aqui ou por PM.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Btw Warrior, sabes quando começam as olímpiadas da informática portuguesas?

Dá para participar estando no 12º?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Qualquer aluno que frequente o ensino básico ou secundário pode participar, desde que seja nascido depois de 30 de Junho de 1987, acho eu.

Acho que a fase de qualificação é em Maio, mas eu devo fazer um post na secção a avisar assim que souber.

A menos que me esqueça, como aconteceu com o CIP..

Já agora, fica aqui para o futuro:

http://cip.dei.uc.pt/

O concurso já foi e eu esqueci-me..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O pessoal que anda no secundário tem que começar a preparação para as próximas olimpiadas nacionais ehehe.

Vamos elevar o nivel das competições portuguesas :P

aproveitem este site e se precisarem de ajuda postem por aqui  :cheesygrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já lá cheguei, e já resolvi o primeiro, Beef McNugets. Quanto ao fence rails: li por alto, não me pareceu exageradamente complicado de resolver (knapsack, já se resolveram vários para trás), mas confesso que não olhei para valores nem fiz contas a complexidade. Se exige tanta optimização.. estou lixado. De qualquer das formas já tinha ouvido falar da sua fama, portanto vou deixá-lo para o fim.

Já que se fala da usaco, usemos o post próprio :D

O Beef McNugets e o Fence Loops são simples.

A base do módulo é a optimização e isso é visivel nos outros exercícios. O Cryptcowgraphy, na minha opinião, é bastante mais complicado do que parece (é preciso optimizar muito).

O Fence Rails é um Multiple Knapsack. Temos até 50 "mochilas", as tábuas, e 1023 Rails... nem é preciso fazer contas para ver que não dá pa usar a Programação Dinâmica como num Knapsack simples. Eu já tenho umas ideias sobre a optimização, mas ainda não peguei no exercício a sério.

Mas parece-me o exercício mais dificil dos que já vi na usaco  :hmm:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Fence Loops já está, cryptcowgraphy follows.

Ainda não pensei muito nele, mas julgo que já consegui chegar a algumas conclusões importantes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Fence Loops já está, cryptcowgraphy follows.

Ainda não pensei muito nele, mas julgo que já consegui chegar a algumas conclusões importantes.

;)

Eu inda vou fazer um exame de melhoria na 6a... mas dp disso nem sei se vou voltar já a USACO. Em principio vou parar um bocado e aproveitar bem este solzinho que começa a aparecer finalmente  :P

É verdade.. decaminho já partes pas IOI's nao ? ehehe. Já tiveram o estágio?

E ná mais pessoal a fazer exercícios da USACO ?  Manifestem-se lol  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ainda não, o estágio começa dia 30, mas uma vez que ganhei as ONI este ano só muito dificilmente não vou.

Eu tinha encostado o USACO, mas agora que arranjei alguém que vai à minha frente deu-me a vontade novamente..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ainda não, o estágio começa dia 30, mas uma vez que ganhei as ONI este ano só muito dificilmente não vou.

Eu tinha encostado o USACO, mas agora que arranjei alguém que vai à minha frente deu-me a vontade novamente..

lololol

Ao menos fico contente por te fazer treinar ehehe :D  Mas vais-me passar facilmente, mas só pk eu tou em "férias" lol , na brinca  :P

O André Pinto está no mesmo ponto que eu. A faltar o Fence Rails. Depois podemos picar a 3 xD

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

E ná mais pessoal a fazer exercícios da USACO ?  Manifestem-se lol  :P

Eueueueueueueueu! E o pcaldeira também andava por lá mais o vbmaster. :D
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

E ná mais pessoal a fazer exercícios da USACO ?  Manifestem-se lol  ;)

Eu comecei ontem...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que cena é esta do USACO?

Saudações...

É o sistema de treino norte americano para as olimpíadas. Muito provavelmente uma das (senão mesmo a) melhor forma de aprendizagem de algoritmos.

Quem precisar de ajuda a resolver um problema que se manifeste. (apesar de que agora vou estar fora uns dias..)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Report - Vou na secção 1.4, já com o problema Mother's Milk resolvido... Alguém mais ou menos na mesma situação? ;)

PS - Aquelas imagens no Packing Rectangles, não as consigo perceber, e pelo tópico no fórum parece que são essenciais para resolver o problema :x

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

PS - Aquelas imagens no Packing Rectangles, não as consigo perceber, e pelo tópico no fórum parece que são essenciais para resolver o problema :x

Para mim é o problema mais xato da secção, deixei-o para o fim na altura  ;)

Sim, as imagens são fundamentais. Elas (como tem na legenda :P ) têm as configurações possíveis dos rectangulos. Se reparares bem 2 das configurações são iguais, por isso só há 5 configurações diferentes.

Dão-nos 4 rectangulos e temos de os usar em cada uma dessas configurações para descobrir a menor área. Em cada configuração, cada um dos rectangulos pode estar "deitado" ou "de pé".

Preferia não me alongar senão decaminho já digo a solução do problema lol

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Report - Vou na secção 1.4, já com o problema Mother's Milk resolvido... Alguém mais ou menos na mesma situação? :P

PS - Aquelas imagens no Packing Rectangles, não as consigo perceber, e pelo tópico no fórum parece que são essenciais para resolver o problema :x

tao... conseguiste fazer o exercício ?  :D  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ainda não voltei a tentar... dessa secção já resolvi o Arithmetic Progressions e o Mother's Milk, estou agora a ler sobre bfs para fazer o The Clocks e depois então vou para o Packing Rectangles, que parece ser o mais chato. ;)

EDIT: Decidi tentar o Packing Rectangles primeiro, estou a (tentar) fazê-lo agora, mas se é o que me parece (só calcular a área nos diferentes layouts, com uma fórmula para cada um, e ver qual é a menor) não deve ser muito difícil, o código é que deve ficar bem grande.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O código fica enorme.

Cuidado que não te podes limitar a tentar po-los à sorte naquelas posições, pois podes fazer permutações entre eles (e um rectângulo pode estar deitado ou de pé)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

E já agora... depois informa se também erraste no caso de teste nº 17  lol

tanto eu como um amigo meu falhamos nesse caso de teste à primeira submissão... um pormenorzito :P

E Warrior, boa sorte para as IOI's  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acabei por resolver primeiro o The Clocks, usei um bfs simples com uma fila circular para poupar espaço, mas mesmo assim nos últimos testes vi-me à rasca por causa do limite de memória :\ Agora o Packing Rectangles é ligeiramente mais complicado, não sabia que os rectângulos podiam rodar... (Possível Spoiler ->) Sendo assim, vou ter de, para cada permutação entre os rectângulos de 1 a 4, calcular a área, para cada um dos layouts, de cada uma das combinações de rectângulos deitados ou de pé... O que dá um total de 4!*2^4 combinações, para cada uma das quais tenho de calcular 6 áreas, certo?

0

Partilhar esta mensagem


Link 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