import java.io.*;
import java.util.NoSuchElementException;

abstract class Ereignis implements Comparable
{
    float zeitpunkt;
    public int compareTo(Object o)
    {	float z = zeitpunkt - ((Ereignis)o).zeitpunkt;
        if (z>0) return +1;
        if (z<0) return -1;
	return 0;
    }
    
    abstract void bearbeite();

    Ereignis(float z) {zeitpunkt = z; }
}

class Simulation
{
    Statistik stat;
    Kassen kassen;
    KundenSchlange kundenSchl_a;
    KundenSchlange[] kundenSchl_b;
    Halde ereignisse;
    boolean einganggeschlossen = false;

    float mu, kundenzeit_a, kundenzeit_b;

    final boolean trace = false;

Simulation(int n, char version,
	   float mittlereAnkunftszeit, float a, float b,
	   float anfangszeit, float endzeit, int haldenGröße)
    {	kassen = new Kassen(n, anfangszeit);
        mu = mittlereAnkunftszeit; 
	kundenzeit_a = a; kundenzeit_b = b;
	stat = new Statistik();
	ereignisse = new Halde(haldenGröße);
	if(version=='a') {
	    kundenSchl_a = new KundenSchlange();
	    ereignisse.einfügen(new Kassenschluss(endzeit));
	    ereignisse.einfügen(new neuer_Kunde_a((float)(anfangszeit +
                 zeitZwischenKunden())));
	}
	else {
	    kundenSchl_b =  new KundenSchlange[n];
	    for (int i=0; i<n; i++) kundenSchl_b[i] = new KundenSchlange();
	    ereignisse.einfügen(new Kassenschluss(endzeit));
	    ereignisse.einfügen(new neuer_Kunde_b((float)(anfangszeit +
                 zeitZwischenKunden())));
	}
	while(!ereignisse.istleer())
	    ((Ereignis)(ereignisse.entferneMin())).bearbeite();
    }

public static void main(String[] args)
    {   System.out.println("gemeinsame Warteschlange. ");
	for (int i=1; i<=3; i++) {
	    Simulation s = new Simulation(3, 'a', 40, 10, 200,
					  9*3600, 19*3600, 100);
	    s.stat.druckeStatistik();
	}
	System.out.println("\ngetrennte Schlangen. ");
	for (int i=1; i<=3; i++) {
	    Simulation s = new Simulation(3, 'b', 40, 10, 200,
					  9*3600, 19*3600, 100);
	    s.stat.druckeStatistik();
	}
    }

class Kassefertig_a extends Ereignis
{   Kassefertig_a(float z) { super(z); }
    void bearbeite()
    {	if(trace) System.out.println("Kasse fertig. " + zeitpunkt);
        if (!kundenSchl_a.istleer()) {
	    Kunde k = kundenSchl_a.drankommen();
	    stat.bearbeiteKunde(zeitpunkt - k.ankunftszeit);
            ereignisse.einfügen(new Kassefertig_a
                   ((float)(zeitpunkt+zeitFürKundenAnKassa())));
	    // sparsamere Variante: Es wird kein neues Objekt erzeugt.
	    //   zeitpunkt += zeitFürKundenAnKassa();
	    //   ereignisse.einfügen(this);
	}
	else kassen.kasseWirdFrei_a(zeitpunkt);
    }
}
class Kassefertig_b extends Ereignis
{   int index; // = Index für Kundenschlange und Kasse
    Kassefertig_b(float z, int i) { super(z); index = i; }
    void bearbeite()
    {	if(trace) System.out.println("Kasse fertig. " + zeitpunkt);
        if (!kundenSchl_b[index].istleer()) {
          Kunde ku = kundenSchl_b[index].drankommen();
          stat.bearbeiteKunde(zeitpunkt - ku.ankunftszeit);
          ereignisse.einfügen(new Kassefertig_b
             ((float)(zeitpunkt+zeitFürKundenAnKassa()), index));
	}
	else kassen.kasse[index].wirdFrei(zeitpunkt);
    }
}

class neuer_Kunde_a extends Ereignis
{   neuer_Kunde_a(float z) { super(z); }
    void bearbeite()
    {	if(trace) System.out.println("neuer Kunde. " + zeitpunkt);
        if (einganggeschlossen) return;
        if (kassen.sindAlleBesetzt()) 
	    kundenSchl_a.anstellen(new Kunde(zeitpunkt));
        else {
            ereignisse.einfügen(new Kassefertig_a
                   ((float)(zeitpunkt+zeitFürKundenAnKassa())));
	    kassen.kasseWirdBesetzt_a(zeitpunkt);
	    stat.bearbeiteKunde(0);
	}
        float neuerZeitpunkt = (float) (zeitpunkt +
                zeitZwischenKunden());
        ereignisse.einfügen(new neuer_Kunde_a(neuerZeitpunkt));
	// Variante: zeitpunkt = neuerZeitpunkt; // es wird kein neues
	//           ereignisse.einfügen(this);  // Objekt erzeugt.
    }
}

class neuer_Kunde_b extends Ereignis
{   neuer_Kunde_b(float z) { super(z); }
    void bearbeite()
    {	if(trace) System.out.println("neuer Kunde. " + zeitpunkt);
        if (einganggeschlossen) return;
	int index = kassen.zufälligeKasse();
	Kasse ka = kassen.kasse[index];
        if (!ka.frei) 
	    kundenSchl_b[index].anstellen(new Kunde(zeitpunkt));
        else {
            ereignisse.einfügen(new Kassefertig_b
                   ((float)(zeitpunkt+zeitFürKundenAnKassa()), index));
	    ka.wirdBesetzt(zeitpunkt);
	    stat.bearbeiteKunde(0);
	}
        float neuerZeitpunkt = (float) (zeitpunkt +
                zeitZwischenKunden());
        ereignisse.einfügen(new neuer_Kunde_b(neuerZeitpunkt));
    }
}

class Kassenschluss extends Ereignis
{   Kassenschluss(float z) { super(z); }
    void bearbeite()
    {   if(trace) System.out.println("Kassenschluss " + zeitpunkt);
	einganggeschlossen = true; 
	kassen.schließeAlleKassen(zeitpunkt);
    }
}
		
class Kasse
{
    boolean frei = true;
    float freiSeit;
    Kasse(float f) {freiSeit = f;}
    void wirdFrei(float z)
    {   frei = true; freiSeit = z; }
    void wirdBesetzt(float z)
    {   frei = false; stat.bearbeiteKasse(z - freiSeit); }
}

class Kassen
{
    int anzKassen, freieKassen;
    Kasse[] kasse;
    Kassen(int anzKassen, float öffnungszeit)
    {
	freieKassen = this.anzKassen = anzKassen;
	kasse = new Kasse[anzKassen];
	for (int i=0; i<anzKassen; ++i)
	    kasse[i] = new Kasse(öffnungszeit);
    }

