Jump to content

USACO


Warrior

Recommended Posts

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?

Link to comment
Share on other sites

  • 2 months later...

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.

Link to comment
Share on other 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..

Link to comment
Share on other sites

  • 6 months later...

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 😛

aproveitem este site e se precisarem de ajuda postem por aqui  😁

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other 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 😄

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  ?

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other 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  😛

É 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  😄

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other 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 😄   Mas vais-me passar facilmente, mas só pk eu tou em "férias" lol , na brinca  😛

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

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

  • 3 weeks later...

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 😛 ) 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

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
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
×
×
  • Create New...

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.