public class MiniMaxOptiCarnet {


	// J'aime bien les majuscules
	public static boolean True = true;
	public static boolean False = false;

	/*
	Variable donnant le nombre d'allumettes au départ du jeu (remplacée par un argument en ligne de commande)
	 */
	public static int[] tests = {5,11,17,42,100};

	private static int[] J1;
	private static int[] J2;

    static long debut;
	private static int compteur;
	private static int limite;

	public static void main(String[] args) {
		limite = 0;
		try {
			for(int n: tests) {
				J1 = new int[limite + 1];
				J2 = new int[limite + 1];
				compteur = 0;
				debut = System.nanoTime();
				compteur = 0;
				System.out.print(n + " allumettes : ");
				int s = Nim(n);
				if (s == 1) {
					System.out.print("Gagné ;");
				} else {
					System.out.print("Perdu ;");
				}
				long fin = System.nanoTime();
				System.out.print(" Temps écoulé (ms) : "+((fin-debut)/1000000)+" ;");
				System.out.println(" Compteur = " + compteur);
			}
		} catch (StackOverflowError e){
		}
		System.out.println(limite-1);
	}

	public static int Nim(int n){
		return exploreMax(n);
	}

	/*
	Vérifie les issues des coups jouables par le J1 et renvoie 1 si le J1 a une opportunité de gagner a coup sur
	Vérifie si le coup a déjà été joué avant de continuer l'arbre, si il verifie l'arbre il ajoute au tableau
	 */
	public static int exploreMax(int allumette) {
		compteur++;
		if (J1[allumette] != 0){
			return J1[allumette];
		}
		int n = allumette;
		int max = -1;
		for (int i=0;allumette>1&&i<3;i++){
			allumette--;
			int v=exploreMin(allumette);
			if (v > max){
				max = v;
			}
		}
		J1[n] = max;
		return max;
	}


	/*
	Vérifie les issues possibles des coups du J2 et renvoie -1 si le J2 a une opportunité de gagner a coup sur
	Vérifie si le coup a déjà été joué avant de continuer l'arbre, si il verifie l'arbre il ajoute au tableau
	 */
	public static int exploreMin(int allumette){
		compteur++;
		if (J2[allumette] != 0){
			return J2[allumette];
		}
		int n = allumette;
		int min = 1;
		for (int i=0;allumette>1&&i<3;i++){
			allumette--;
			int v=exploreMax(allumette);
			if (v < min){
				min = v;
			}
		}
		J2[n] = min;
		return min;
	}

}