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

Envío 6561

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

  • Autor: bryancalisto
  • Fecha: 2022-08-06 01:25:21 UTC (Hace alrededor de 2 meses)
Caso # Resultado Tiempo Memoria
#1
Incorrecto
0.015 s 3 KBi
#2
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 33, in <module>
    print(contar(valor, monedas) % 1000000007)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  [Previous line repeated 995 more times]
  File "script.py", line 7, in contar
    if valor == 0:
RecursionError: maximum recursion depth exceeded in comparison
0.019 s 4 KBi
#3
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 33, in <module>
    print(contar(valor, monedas) % 1000000007)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  [Previous line repeated 995 more times]
  File "script.py", line 7, in contar
    if valor == 0:
RecursionError: maximum recursion depth exceeded in comparison
0.022 s 4 KBi
#4
Correcto
0.014 s 3 KBi
#5
Correcto
0.066 s 4 KBi
#6
Incorrecto
0.075 s 8 KBi
#7
Incorrecto
0.087 s 9 KBi
#8
Incorrecto
0.08 s 7 KBi
#9
Correcto
0.732 s 4 KBi
#10
Tiempo límite excedido
1.572 s 7 KBi
#11
Tiempo límite excedido
1.571 s 10 KBi
#12
Incorrecto
0.719 s 7 KBi
#13
Correcto
1.21 s 4 KBi
#14
Tiempo límite excedido
1.574 s 6 KBi
#15
Error en tiempo de ejecución (NZEC)
Exited with error status 1
Traceback (most recent call last):
  File "script.py", line 33, in <module>
    print(contar(valor, monedas) % 1000000007)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  File "script.py", line 19, in contar
    combs += contar(valor - moned, monedas)
  [Previous line repeated 995 more times]
  File "script.py", line 7, in contar
    if valor == 0:
RecursionError: maximum recursion depth exceeded in comparison
0.014 s 4 KBi
Puntos totales: 27 / 100

Código

mem = {}


def contar(valor, monedas):
    global mem

    if valor == 0:
        return 1

    if valor < 0:
        return 0

    if valor in mem:
        return mem[valor]

    combs = 0

    for moned in monedas:
        combs += contar(valor - moned, monedas)

    mem[valor] = combs

    return combs


N = int(input())
monedas = list(map(int, input().split(' ')))
M = int(input())

for i in range(M):
    valor = int(input())

    print(contar(valor, monedas) % 1000000007)