Solução problema UVA: 147 - Dollars (PYTHON)

Solução problema UVA: 147 - Dollars (PYTHON)

O problema consiste basicamente em identificar, dadas as moedas existentes ($100, $50, $20, $10, and $5 notes and $2, $1, 50c, 20c, 10c and 5c) e dado um certo valor, de quantas formas diferentes pode-se obter este valor através das moedas citadas.

Link do Problema: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=83


Basicamente, a solução consiste de um contador de um contador de possibilidades individuais combinado, ou seja, quantas vezes cada moeda pode formar o valor de entrada.

Solução:

#retorna a quantidade de possibilidades
#moedas de 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 centavos
maxvalue = 30000+1
memo = [maxvalue]
N = 0
inteiro = 0
decimal = 0
cents = 0
i = 0
#sem usar nenhuma moeda (apenas o valor 0 eh obtido)
memo[0] = 1
for i in range(1, maxvalue):
    memo.insert(i, 0)
#incluir moedas de $1
#for i in range(1, maxvalue):
#    memo.insert(i, 1)
   
#incluir moedas de 5c
for i in range(5, maxvalue):
    memo[i] += memo[i-5]
#incluir moedas de 10c
for i in range(10, maxvalue):
    memo[i] += memo[i-10]
   
#incluir moedas de 20c
for i in range(20, maxvalue):
    memo[i] += memo[i-20]
#incluir moedas de 50c
for i in range(50, maxvalue):
    memo[i] += memo[i-50]
#incluir moedas de $1
for i in range(100, maxvalue):
    memo[i] += memo[i-100]
#incluir moedas de $2
for i in range(200, maxvalue):
    memo[i] += memo[i-200]
#incluir moedas de $5
for i in range(500, maxvalue):
    memo[i] += memo[i-500]
   
#incluir moedas de $10
for i in range(1000, maxvalue):
    memo[i] += memo[i-1000]
#incluir moedas de $20
for i in range(2000, maxvalue):
    memo[i] += memo[i-2000]
#incluir moedas de $50
for i in range(5000, maxvalue):
    memo[i] += memo[i-5000]
   
#incluir moedas de $100
for i in range(10000, maxvalue):
    memo[i] += memo[i-10000]

cond = True
while cond:
    N = input()
    inteiro, decimal = N.split(".")
    cents = (100 * int(inteiro) ) + (10 * int(decimal) )
   
    if cents==0:
        cond = False
       
   
    if cents > maxvalue:
        cond = False
    else:
        if cents>=0 and cents<=maxvalue:
            print ( memo[cents] )
        else:
            cond = False
         
Recente
Anterior
Próximo Post »