Untitled

mail@pastecode.io avatar
unknown
java
2 years ago
1.4 kB
1
Indexable
Never
import java.util.*;

class Main {
    public static void main(String[] args) {
        System.out.println("Hello, World!");
        Scanner in = new Scanner(System.in);
       
        int N = in.nextInt();
        int M = in.nextInt();
       
        Map<Integer, Map<Integer, Integer>> memory = new HashMap<>();
       
        System.out.println(dfs(N, M, memory, 10));
    }
   
    public static int dfs(int N, int M, Map<Integer, Map<Integer, Integer>> memory, int denomination) {
        if(memory.containsKey(N) && memory.get(N).get(M) != null)
            return memory.get(N).get(M);
        if(N == 0 && M == 0) return 1;
        if(N == 0 || M < 10) {
            memory.computeIfAbsent(N, k -> new HashMap<Integer, Integer>()).put(M, 0);
            return 0;
        }
        int res = 0;
       
        switch(denomination) {
            case 10:
                res += dfs(N-1, M-10, memory, 10);
                res += dfs(N-1, M-30, memory, 30);
                res += dfs(N-1, M-50, memory, 50);
                break;
            case 30:
                res += dfs(N-1, M-30, memory, 30);
                res += dfs(N-1, M-50, memory, 50);
                break;
            case 50:
                res += dfs(N-1, M-50, memory, 50);
                break;
        }
       
        memory.computeIfAbsent(N, k -> new HashMap<Integer, Integer>()).put(M, res);
       
       
        return res;
    }
}