quinta-feira, 27 de setembro de 2012

#66 Exercício - Plágio musical

Nome: Plágio musical
Link: http://br.spoj.pl/problems/PLAGIO/
Dificuldade: 8/10
Linguagem: C++
Tempo atingido: 0.46
Memória usada: 3.3M
Colocação alcançada: 55
Tentativas: Várias

Comentário:
Caramba, essa foi difícil.
Mas depois de pensar e repensar estratégias, deu pra resolver.
Aliás, os músicos levam uma vantagem ai pra poder identificar a entrada. Caso não estejam compreendendo, pensem nas notas como um sequência que se repete, e tente calcular o intervalo entre cada nota.

Dicas:
- O primeiro passo é converter a entrada em valores inteiros. Eu converti a entrada entre valores de 1 a 12, que é o total de notas musicais.
- Uma dica é calcular as diferenças entre cada nota adjacente, para então poder comparar com as diferenças da melodia original.
- Outra dica é encontrar um modo de não ficar voltando ao começo da melodia. Tentem ir sempre em frente, verificando e voltando o mínimo possível.

3 comentários:

  1. Dá pra perceber pelo tamanho da entrada do programa que não dá pra procurar a correspondencia usando o algoritmo comum. Mas vc não mencionou nenhum específico, você usou o Knuth-Morris-Pratt que é feito pra isso? ou deduziu outro?

    ResponderExcluir
  2. Bom, eu não cheguei a estudar algo relacionado ao assunto, foi mais dedução mesmo.

    ResponderExcluir
  3. blz, era só curiosidade. eu ainda não fiz não. Vou tentar ver aki se eu consigo por mim mesmo, se eu não pensar em nda eu vou tentar aprender o knuth-morris-pratt mesmo, pq eu ainda nem sei ele, só conheço a existencia. Outra questão que é do mesmo tipo é o construtores de totens, é uma correspondencia bidimensional, é mais dificil ainda.

    ResponderExcluir