import java.util.*;
//-----------------------------------------------------------------------------
//S i m u l a t i o n D a t a
//Benyttes til at pakke resultaterne ind beregnet under simulationen fra 'CarSimulation' klassen.
class SimulationData
{
  long meanWaitingTime = 0;
  long maximalWaitingTime = 0;
  long nrOfProcessedCars = 0;
  CarQueue[] carQueues;
  SimulationData(long meanWaitingTime, long maximalWaitingTime, long nrOfProcessedCars,
                 CarQueue[] carQueues)
  { this.meanWaitingTime = meanWaitingTime;
    this.maximalWaitingTime = maximalWaitingTime;
    this.nrOfProcessedCars = nrOfProcessedCars;
    this.carQueues = carQueues;
  }
}
//-----------------------------------------------------------------------------
//C a r S i m u l a t i o n
//Klassen står for udførslen og koordineringen af selve simulationen
class CarSimulation
{
  //Array indeholdende de bilkøer som indgår i simulationen.
  CarQueue[] carQueues = null;

  //Angiver simulations tiden for hvornår den næste bil skal ankomme!
  long newCarArrivingTime = 0;

  public SimulationData newSimulationSession(int meanArrivalTime, //gennemsnitlige ankomst tid (sek)
                                             int diviationArrivalTime, //afvigelsen for ankomsterne
                                             int payTime, //den tid det tager at betale i boden
                                             int nrOfQueues, //antallet af køer tilrådighed
                                             int simulationTime) //længden af simulationen.
  {
    if(meanArrivalTime <= 0 || diviationArrivalTime < 0 ||
       meanArrivalTime < diviationArrivalTime || payTime <= 0 || nrOfQueues <= 0 ||
       simulationTime <= 0)
      return null;

    long timeOffset = meanArrivalTime - diviationArrivalTime;

    carQueues = new CarQueue[nrOfQueues];
    for(int i = 0; i < nrOfQueues; i++)
      carQueues[i] = new CarQueue();

    newCarArrivingTime = 0;
    //Statiske variable i CarQueue nulstilles til en ny session.
    CarQueue.resetParameters();
    CarQueue.simulationTime = simulationTime;
    CarQueue.payTime = payTime;
    //Loop indtil simulationen er færdig. (1 loop = 1 sek)
    for(long clock = 0; clock < simulationTime; clock++)
    {
      //Hvis der er ankommet en ny bil i dette sekund!
      if(newCarArrivingTime <= clock)
      { //Find den bil-kø med de færreste antal ventende biler!
        int minimumCars = carQueues[0].getCarQueueSize();
        int minimumIndex = 0;
        for(int i = 1; i < nrOfQueues; i++)
        { if(carQueues[i].getCarQueueSize() < minimumCars)
          { minimumIndex = i;
            minimumCars = carQueues[i].getCarQueueSize();
          }
        }
        //prop den næste bil i den udvalgte kø!
        carQueues[minimumIndex].putCarInQueue(new Car(clock));

        //find udaf hvornår den næste bil skal ankomme
        //NB: timeOffset = gennemsnits tid - afvigelsen. Hertil lægges et randomiseret antal
        //som ligger indenfor rammen 2*afvigelsen
        newCarArrivingTime = (clock + ((int)(Math.random()*(2*diviationArrivalTime)) + timeOffset));
      }
      //Se om nogen af køerne har færdiggjort en bil i dette sekund!
      for(int i = 0; i < nrOfQueues; i++)
        carQueues[i].tryToProcessAnOtherCar(clock);
    }
    //hvis der nu var en bil kø som ingen biler havde ved afslutningen opdateres dennes rest tid
    for(int i = 0; i < nrOfQueues; i++)
      carQueues[i].updateRestOfSpareTime();

    //Resultaterne returneres indpakket i et 'SimulationData' objekt
    return new SimulationData((long)(CarQueue.totalWaitingTime/CarQueue.nrOfProcessedCars),
                              CarQueue.maximalWaitingTime, CarQueue.nrOfProcessedCars,
                              carQueues);
  }
}
//-----------------------------------------------------------------------------
//C a r Q u e u e
//Klassen holder styr på selve bil køen og sørger for at hive bilerne ud af køen
//når det bliver deres tur til at betale. Herudover holder klassen også styr på
//de statistiske data som skal indsamles under simulationen.
class CarQueue
{
  //Statiske parametre og funktioner. NB: virker for alle køer!
  static long totalWaitingTime = 0;   //Angiver den accumulerede ventetid for alle biler.
  static long nrOfProcessedCars = 0;  //De totale behandlede biler for alle køer.
  static long maximalWaitingTime = 0; //Angiver den længste målte ventetid for en bil i køerne.
  static long payTime = 0;            //Angiver hvormange sec. det tager at betale i boden.
  static long simulationTime = 0;     //Angiver simulations længden i sekunder.
  public static void resetParameters()
  {
    totalWaitingTime = nrOfProcessedCars = maximalWaitingTime = payTime = simulationTime = 0;
  }
  //private variable for den enkelte kø.
  private LinkedList myCarQueue = new LinkedList(); //selve bil-køen!
  private long mySpareTime = 0;       //Den accumulerede rest tid for boden/køen
  private long freeAtTime = 0;        //Angiver den tid hvor boden igen bliver ledig.
  private int nrOfMyProcessedCars = 0;//Antallet af behandlede biler for boden!

  //Access funktioner
  public int getCarQueueSize() { return myCarQueue.size(); }
  public long getSpareTime() { return mySpareTime; }
  public int getProcessedCars() { return nrOfMyProcessedCars; }
  public int getWaitingCars() { return myCarQueue.size(); }

  public void putCarInQueue(Car aCar) { myCarQueue.addFirst(aCar); }
  public void tryToProcessAnOtherCar(long currentClock)
  {
    //Er boden ledig til at modtage en ny bil dette sekundt og er der nogen biler i køen.!
    if(freeAtTime <= currentClock && myCarQueue.size() > 0)
    {
      //Rest tiden opdateres idet køen kan have været tom i længere tid
      mySpareTime += (currentClock - freeAtTime);

      //Hent den næste bil udfra køen
      Car car = (Car)myCarQueue.removeLast();

      //Hvis vi kan se at bilen ikke kan nå at blive færdiggjort inden simulationstiden er overstået
      //skal bilen ikke indgå i den samlede statestik!
      if((currentClock+payTime) < simulationTime)
      {
        long waitingTime = (currentClock - car.getStartTime()) + payTime;
        totalWaitingTime += waitingTime;
        if(maximalWaitingTime < waitingTime)
          maximalWaitingTime = waitingTime;
        nrOfProcessedCars++;
        nrOfMyProcessedCars++;
      }
      //beregn hvornår bilen er færdig i boden og en ny bil kan behandles
      freeAtTime = (currentClock + payTime);
    }
  }
  public void updateRestOfSpareTime()
  {
    if(simulationTime > freeAtTime)
      mySpareTime += (simulationTime - freeAtTime);
  }
}
//-----------------------------------------------------------------------------
//C a r
//Klassen holder styr på hvornår en bil ankommer til en bil kø ved broen!
class Car
{
  private long startTime = 0;
  Car(long startTime) { this.startTime = startTime;  }
  public long getStartTime()  { return startTime; }
}
//-----------------------------------------------------------------------------