import java.util.Scanner;

public class ChangeMaker {
    public static void main(String[] args) {
        int[] result, resultGreedy;
        int numberOfCoins, n, numberOfCoinsGreedy;

        Scanner input = new Scanner(System.in);

        System.out.println("Enter the number of coins-denominations and the set of coin values:");

        int k = input.nextInt();
        int[] d = new int[k];

        for (int i = 0; i < k; i++) {
            d[i] = input.nextInt();
        }

        do {
            numberOfCoins = 0;
            numberOfCoinsGreedy = 0;
            System.out.println("\nEnter a positive amount to be changed (enter 0 to quit):");
            n = input.nextInt();
            result = change_DP(n, d);
            resultGreedy = change_greedy(n, d);
            int[][] printedDP = new int[2][result.length];
            int[][] printedGreedy = new int[2][result.length];

            for (int i = 0; i < result.length; i++) {
                numberOfCoins += result[i];
                numberOfCoinsGreedy += resultGreedy[i];
                if (result[i] > 0) {
                    printedDP[0][i] = result[i];
                    printedDP[1][i] = d[i];
                    printedGreedy[0][i] = resultGreedy[i];
                    printedGreedy[1][i] = d[i];
                }
            }

            System.out.println("\nDP algorithm results");
            System.out.println("Amount: " + n);
            System.out.print("Optimal coin distribution: ");

            for (int i = 0; i < printedDP[0].length - 1; i++) {
                if (printedDP[0][i] > 0) {
                    System.out.print(printedDP[0][i] + "*" + printedDP[1][i] + "c + ");
                }
            }

            System.out.println(printedDP[0][printedDP[0].length - 1] + "*" + printedDP[1][printedDP[0].length - 1] + "c");
            System.out.println("Optimal coin count: " + numberOfCoins);

            System.out.println("\nGreedy algorithm results");
            System.out.println("Amount: " + n);
            System.out.print("Optimal coin distribution: ");

            for (int i = 0; i < printedGreedy[0].length - 1; i++) {
                if (printedDP[0][i] > 0) {
                    System.out.print(printedGreedy[0][i] + "*" + printedGreedy[1][i] + "c + ");
                }
            }

            System.out.println(printedGreedy[0][printedGreedy[0].length - 1] + "*" + printedGreedy[1][printedGreedy[0].length - 1] + "c");
            System.out.println("Optimal coin count: " + numberOfCoinsGreedy);


        } while (n > 0);


    }

    public static int[] change_greedy(int n, int[] d) {
        int i;
        int [] result = new int[d.length];

        while (n > 0) {
            for (i = 0; i < d.length; i++) {
                if (d[i] < n) {
                    break;
                }
            }

            result[i] = (n - (n % d[i])) / d[i];
            n = n - result[i] * d[i];
        }

        return result;
    }

    public static int[] change_DP(int n, int[] d) {
        int[] A = new int[n + 1];
        int[] C = new int[n + 1];
        int[] B = new int[d.length];

        C[0] = 0;

        for (int j = 1; j < n + 1; j++) {
            int min = Integer.MAX_VALUE;
            int chosen = 0;

            for (int i = 0; i < d.length; i++) {
                if (j >= d[i]) {
                    if (C[j - d[i]] <= min) {
                        min = C[j - d[i]];

                        chosen = i;
                    }
                }
            }

            C[j] = 1 + min;
            A[j] = chosen;
        }

        while (n > 0) {
            B[A[n]] += 1;
            n -= d[A[n]];
        }
        return B;
    }
}