█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 6563

Problema 0xcb - Contar maneras de formar una cantidad con monedas

  • Autor: bryancalisto
  • Fecha: 2022-08-06 20:27:27 UTC (Hace alrededor de 2 meses)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.039 s 5 KBi
#2
Correcto
0.049 s 5 KBi
#3
Correcto
0.035 s 4 KBi
#4
Correcto
0.024 s 4 KBi
#5
Correcto
0.075 s 4 KBi
#6
Correcto
0.071 s 4 KBi
#7
Correcto
0.074 s 4 KBi
#8
Correcto
0.074 s 4 KBi
#9
Tiempo límite excedido
1.59 s 44 KBi
#10
Tiempo límite excedido
1.583 s 108 KBi
#11
Tiempo límite excedido
1.569 s 102 KBi
#12
Tiempo límite excedido
1.574 s 98 KBi
#13
Correcto
1.453 s 44 KBi
#14
Tiempo límite excedido
1.57 s 87 KBi
#15
Correcto
0.107 s 5 KBi
Puntos totales: 67 / 100

Código

N = int(input())
monedas = list(map(int, input().split(' ')))
M = int(input())
nValores = 10001  # Segun constraint de maximo valor y +1 porque incluye el 0

tbl = [[0 for i in range(N)] for j in range(nValores)]

for iMoneda in range(N):  # Si tienes un valor de 0 (fila 0), necesitas solo un set para representar ese valor: {}
    tbl[0][iMoneda] = 1

for valor in range(nValores):
    for iMoneda in range(N):
        if iMoneda > 0:
            tbl[valor][iMoneda] = tbl[valor][iMoneda-1]

        restante = valor - monedas[iMoneda]

        if restante >= 0:
            tbl[valor][iMoneda] = (tbl[valor][iMoneda] + tbl[restante][iMoneda]) % 1000000007


for i in range(M):
    valor = int(input())
    print(tbl[valor][N - 1])