// RahaJako.java SJ
// Vaihtorahaongelma esimerkkina algoritmistrategioista

import java.util.*;
import java.lang.RuntimeException;

public class RahaJako {

    public static void main(String[] args) {

        // Ensimmäinen paratri on rahamäärä
        int rahamaara = 25;

        if (args.length > 0)
            rahamaara = Integer.valueOf(args[0]);

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

        // loput parametrit tulkitaan kolikoksi
        for (int i = 1; i < args.length; i++)
            Kolikot.add(Integer.valueOf(args[i]));

        // jollei kolikoita ollut, laitetaan eurosentit
        if (Kolikot.size() == 0) {
            Kolikot.add(1);
            Kolikot.add(2);
            Kolikot.add(5);
            Kolikot.add(10);
            Kolikot.add(20);
            Kolikot.add(50);
        }

        Ajastin a;
        int n;

        System.out.println("Kolikot: " + Kolikot);

        a = new Ajastin("Ahne_" + rahamaara);
        n = ahnejako(rahamaara, Kolikot);
        a.stop();
        System.out.println(a + " kolikkoja: " + n);

        if (rahamaara < 36) {
            a = new Ajastin("Hajoita-ja-hallitse_" + rahamaara);
            n = hajhalljako(rahamaara, Kolikot);
            a.stop();
            System.out.println(a + " kolikkoja: " + n);
        }

        a = new Ajastin("Dynaaminen_" + rahamaara);
        n = dynjako(rahamaara, Kolikot);
        a.stop();
        System.out.println(a + " kolikkoja: " + n);


    }

    // Ahne algoritmi
    static int ahnejako(int rahamaara, Collection<Integer> Kolikot) {
        int[] kol = new int[Kolikot.size()];
        int n = 0;
        for (int c : Kolikot)
            kol[n++] = c;
        java.util.Arrays.sort(kol);

        int r = 0;
        while (rahamaara > 0) {

            // valitaan suurin mahdollinen kolikko
            for (int j = n-1; j >= 0; j--) {
                if (kol[j] <= rahamaara) {
                    rahamaara -= kol[j];    // löytyi
                    r++;
                    break;
                }
                if (j == 0)
                    throw new RuntimeException("Ei riittävän pientä kolikkoa");
            }
        }
        return r;
    }

    // Hajoita-ja-hallitse
    // TODO: ei havaitse mahdotonta tehtävää
    static int hajhalljako(int rahamaara, Iterable<Integer> Kolikot) {
        if (rahamaara == 0)
            return 0;
        int tulos = rahamaara;		// yläraja
        for(Integer c : Kolikot)	// kolikkojen arvojen läpikäynti
            if (c <= rahamaara) {
                int r = hajhalljako(rahamaara - c, Kolikot) + 1;
                if (r < tulos)
                    tulos = r;
            }
        return tulos;
    }

    // Dynaaminen ratkaiseminen
    // TODO: ei havaitse mahdotonta tehtävää
    static int dynjako(int rahamaara, Iterable<Integer> Kolikot) {
        int[] ratkaisut = new int[rahamaara+1];
        ratkaisut[0] = 0;
        // haetaan ja talletetaan kaikki osaratkaisut
        for (int i = 1; i <= rahamaara; i++) {
            int min = i+1;
            // kullakin kolikolla
            for(Integer c : Kolikot) {
                if (c <= i) {
                    int r = ratkaisut[i-c]+1;
                    if (r < min)
                        min = r;
                }
            }
            ratkaisut[i] = min;
        }
        // vastaus alkuperäiseen tehtävään
        return ratkaisut[rahamaara];
    }
}