Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MOEDAS - Moedas

Autor: Pedro Demasi

O rei de Pinelândia tinha alergia ao material que compunha o dinheiro de seu país, e por isso resolveu acabar com todas as células, e mandou fabricar, dali em diante, apenas moedas. Os valores destas, ao contrário do que se esperava, não eram, necessariamente, múltiplos de 5. Como os preços das mercadorias, em Pinelândia, eram caríssimos, o povo tinha sérios problemas em fazer comércio, pois, dependendo do valor do que seria comprado ou vendido, o número de moedas a ser utilizado poderia ser muito alto. Por exemplo, se as moedas fabricadas fossem apenas de 5 tostões (a unidade monetária do reinado), um cidadão deveria usar 200 moedas para comprar algo que custasse 1000 tostões. Entretanto, se houvesse moedas de 35 e de 150, a pessoa precisaria ter apenas 22 moedas: 20 de 35 e 2 de 150.

Você deve escrever um programa que, dados o preço de uma mercadoria e os valores das moedas disponíveis, calcule o menor número possível de moedas necessário para comprar o produto sem haver troco, ou seja, o menor número de moedas tal que o total seja exatamente o preço da mercadoria.

Entrada

O arquivo de entrada contém vários casos de teste. Cada caso inicia com dois inteiros, m (1 <= m <= 50000), correspondente ao preço da mercadoria, e n (1 <= n <= 100), o número de moedas. A seguir, há n inteiros, 0 < v_1 < v_2 < ... < v_n < 50000, que correspondem aos valores de cada moeda. Pode haver quebras de linha e espaços extras entre os números e após os mesmos.

A entrada termina quando m = 0, caso que não deve ser processado.

Saída

A saída consiste de tantas linhas quantos casos de teste houver. Em cada linha, deve ser impresso o menor número de moedas necessário para comprar o produto correspondente àquele caso. Se em algum caso não for possível utilizar as moedas para chegar exatamente ao valor solicitado, escreva ``Impossivel'' (sem aspas e sem acento).

Exemplo

Entrada:
1000 2
35 150
110 3 20 30 60
3 2 2 9
0

Saída:
22
3
Impossivel

Adicionado por:Wanderley Guimarăes
Data:2008-07-08
Tempo limite:2.130s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Torneio Interno 2003 - UFRJ

hide comments
2016-11-27 00:11:57 Kleber Vianna [FATEC/SP]
Há muitos artigos na internet sobre o problema MOEDAS do SPOJ, mas em todos eles os autores escondem o jogo de como resolvê-lo com explicações supérfluas e incompletas que só confundem e o código apresentado é de difícil entendimento para quem não sabe a estratégia adotada. Depois de muito procurar só achei um que dava uma tênue ideia de como implementar a solução.
Para acabar com isso, vou aqui entregar o ouro. Crie um vetor ("qm") onde o índice representará os valores inteiros de zero até o preço (o SPOJ chama de "m" e sugere que seja um vetor de 50000 posições, p.ex., qm[50000]). A posição zero será preenchida com zero significando que são necessárias zero moedas para pagar um preço de zero tostões. Use um flag para preencher as posições impossíveis de terem um número de moedas sem troco. Para simplificar a programação, escolha um valor alto como o inteiro máximo da linguagem escolhida ou 50001 ou preço+1. As restantes posições do vetor devem ser preenchidas com
1+qm[i-v[j]],
onde "v" é o vetor com os valores das moedas, se qm[i-v[j]] não for impossível.
2016-04-29 03:57:55
A resposta do primeiro caso de teste não está errada.
2016-04-05 14:34:17 Daniel
A resposta do primeiro caso de teste de exemplo está errada a solução é impossível.
2012-10-17 13:45:51 Flavio Bogila
Todos os testes que fiz funcionaram, năo sei onde posso estar errando =(
2010-12-18 16:37:19 Lucas Porto Maziero [UNIS]


Last edit: 2011-02-12 19:43:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.