Blog de Helton Duarte

Estamos aqui de novo!

Bem, pessoal, como alguns já devem saber, próxima sexta-feira acontece em todo o Brasil a primeira fase da III Olimpíada de Algoritmo Hostnet e estarei participando mais um ano, em busca do bicampeonato =D. A fim de treinarmos para essa competição, resolvi fazer esse post, dando umas dicas e um exercício, como exemplo, para vocês tentarem fazer. OBS: Quem quiser saber se resolveu corretamente, faça um comentário dizendo isso que entrarei em contato por e-mail, ok?

Dicas

Tirando como base as dicas do site da Maratona de Programação e o artigo do Shariar Manzoor na revista Crossroads, pensei em umas dicas básicas:

• Não há nada pior do que gastar muito tempo fazendo e passando a limpo um algoritmo para, depois, descobrir que ele está errado. Na OAH, esse erro é fatal, já que o tempo é sempre um grande adversário. Por isso, apesar de a pressa ser necessária, procure sempre certificar-se da corretude do algoritmo ANTES de escrevê-lo!
• A escolha de seu time é essencial. Um bom time de programação precisa que cada componente tenha um conhecimento de algoritmos básicos (ordenação, encontrar n-ésimo número primo, calcular MDC/MMC, etc.), além da capacidade de criar novos para situações diversas.
• Ao treinar, certifique-se de que cada membro do time sabe fazer o básico, como escrever procedimentos e fazer “debug” de um algoritmo. Um time bem-sucedido terá membros com algumas especialidades, como aquele que resolve problemas com busca, ou aquele bom em matemática, ou aquele que encontra erros facilmente. Todos os membros devem saber as qualidades e defeitos dos outros para saber quem ficará responsável por cada questão.
• Todos devem estar aptos para realizar Pair-Programming, ou seja, resolver uma das questões juntamente com outro membro, principalmente as mais difíceis. Não aconselho que fiquem os 3 membros pensando sobre o mesmo problema, a não ser em casos extremos.
• Faça treinos de simulação, pois é a melhor forma de fazer a prova em um bom tempo. Treinar nas mesmas condições da competição é uma ótima dica, ou seja, fazer uma prova passada com o tempo cronometrado e depois pedir para um professor da instituição corrigí-la.
• Faça muitas questões daqui para sexta-feira!

Exercício

Coleta de Lixo Ecológica (traduzido e adaptado de “Ecological Bin Packing”, do UVa Online Judge)

O Problema

Reciclar vidro requer que ele seja separado por cor em uma das três categorias: vidro marrom, vidro verde e vidro transparente. Nesse problema você terá 3 latas de lixo, cada uma contendo um número específico de garrafas marrom, verde e transparente. No intuito de serem recicladas, as garrafas terão de ser movidas a fim de cada lata de lixo conter apenas garrafas de uma cor.

O problema é minimizar o número de garrafas que serão movidas. Você deve assumir que o único problema é minimizar o número de movimentos entre os cestos de lixo. Para a proposta desse problema, cada lixo tem a capacidade de armazenar infinitas garrafas e a única restrição é movê-las para cada cesto conter garrafas de uma única cor.

A Entrada

A entrada que seu programa irá ler consiste em uma linha contendo nove inteiros. Os primeiros três inteiros representam o número de garrafas marrons, verdes e transparentes (respectivamente) na lata 1, os segundos três inteiros representam o número de garrafas marrons, verdes e transparentes (respectivamente) na lata 2, os últimos três inteiros representam o número de garrafas marrons, verdes e transparentes (respectivamente) na lata 3. Por exemplo, a linha 10 15 20 30 12 8 15 8 31, indica que há 20 garrafas transparentes na lata 1, 12 garrafas verdes na lata 2 e 15 marrons na lata 3.

A Saída

A saída indicará as garrafas de que cores que estarão em cada lata para minimizar o número de movimentos. Você também deve escrever o número mínimo de movimentos com as garrafas para que isso ocorra.

O programa deverá escrever uma string com três letras maiúsculas ‘M’, ‘V’ e ‘T’ (representando as cores marrom, verde e transparente) representando a cor associada a cada lata de lixo.

O primeiro caracter representa a cor relacionada com a primeira lata, o segundo caracter representa a cor relacionada com a segunda lata e o terceiro caracter representa a cor relacionada com a terceira lata. Além disso, o inteiro representando o menor número de movimentos a serem feitos deverá vir seguido da string, separados com um espaço.

Se mais de uma ordem de latas marrom, verde e transparente produzir o número mínimo de movimentos, então a string que vier primeiro alfabeticamente deverá ser escrita.

Exemplo de Entrada 1

1 2 3 4 5 6 7 8 9

Exemplo de Saída 1

MTV 30

Exemplo de Entrada 2

5 10 5 20 10 5 10 20 10

Exemplo de Saída 2

TMV 50

Com isso, nossas dicas para a OAH 2009 estão dadas, então eu desejo a todos os competidores, desde já, boa sorte! Mostrem a todos que vocês são capazes, mas não esqueçam, Deus é o único responsável por qualquer conquista sua.

Posts interessantes:

• Categoria: Cursos – Programando Melhor
• Google Code Jam 2009: uma nova oportunidade
• Top Coder Marathon Matches
• OAH 2008

Vamos lá, treine bem para mais essa competição! Comente e diga qual colégio estará representando, além do mais, tire qualquer dúvida!

Helton de Melo Duarte

“O justo se alegrará no SENHOR e confiará nEle; e todos os retos de coração se regozijarão.” Salmos 64.10

“Bendito seja Deus, que não rejeitou a minha oração, nem desviou de mim a sua misericórdia.” Salmos 66.20

This entry was posted on sexta-feira, setembro 25th, 2009 at 17:57 and is filed under Cursos / Dicas / Tutoriais. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.