import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;

public class LeJeuAllumette {
    public static void main(String[] args){
	Intelligence intelligence = new Intelligence();
	Jeu jeu = new JeuDecore(new JeuConcret(5),intelligence);
	Joueur[] joueur = new Joueur[]{new Humain("aaa"), new Ordi(intelligence,"toto")}; 
	/*	Joueur[] joueur = new Joueur[]{
	    new Ordi(((JeuDecore)jeu).intelligence),
	    new Ordi(((JeuDecore)jeu).intelligence)
	}; 
	*/
	for  (int i= 0; i<100; i++) {
	    System.out.println(jeu);
	    int tour = 0;
	    while (!jeu.fin()) {
		int coup;
		do {
		    System.out.print("Joueur " + joueur[tour] + "> " );
		    coup = joueur[tour].joue(jeu.etat());
		    System.out.println("\tcoup = " + coup);
		}
		while(!jeu.jouer(coup));
		System.out.println(jeu);
		tour = tour==0?1:0;
	    }
	    System.out.println("Joueur " + joueur[tour==0?1:0]  + " gagnant !");
	    jeu.reset(5);
	}
    }
}

interface Joueur {
    public int joue(Couple couple);
}

class Humain implements Joueur {
    Scanner sc = new Scanner(System.in);
    String nom;

    public Humain (String nom) {
	this.nom = nom;
    }

    public int joue(Couple couple) {
	return sc.nextInt();
    }

    public String toString() {
	return nom;
    }
}

class Ordi implements Joueur {
    Intelligence intelligence;
    String nom;

    public Ordi(Intelligence i, String nom) {
	intelligence = i;
	this.nom = nom;
    }

    public int joue(Couple couple) {
	int nbAllumette = couple.a;
	int possible = couple.b;

	int coup = 1;
	int valCoup = intelligence.get(nbAllumette-1,2);
	
	for (int choix = 2; choix <= possible; choix++) {
	    int valChoix  = intelligence.get(nbAllumette-choix,2*choix);
	    if (valChoix>valCoup) {
		coup = choix;
		valCoup = valChoix;
	    }
	}
	
	return coup;
    }

    public String toString() {
	return nom + "*";
    }
    
}


class Intelligence {
    HashMap<Couple,Integer> memoire = new HashMap<Couple,Integer>();

    public void update(ArrayList<Couple> partie) {
	boolean gagnant = false;
	for (int i= partie.size()-1; i>=0; i--) {
	    update(partie.get(i),gagnant?-1:1);
	    gagnant = ! gagnant;
	}
    }

    private void update(Couple couple, int n) {
	Integer val = memoire.get(couple);

	if (val == null)
	    memoire.put(couple,n);
	else
	    memoire.put(couple,n+val);
    }

    public int get(int a, int b) {
	if (a <=b )
	    b = a;
	Integer val = memoire.get(new Couple(a,b));
	return val == null ? 0: val;
    }

    public String toString() {
	return memoire.toString();
    }
}


interface Jeu {
    public boolean fin();
    public boolean jouer(int n);
    public Couple etat();
    public void reset(int n);
}

class JeuDecore implements Jeu {
    Jeu jeu;
    Intelligence intelligence;
 
    ArrayList<Couple> partie = new ArrayList<Couple>();

    public JeuDecore(Jeu jeu, Intelligence intelligence) {
	this.jeu = jeu;
	partie.add(jeu.etat());
	this.intelligence = intelligence;
    }

    public void reset(int n) {
	if (fin())
	    intelligence.update(partie);

	System.out.println(intelligence);

	jeu.reset(n);

	partie.clear();
	partie.add(jeu.etat());
    }

    public boolean fin() {
	return jeu.fin();
    }

    public boolean jouer(int n) {
	boolean ok = jeu.jouer(n);
	if (ok) {
	    partie.add(jeu.etat());
	}
	return ok;
    }

    public Couple etat() {
	return jeu.etat();
    }

    public String toString() {
	return jeu.toString() + "\t" + partie.toString();
    }
}

class Couple {
    int a;
    int b;

    Couple (int a, int b) {
	this.a = a;
	this.b = b;
    }

    public String toString() {
	return a + ":" + b;
    }

    public int hashCode() {
	return a + 29*b;
    }

    public boolean equals(Object o) {
	if (o == null || ! (o instanceof Couple))
	    return false;
	else {
	    Couple couple = (Couple) o;
	    return a ==  couple.a && b == couple.b; 
	}
    }
}


class JeuConcret implements Jeu {
    int nbAllumettes;
    int possible;

    public JeuConcret (int n) {
	nbAllumettes = n;
	possible = n-1;
    }

    public void reset(int n) {
	nbAllumettes = n;
	possible = n-1;       
    }

    public boolean fin() {
	return nbAllumettes == 0;
    }

    public boolean jouer(int n) {
	if (n>possible || n<=0)
	    return false;
	else {
	    nbAllumettes -= n;
	    possible = 2*n>=nbAllumettes ? nbAllumettes: 2*n;
	    return true;
	}
    }

    public Couple etat() {
	return new Couple(nbAllumettes, possible);
    }

    public String toString() {
	return nbAllumettes + ":" + possible;
    }
}