import java.util.*;

public class Kolikot {
    static final int ISO = 1000000000;
    static int[] kolikot;

    static ArrayList<Integer> montakoKolikkoa(int hinta) {
        // muisti[x] = montako kolikkoa tarvitaan x esittämiseen
        int[] muisti = new int[hinta + 1];
        muisti[0] = 0;
        for(int jaljella = 1; jaljella <= hinta; ++jaljella) {
            int tulos = ISO;
            for(int kolikko : kolikot) {
                if(kolikko > jaljella) continue;
                tulos = Math.min(tulos, muisti[jaljella - kolikko] + 1);
            }
            muisti[jaljella] = tulos;
        }

        ArrayList<Integer> tulos = new ArrayList<>();
        int jaljella = hinta;
        while(jaljella != 0) {
            for(int kolikko : kolikot) {
                if(kolikko > jaljella) continue;
                if(muisti[jaljella] == muisti[jaljella - kolikko] + 1) {
                    tulos.add(kolikko);
                    jaljella -= kolikko;
                    break;
                }
            }
        }
        return tulos;
    }

    public static void main(String[] args) {
        kolikot = new int[] {1, 3, 4};
        int hinta = 19;

        // Aikavaativuus: O(hinta * |kolikot|)
        // hinta * kolikot = 3 miljoonaa

        long alku = System.nanoTime();
        ArrayList<Integer> tulos = montakoKolikkoa(hinta);
        long loppu = System.nanoTime();

        System.out.println("Lukumäärä: " + tulos.size());
        System.out.print("Kolikot:");
        for(int kolikko : tulos) {
            System.out.print(" " + kolikko);
        }
        System.out.println();
        System.out.println("Aika: " + (loppu - alku) * 1e-9 + " s");
    }
}