import java.util.*;

public class TRAII_24_t21_22_skeleton {

    public static void main(String[] args) {

        // defaults
        int sum = 80;

        if (args.length > 0)
            sum = Integer.parseInt(args[0]);

        Vector<Integer> coins = new Vector<Integer>();

        for (int i = 1; i < args.length; i++)
            coins.add(Integer.valueOf(args[i]));

        if (coins.isEmpty()) {
            coins.add(1);
            coins.add(2);
            coins.add(5);
            coins.add(10);
            coins.add(40);
            coins.add(50);
        }

        int n;

        // call the examples that return only number of coins needed

        n = greedyCoins(sum, coins);
        System.out.println("Greedy: number of coins=" + n);

        if (sum < 37) {
            n = dacCoins(sum, coins);
            System.out.println("Divide_and_conquer: number of coins=" + n);
        }

        n = dynCoins(sum, coins);
        System.out.println("Dynamic: number of coins=" + n);


        Collection<Integer> result = dynCoins21(sum, coins);
        System.out.println("Dyn21: coins=" + result);



        result = dacCoins22(sum, coins);
        System.out.println("DaC22: coins=" + result);


    }


    /**
     * Dynamic coins.
     * @param sum amount to give
     * @param coins available coins
     * @return the coins to give
     */
    static Collection<Integer> dynCoins21(int sum, Collection<Integer> coins) {
        Collection<Integer> result = new ArrayList<>();

        // TODO

        return result;
    }



    /**
     * Divide-and-conquer coins.
     * @param sum amount to give
     * @param coins available coins
     * @return the coins to give
     */
    static Collection<Integer>  dacCoins22(int sum, Collection<Integer> coins) {
        Collection<Integer> result = new ArrayList<>();

        // TODO

        return result;
    }


    static int greedyCoins(int sum, Collection<Integer> coins) {
        int[] coin = new int[coins.size()];
        int n = 0;
        for (int c : coins)
            coin[n++] = c;
        Arrays.sort(coin);

        int r = 0;
        while (sum > 0) {
            // choose largest possible coin
            for (int j = n-1; j >= 0; j--) {
                if (coin[j] <= sum) {
                    sum -= coin[j];
                    r++;
                    break;
                }
            }
        }
        return r;
    }





    /**
     * Divide-and-conquer coins.
     * @param sum amount to give
     * @param coins available coins
     * @return number of coins needed
     */
    static int dacCoins(int sum, Collection<Integer> coins) {
        if (sum == 0)
            return 0;
        int result = sum;		// upper limit
        for(Integer c : coins)	// iterate over coins
            if (c <= sum) {
                int r = dacCoins(sum - c, coins) + 1;
                if (r < result)
                    result = r;
            }
        return result;
    }

    /**
     * Dynamic coins.
     * @param sum amount to give
     * @param coins available coins
     * @return number of coins needed
     */
    static int dynCoins(int sum, Collection<Integer> coins) {
        int[] results = new int[sum+1];
        results[0] = 0;
        for (int i = 1; i <= sum; i++) {
            int min = i+1;
            for(Integer c : coins) {
                if (c <= i) {
                    int r = results[i-c]+1;
                    if (r < min)
                        min = r;
                }
            }
            results[i] = min;
        }
        return results[sum];
    }
}