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

Envío 6610

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

  • Autor: rpedrazacoello
  • Fecha: 2022-09-03 21:31:28 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#2
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#3
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#4
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#5
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#6
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#7
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#8
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#9
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#10
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#11
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#12
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#13
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#14
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
#15
Error de compilación 
                      Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                  ^
  symbol:   class HashMap
  location: class Main
Main.java:3: error: cannot find symbol
    public static HashMap<String, Integer> memoization = new HashMap<>();
                                                             ^
  symbol:   class HashMap
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
        ^
  symbol:   class Scanner
  location: class Main
Main.java:6: error: cannot find symbol
        Scanner scanner = new Scanner(System.in);
                              ^
  symbol:   class Scanner
  location: class Main
4 errors
Puntos totales: 0 / 100

Código

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;
    }
}