// This class illustrates techniques for calculating the number of different 
//  combinations of coins that can be used to reach a specific amount of money.
// In England the currency is made up of pounds, £ (dollars), and pence, p (pennies).
// There are commonly 8 types of coins in general circulation:
// 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

/**
 *  This is serious brute force. It's optimized a little bit because we are
 *   checking the limit for each coin counter.
 * 
 */ 

public class Problem031 {
    private static final boolean debug = false;

    public static int Solve(int pounds) {
        int result = 0;
        int i, j, total;               // 0   1   2   3    4    5    6     7
        int coins[] = new int[8];      // 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p
        int coinsMax[] = new int[8];   // 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p
        for (i = 0; i < 8; i++) {
            coins[i] = 0;
        }
        coinsMax[0] = 200;
        coinsMax[1] = 100;
        coinsMax[2] = 40;
        coinsMax[3] = 20;
        coinsMax[4] = 10;
        coinsMax[5] = 4;
        coinsMax[6] = 2;
        coinsMax[7] = 1;
        try {
            while (true) {
                total =   coins[0] * 1
                        + coins[1] * 2
                        + coins[2] * 5
                        + coins[3] * 10
                        + coins[4] * 20
                        + coins[5] * 50
                        + coins[6] * 100
                        + coins[7] * 200;
                if (total == (pounds * 100)) {
                    if (debug) {
                       for (int k = 0; k < coins.length; k++) { System.out.print(coins[k] + ", ");}
                       System.out.println(".");
                    }
                    result++;
                }
                for (i = 0; i < coins.length; i++) {
                    coins[i]++;
                    if (coins[i] > coinsMax[i]) {
                        if (i == coins.length - 1) {
                            throw new Exception("done");
                        }
                        coins[i] = 0;
                    } else {
                        break;
                    }
                }
            }
        } catch (Exception ex) {

            System.out.println("Solve(): + ex.");

        }
        return result;

    }
}