Nome: Moedas
Link: http://br.spoj.pl/problems/MOEDAS/
Dificuldade: 7/10
Linguagem: C++
Tempo atingido: 0.20
Memória usada: 3.1M
Colocação alcançada: 51
Tentativas: 8
Comentário:
Muito interessante este exercício, pode parecer simples mas um algoritmo ingênuo estoura o tempo facilmente.
Para resolvê-lo eu usei algo parecido com BFS, só que um pouco objetivo.
A ideia eu tirei deste tópico aqui, do blog do péricles.
Também é possível resolver com PD (Programação Dinâmica), como me ensinou meu parceiro Fúlvio Abrahão. Agradeço a ajuda.
Dicas:
- Testar todos os casos com todas as possibilidades é suicídio, o tempo vai estourar, portanto nem tente.
- Uma boa técnica é criar um vetor para armazenar, no indice valor, a quantidade mínima de moedas para se chegar lá. Por exemplo: no vetor m[] de índice 10, visto que eu tenho posse de moedas de 2 e de 5 centavos, é possível chegar lá com 2 moedas de 5 centavos, portanto m[10]=2. Agora usem a imaginação.
Curto e grosso: para resolver o problema moedas do spoj crie um vetor com 50000 posições. O índice desse vetor vai ser o preço (o spoj chama de "m") . A posição zero vai conter zero. Suponha que as moedas disponíveis sejam 6 e 13. O conteúdo da posição 57, p.ex., vai ser um mais a posição 57-6 ou 57-13, a que for menor ou impossível, se ambas forem impossíveis.
ResponderExcluirAlgo do tipo 1 + qm[i - v[j]], onde qm é o vetor. No exemplo, i=57, v o vetor com os valores das moedas, 6 e 13.