import java.util.*;

public class Peli {
    static HashMap<ArrayList<Integer>, Boolean> muisti = new HashMap<>();

    // Aikavaativuus: O(TULO(pinot) * SUMMA(pinot) * |pinot|)
    static boolean voittaako(ArrayList<Integer> pinot) {
        boolean tyhja = true;
        for(int pino : pinot) {
            if(pino != 0) tyhja = false;
        }
        if(tyhja) return false;

        if(muisti.containsKey(pinot)) {
            return muisti.get(pinot);
        }

        // voitamme <=> on olemassa siirto, jonka jälkeen vastustaja häviää
        boolean tulos = false;
        for(int i = 0; i < pinot.size(); ++i) {
            for(int poisto = 1; poisto <= pinot.get(i); ++poisto) {
                if(poisto == 2) continue;
                ArrayList<Integer> uudetPinot = new ArrayList<>(pinot);
                uudetPinot.set(i, uudetPinot.get(i) - poisto);
                Collections.sort(uudetPinot);
                if(!voittaako(uudetPinot)) {
                    tulos = true;
                }
            }
        }

        muisti.put(pinot, tulos);
        return tulos;
    }

    static ArrayList<Integer> siirto(ArrayList<Integer> pinot) {
        ArrayList<Integer> havioSiirto = null;

        for(int i = 0; i < pinot.size(); ++i) {
            for(int poisto = 1; poisto <= pinot.get(i); ++poisto) {
                if(poisto == 2) continue;
                ArrayList<Integer> uudetPinot = new ArrayList<>(pinot);
                uudetPinot.set(i, uudetPinot.get(i) - poisto);
                if(!voittaako(uudetPinot)) {
                    return uudetPinot;
                }
                havioSiirto = uudetPinot;
            }
        }

        return havioSiirto;
    }

    public static void main(String[] args) {
        ArrayList<Integer> pinot = new ArrayList<>();
        pinot.add(10);
        pinot.add(12);
        pinot.add(13);
        pinot.add(4);

        long alku = System.nanoTime();
        boolean tulos = voittaako(pinot);
        long loppu = System.nanoTime();

        System.out.println("Voitammeko? " + tulos);
        System.out.println("Aika " + (loppu - alku) * 1e-9 + " s");

        boolean meidanVuoro = true;
        while(true) {
            for(int pino : pinot) {
                System.out.print(pino + " ");
            }
            if(meidanVuoro) {
                System.out.println("-> meidän vuoro");
            } else {
                System.out.println("-> vastustajan vuoro");
            }

            pinot = siirto(pinot);
            if(pinot == null) {
                if(meidanVuoro) {
                    System.out.println("Hävisimme");
                } else {
                    System.out.println("Voitimme");
                }
                break;
            }

            meidanVuoro = !meidanVuoro;
        }
    }
}