(UVA) e-Coins - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1247

The solution below used the concept of Coin Change, related to Dynamic Programming, to solve this problem.


import java.io.*;
import java.util.*;

class Main {
    public int emodulus;
    public ECoin[] coins;
    public int[][][] matrix;
   
    public int coinChange(int conventionalValue, int ITValue, int indexCoin) {
        int result = conventionalValue*conventionalValue+ITValue*ITValue;
        if (result == emodulus) {
            return 0;
        }
        else if (result > emodulus || indexCoin < 0) {
            return 1000000000;
        }
       
        if (matrix[conventionalValue][ITValue][indexCoin] != -1) {
            return matrix[conventionalValue][ITValue][indexCoin];
        }
       
        int use = coinChange(conventionalValue+coins[indexCoin].convValue, ITValue+coins[indexCoin].ITValue, indexCoin) + 1;
        int notUse = coinChange(conventionalValue, ITValue, indexCoin-1);
        matrix[conventionalValue][ITValue][indexCoin] = Math.min(use, notUse);
        return matrix[conventionalValue][ITValue][indexCoin];
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numProblems = sc.nextInt();
        for (int i = 0; i < numProblems; i++) {
            int numCoins = sc.nextInt();
            emodulus = sc.nextInt();
            emodulus *= emodulus; // no need for sqrt later
           
            coins = new ECoin[numCoins];
            for (int j = 0; j < numCoins; j++) {
                int v1 = sc.nextInt();
                int v2 = sc.nextInt();
                coins[j] = new ECoin(v1, v2);
            }
           
            matrix = new int[301][301][41];
            for (int j = 0; j < 301; j++) {
                for (int k = 0; k < 301; k++) {
                    for (int l = 0; l < 41; l++) {
                        matrix[j][k][l] = -1;
                    }
                }
            }
           
            int numCoinsAnswer = coinChange(0, 0, numCoins-1);
            if (numCoinsAnswer == 2000000000) {
                bw.write("not possible\n");
            }
            else {
                bw.write(numCoinsAnswer+"\n");
            }
        }
               
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class ECoin {
    int convValue;
    int ITValue;
   
    public ECoin(int v1, int v2) {
        convValue = v1;
        ITValue = v2;
    }
}