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

Envío 6611

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

  • Autor: rpedrazacoello
  • Fecha: 2022-09-03 21:31:49 UTC (Hace alrededor de 1 mes)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.171 s 14 KBi
#2
Tiempo límite excedido
1.052 s 125 KBi
#3
Correcto
0.169 s 15 KBi
#4
Correcto
0.143 s 14 KBi
#5
Tiempo límite excedido
1.075 s 125 KBi
#6
Tiempo límite excedido
1.014 s 125 KBi
#7
Error en tiempo de ejecución (NZEC)
Exited with error status 137
run: line 1:     3 Killed                  /usr/local/openjdk13/bin/java Main
0.97 s 125 KBi
#8
Tiempo límite excedido
1.084 s 103 KBi
#9
Tiempo límite excedido
1.056 s 71 KBi
#10
Tiempo límite excedido
1.099 s 106 KBi
#11
Tiempo límite excedido
1.051 s 83 KBi
#12
Tiempo límite excedido
1.118 s 104 KBi
#13
Tiempo límite excedido
1.018 s 78 KBi
#14
Tiempo límite excedido
1.12 s 111 KBi
#15
Tiempo límite excedido
1.057 s 103 KBi
Puntos totales: 20 / 100

Código

import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static HashMap<String, Integer> memoization = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] coins = new int[n];

        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }

        int noConsultas = scanner.nextInt();
        int[] consultas = new int[noConsultas];
        for (int i = 0; i < noConsultas; i++) {
            consultas[i] = scanner.nextInt();
        }

        for (int i = 0; i < noConsultas; i++) {
            System.out.println(dpCountCoins(-1, coins, consultas[i]));
        }

    }

    public static int dpCountCoins(int currentCoin, int[] coins, int totalAmount) {
        String key = currentCoin + "-" + totalAmount;
        if (memoization.containsKey(key)) {
            return memoization.get(key);
        }

        if (totalAmount == 0) {
            return 1;
        }

        if (totalAmount < 0) {
            return 0;
        }

        if (currentCoin >= coins.length) {
            return 0;
        }

        int count = 0;

        int coinValue = currentCoin >=0 ? coins[currentCoin] : 0;
        int localAmount = totalAmount - coinValue;
        while (localAmount > 0) {
            for (int i = currentCoin + 1; i <= coins.length; i++) {
                count += dpCountCoins(i, coins, localAmount);
            }
            localAmount = currentCoin >=0 ? localAmount - coinValue : -1;
        }

        if(localAmount == 0){
            count++;
        }

        memoization.put(key, count);
        return count;
    }
}