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

Envío 6609

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

  • Autor: rpedrazacoello
  • Fecha: 2022-09-03 21:31:08 UTC (Hace 28 días)
Caso # Resultado Tiempo Memoria
#1
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#2
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#3
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#4
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#5
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#6
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#7
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#8
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#9
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#10
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#11
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#12
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#13
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#14
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

                    
#15
Error de compilación
                      main.c:1:1: error: unknown type name 'public'
public class Main {
^
main.c:1:13: error: expected ';' after top level declarator
public class Main {
            ^
            ;
2 errors generated.

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