    void kasseWirdFrei_a(float z)
    {   kasse[freieKassen++].wirdFrei(z); }
    void kasseWirdBesetzt_a(float z)
    {   kasse[--freieKassen].wirdBesetzt(z); }
    int zufälligeKasse()
    { return (int) Math.floor(anzKassen * Math.random()); }
    boolean sindAlleBesetzt() { return freieKassen==0; }
    void schließeAlleKassen(float zeitpunkt)
    {   for(int i=0; i<anzKassen; ++i)
           if(kasse[i].frei)
	       stat.bearbeiteKasse(zeitpunkt - kasse[i].freiSeit); 
    }

}


double zeitZwischenKunden()
    { return -mu*Math.log(Math.random()); }
double zeitFürKundenAnKassa()
    { return kundenzeit_a + (kundenzeit_b-kundenzeit_a)*Math.random(); }

class Kunde
{   float ankunftszeit;
    Kunde next;

    Kunde(float z) { ankunftszeit=z; }
}
class KundenSchlange
{   Kunde first, last;
    int anzKunden = 0;

    boolean istleer() {return anzKunden==0;}
    void anstellen(Kunde k)
    {   if (first==null) first = k; else last.next = k;
        last = k;
        k.next = null;
	anzKunden++;
	if (trace) System.out.println("anstellen. "+anzKunden);
    }
    Kunde drankommen()
    {   if (first==null) throw new NoSuchElementException();
        Kunde k = first;
	first = first.next;
	anzKunden--;
	if (trace) System.out.println("drankommen. "+anzKunden);
	return k;
    }
}

class Statistik
{   int anzKunden = 0;
    float gesamtWartezeit = 0.0f;
    float maxWartezeit = 0.0f;
    float gesamtfreieZeit = 0.0f;
   
    void bearbeiteKunde(float wartezeit)
    {   anzKunden++;
        gesamtWartezeit += wartezeit;
	if (maxWartezeit < wartezeit) maxWartezeit = wartezeit;
    }
    void bearbeiteKasse(float freiezeit)
    {   gesamtfreieZeit += freiezeit;
    }

void druckeStatistik()
    { System.out.println("Anzahl der Kunden: " + anzKunden);
      System.out.println("durchschnittliche Wartezeit:         " + 
			    gesamtWartezeit / anzKunden + " Sekunden");
      System.out.println("maximale Wartezeit:                  " + 
			    maxWartezeit + " Sekunden");
      System.out.println("gesamte untätige Zeit an den Kassen: " + 
			    gesamtfreieZeit + " Sekunden");
    }
}
}