Algoritmos e Estrutura de Dados I - AE22CP - 2012/1

TRABALHO PRÁTICO 2

Bruno César Ribas e Silvio Boss

Resultado Final do RANK

A etapa final do rank foi executada dia 3 de outubro, com uma entrada que possui 10 pokemons com no máximo 20000 habilidades e 21769 inimigos com no máximo 500 fraquezas, o arquivo de entrada possui 68MB. Mais informações de todas as execuções do rank e link para download das entradas acesse a página do RANK.

Gostaria de parabenizar todos os alunos que enviaram o trabalho para o sistema de rank.

Nome Golpes Utilizados Tempo de Execucao Ponto extra
Douglas Ortlieb 45409 4.41 10
Willian Leonardo 45409 9.06 10
Bruno Ribas 45409 11.18 --
Matheus Bauer 45409 16.64 10
Maycon Douglas 45409 3298.57 5
stanga 45409 3756.35 5
Dionei Michem 45409 4664.27 5
Renan Ribeiro Andre H 45409 5103.15 5
Marcio 45409 5779.02 5
Gil 45409 6553.25 5
Fabricio Monitor 45409 8540.08 --
Fernanda Moreira 45409 9854.14 5
Dalmo Hollen 45409 17760.93 5

O Mundo Pokemon

O mundo dos treinadores Pokemon está bem agitado com a aproximação do torneio internacional de batalhas Pokemon.

Ash está com diversas dificuldades em continuar seu treinamento pois Mist e Brock não ajudam mais como antigamente. Mist resolveu voltar a treinar com suas irmãs e Brock só pensa em seu namoro com a enfermeira Joy de Hyrule. Apesar das dificuldades Ash não desiste e quer se tornar o maior medalhista de todos os tempos com seus Pokemons e quer fazer um treinamento rigoroso.

Uma batalha Pokemon consiste em uma disputa entre dois Pokemons comandados por seus respectivos mestres e por isso o treinador deve conhecer seus Pokemons, e acima de tudo, o treinador deve ser o melhor amigo do Pokemon e o Pokemon o melhor amigo de seu treinador. Quando essa relação simbiótica está feita as batalhas poderão fluir de uma forma jamais vista.

Para continuar o treinamento você foi contratado para desenvolver um programa de computador que ajude Ash a escolher o Pokemon certo e executar o melhor golpe para nocautear o inimigo.

Enunciado do trabalho

O Enunciado do trabalho está disponível em PDF.

Formato de Entrada

O arquivo de entrada deve ser seguido rigorosamente, como foi descrito no enunciado em pdf.

Segue um exemplo de entrada: 

  3
  Machoke [ secreto19: 5 ]
  Electrode [ golpeN: 4, secreto7: 3, golpe35: 3 ]
  Clefairy [ secreto19: 1, smog: 2, ember: 2, secreto2: 1, golpeR: 3 ]
  
  Ludicolo [ golpeN: 1, smog: 2, secreto2: 2, golpeR: 1 ]
  Klink [ smog: 3, secreto2: 4, golpeR: 5, golpeN: 3, secreto7: 1 ]
  Snover [ golpeN: 2, secreto7: 4, secreto19: 2, golpe35: 4 ]
  Escavalier [ secreto19: 2, golpe35: 3, ember: 2, secreto2: 2, smog: 3 ]
  FIM

Batalha

Uma batalha consiste em analisar o Pokemon inimigo e identificar sua fraqueza e depois escolher um Pokemon que você seja o dono e aplicar o seu golpe no inimigo tantas vezes seja necessário para tirar pelo menos 100 pontos de energia.

Cada Fragilidade de um Pokemon inimigo possui o mesmo nome da Habilidade de seu Pokemon. O ataque é contabilizado multiplicando a força da habilidade do seu Pokemon com o multiplicador da Fragilidade para essa Habilidade.

Um inimigo pode ser atacado por apenas 1 Pokemon seu e cada inimigo possui 100 de energia.

Um exemplo de ataque para a entrada definida acima é: o Pokemon 'Electrode' é seu e possui o golpe 'golpeN', o Pokemon inimigo 'Ludicolo' possui a fragilidade 'golpeN'. A força do golpe 'golpeN' de 'Electrode' é 4 e a fraqueza para esse golpe de 'Ludicolo' é 1. Então aplicando o 'golpeN' 25 vezes em 'Ludicolo' gera a conta 25 * (4 * 1) = 100. Logo 25 vezes o 'golpeN' de 'Electrode' em 'Ludicolo' é o suficiente para derrotá-lo.

Formato da Saída

As batalhas acontecem na ordem do arquivo de entrada, ou seja, você deve derrotar os inimigos na ordem em que aparecem no arquivo de entrada.

Por exemplo, considerando a entrada definida acima, o seu programa deve imprimir primeiro como você derrota o inimigo "Ludicolo" e depois como derrota o "Klink" depois o "Snover" e por fim como derrotar o "Escavalier".

Uma possível solução é: 

  Electrode golpeN 25
  Clefairy golpeR 7
  Electrode golpe35 9
  Machoke secreto19 10

Nesse exemplo de solução significa que você usou o 'Electrode' com o golpe 'golpeN' 25 vezes para derrotar o primeiro inimigo, que é o 'Ludicolo'. Depois usou o 'Clefairy' com o golpe 'golpeR' 7 vezes para derrotar o Klink. Depois o 'Electrode' com o 'gople35' 9 vezes para derrotar o 'Snover', e por fim usou o 'Machoke' com o golpe 'secreto19' 10 vezes para derrotar o 'Escavalier'

Execução

A entrada e saída do programa devem ser feitas pela entrada e saída padrão ( como se estivesse lendo as informações pelo teclado)

exemplo de execução: 

  ./meuprograma < input-3pokemon-10inimigos.txt

Onde "meuprograma" é o nome do executável do trabalho (pode ser outro nome qualquer), e "input-3pokemon-10inimigos.txt" é o arquivo que contém a descrição da batalha.

Quando executar o seu programa da forma indicada abaixo , o sinal '<' significa que o conteúdo do 'input-3pokemon-10inimigos.txt' será passado ao programa como se ele estivesse sendo lido do teclado.

Exemplo da solução do professor para o exemplo com 3 pokemons e 10 inimigos 

  brunoribas@winterfell:~$ ./pokemon < input-3pokemon-10inimigos.txt
  Electrode golpe35 9
  Clefairy ember 10
  Machoke secreto19 4
  Machoke secreto19 5
  Clefairy golpeR 12
  Electrode golpe35 7
  Electrode golpeN 25
  Clefairy golpeR 7
  Electrode golpe35 9
  Electrode secreto7 9

Exemplos de Entrada e Saída

Não se limite a esses exemplos, crie seus próprios exemplos!

Importante notar que o conteúdo gerado pelo seu programa como solução de um problema deve obedecer rigorosamente a especificação, não deve imprimir nada a mais nem a menos que o especificado.

Teste seu arquivo de solução

Teste o seu arquivo de solução para os exemplos de entrada definidos acima.

Esse testador verifica se o arquivo enviado está dentro dos padrões da especificação, conforme determina a saída do seu programa, bem como se a solução é factível.

Testar solucao para entrada:
Arquivo de Solução:

Ranking

O ranking será feito por disputas diárias. Para participar basta enviar o código compactado em .tar que o sistema copilará e executará.

Para participar do Ranking o seu código deve funcionar em LINUX, recomendamos o uso do Ubuntu. Se o sistema não conseguir compilar seu programa apenas será avisado que não conseguiu e nada mais.

---
Last Modified: Wed Oct 3 20:51:14 2012.