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

Envío 6562

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

  • Autor: bryancalisto
  • Fecha: 2022-08-06 20:09:36 UTC (Hace alrededor de 2 meses)
Caso # Resultado Tiempo Memoria
#1
Incorrecto
0.037 s 3 KBi
#2
Incorrecto
0.047 s 3 KBi
#3
Incorrecto
0.021 s 3 KBi
#4
Incorrecto
0.022 s 3 KBi
#5
Incorrecto
0.077 s 3 KBi
#6
Incorrecto
0.083 s 3 KBi
#7
Incorrecto
0.072 s 3 KBi
#8
Incorrecto
0.071 s 3 KBi
#9
Tiempo límite excedido
1.58 s 3 KBi
#10
Tiempo límite excedido
1.558 s 3 KBi
#11
Tiempo límite excedido
1.575 s 3 KBi
#12
Incorrecto
1.233 s 3 KBi
#13
Tiempo límite excedido
1.525 s 3 KBi
#14
Tiempo límite excedido
1.572 s 3 KBi
#15
Incorrecto
0.096 s 3 KBi
Puntos totales: 0 / 100

Código

N = int(input())
monedas = list(map(int, input().split(' ')))
M = int(input())
todosLosValores = 10001  # +1 porque incluye el 0

tbl = [[0] * N] * todosLosValores

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(todosLosValores):
    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])