#include <stdio.h>
#include <assert.h>
#include <string.h>

#ifdef _WIN32
  #include "librandom/c++/PseudoEnthropy.hpp"
  #include "librandom/c++/FileByteSource.hpp"
  #include "librandom/c++/Random.hpp"
  #include "librandom/double/cephes.h"
  #include <windows.h>
  #pragma comment(lib, "librandom/Release/librandom.lib")
#else
  #include "SeededEnthropy.hpp"
  #include "FileByteSource.hpp"
  #include "Random.hpp"
  #include "cephes.h"
#endif

//#define NOPRINT

#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
using namespace std;

//======================================================================//
// Random2
//======================================================================//
class Random2: public Random
{
public:
  int poisson(double lambda) throw (BadArgsError)
  {
    if(!(lambda > 0))
      throw BadArgsError();
    double val = uniform();
    int kmin=0, kmax=0, kmid;
    while(cephes_pdtr(kmax, lambda) < val)
    {
      kmin = kmax;
      kmax = (kmax << 1) + 1;
    }
    while(kmin != kmax)
    {
      kmid = (kmax + kmin) >> 1;
      if(cephes_pdtr(kmid, lambda) < val)
        kmin = kmid + 1;
      else
        kmax = kmid;
    }
    return kmin;
  }

  int exact(int n, double* Probabilities)
  {
    if(n == 0)
      throw BadArgsError();
    double sum = 0;
    double val = uniform();
    int i;
    for(i = 0; i < n; i++)
    {
      sum += Probabilities[i];
      if(val < sum)
        return i;
    }
    return n;
  }

  Random2(EnthropySource *_src) throw (BadArgsError): Random(_src) {};
};      

Random2* rnd;

//======================================================================//
// Classes
//======================================================================//
class TVisitor;
class TCrowdedPlace;
class TEntrance;
class TExit;
class TBureaucrat;

struct TEvent
{
  double time;
  TCrowdedPlace* Subject;
  bool operator< (const TEvent& Event) const
  {
    return (time > Event.time);
  }
};

class TMinistery
{
private:
  double time, CloseTime;
  priority_queue<TEvent> EventQueue;
  vector<TCrowdedPlace*> CrowdedPlaces; 
  int N;
  int VisitorsProcessed;
  float MeanVisitsPerVisitor;
  float MeanQueueLenght;
  // 0 - Exit
  // 1..N - Bureaucrats
  // N+1 - Entrance
public:
  void InitStatisticData()
  {
    VisitorsProcessed = 0;
    MeanVisitsPerVisitor = 0;
    MeanQueueLenght = 0;
  }
  void AddVisitor()
  {
    VisitorsProcessed++;
  }
  void AddVisit()
  {
    MeanVisitsPerVisitor++;
  }
  void AddToQueueLength(float value)
  {
    MeanQueueLenght+=value;
  }
  string GetStatisticData();
  double CurrentTime() 
  {
    return time;
  }
  string CurrentTimeString() 
  {
    stringstream ss;
    ss<<left<<setw(6)<<time;
    return ss.str().substr(0,6);
  } 
  bool IsClosed() 
  {
    return time > CloseTime;
  }
  void SendVisitor(int Destination, TVisitor* Visitor);
  void AddEvent(double TimeLeft, TCrowdedPlace* Subj);
  TMinistery();
  void Run();
  friend istream& operator>> (istream& s, TMinistery& Ministery);
};

class TVisitor
{
private:
  static int TotalClients;
public:
  int id;
  int Visits;
  TVisitor()
  {
    id = TotalClients;
    Visits = 0;
    TotalClients++;
  }
};

int TVisitor::TotalClients = 0;

class TCrowdedPlace
{
protected:
  queue<TVisitor*> Queue;
  TMinistery* Owner;
  float LastEventTime;
  float MeanQueueLength;
public:
  virtual void Execute()=0;
  TCrowdedPlace(TMinistery* owner) 
  {
    Owner = owner;
    LastEventTime = 0;
    MeanQueueLength = 0;
  }
  virtual void AddToQueue(TVisitor* Visitor)
  {
    MeanQueueLength += (Owner->CurrentTime() - LastEventTime) * Queue.size();
    LastEventTime = Owner->CurrentTime();
    Queue.push(Visitor);
  }
  virtual void PopQueue()
  {
    MeanQueueLength += (Owner->CurrentTime() - LastEventTime) * Queue.size();
    LastEventTime = Owner->CurrentTime();
    Queue.pop();
  }
  float GetMeanQueueLength()
  {
    return MeanQueueLength / Owner->CurrentTime();
  }
  virtual ~TCrowdedPlace() 
  {
    while(Queue.size() > 0)
    {
      delete Queue.front();
      PopQueue();
    }
  };
  virtual istream& ReadFromStream(istream& s)=0;
};

istream& operator>> (istream& s, TCrowdedPlace& CrowdedPlace)
{
  return CrowdedPlace.ReadFromStream(s);
}

class TEntrance: public TCrowdedPlace
{
protected:
  bool Executed;
  double* Probabilities;
  int n;
  double lambda;
public:
  void SetBureaucratCount(int N)
  {
    n = N + 1;
  }
  virtual void Execute()
  {
    if(!Owner->IsClosed())
    {
      if(Executed)
      {
        TVisitor* Visitor = new TVisitor;
        int Destination = rnd->exact(n, Probabilities);
#ifndef NOPRINT
        if(Destination != 0)
          cout<<Owner->CurrentTimeString()<<": Visitor "<<Visitor->id<<" entered the Building and was sent to Bureaucrat "<<Destination<<"\n";
        else
          cout<<Owner->CurrentTimeString()<<": Visitor "<<Visitor->id<<" entered the Building and was sent back by Bureaucrats\n";
#endif
        Owner->SendVisitor(Destination, Visitor);
      }
      Owner->AddEvent(rnd->exponent(lambda), this);
      Executed = true;
    }
  }
  TEntrance(TMinistery* owner):TCrowdedPlace(owner) {Executed = false; n = 0; lambda = 0; Probabilities=0;};
  virtual istream& ReadFromStream(istream& s)
  {
    // Input:
    // Lambda (Poisson agrument)
    // Probabilities [0 - exit, 1..N - Bureaucrats]
    s>>lambda;
    Probabilities = new double[n];
    for(int i = 0; i < n; i++)
      s>>Probabilities[i];
    return s;
  }
  virtual ~TEntrance() 
  {
    if(Probabilities != 0)
      delete[] Probabilities;
  }
};

class TExit: public TCrowdedPlace
{
public:
  virtual void AddToQueue(TVisitor* Visitor)
  {
#ifndef NOPRINT
    cout<<Owner->CurrentTimeString()<<": Visitor "<<Visitor->id<<" Left the Building\n";
#endif
    delete Visitor;
    Owner->AddVisitor();
  }
  virtual void Execute(){}
  virtual istream& ReadFromStream(istream& s){return s;}
  TExit(TMinistery* owner):TCrowdedPlace(owner){}
};

class TBureaucrat: public TCrowdedPlace
{
protected:
  bool Working;
  vector<double*> Probabilities;
  int n;
  int MyNumber;
  map<int, int> TimesVisited;
  double lambda;
  double* GetProbabilities(int VisitN)
  {
    if(VisitN >= Probabilities.size())
      return Probabilities[Probabilities.size() - 1];
    else
      return Probabilities[VisitN];
  }
public:
  void SetBureaucratCount(int N)
  {
    n = N + 1;
  }
  virtual void Execute()
  {
    if(Working)
    {
      int Destination = rnd->exact(n, GetProbabilities(TimesVisited[Queue.front()->id]));
#ifndef NOPRINT
      if(Destination != 0)
        cout<<Owner->CurrentTimeString()<<": Visitor "<<Queue.front()->id<<" was sent to Bureaucrat "
          <<Destination<<" by Bureaucrat "<<MyNumber<<"\n";
      else
        cout<<Owner->CurrentTimeString()<<": Visitor "<<Queue.front()->id<<" was sent to Exit by Bureaucrat "<<MyNumber<<"\n";
#endif
      Owner->SendVisitor(Destination, Queue.front());
      TimesVisited[Queue.front()->id]++;
      PopQueue();
    }
    if(Queue.empty())
      Working = false;
    else
    {
#ifndef NOPRINT
      cout<<Owner->CurrentTimeString()<<": Visitor "<<Queue.front()->id<<" entered office of Bureaucrat "<<MyNumber<<"\n";
#endif
      Owner->AddEvent(rnd->exponent(lambda), this);
      Owner->AddVisit();
    }
  }
  virtual void AddToQueue(TVisitor* Visitor)
  {
    TCrowdedPlace::AddToQueue(Visitor);
    if(!Working)
    {
      Working = true;
#ifndef NOPRINT
      cout<<Owner->CurrentTimeString()<<": Visitor "<<Queue.front()->id<<" entered office of Bureaucrat "<<MyNumber<<"\n";
#endif
      Owner->AddEvent(rnd->exponent(lambda), this);
    }
  }
  TBureaucrat(TMinistery* owner, int myNumber):TCrowdedPlace(owner) {Working = false; n = 0; lambda = 1; MyNumber = myNumber;}
  virtual istream& ReadFromStream(istream& s)
  {
    // Input:
    // Lambda (Exponent argument)
    // K (revisits)
    //
    // Probabilities for 1-st Visit [0 - exit, 1..N - Bureaucrats]
    // Probabilities for 2-nd Visit [0 - exit, 1..N - Bureaucrats]
    // ...
    // Probabilities for K-th Visit [0 - exit, 1..N - Bureaucrats]
    s>>lambda;
    int K;
    s>>K;
    for(int i = 0; i < K; i++)
    {
      double* probs = new double[n];
      for(int j = 0; j < n; j++)
        s>>probs[j];
      Probabilities.push_back(probs);
    }
    return s;
  }
  virtual ~TBureaucrat() 
  {
    if(Probabilities.size() != 0)
    {
      for(int i = 0; i < Probabilities.size(); i++)
      delete[] Probabilities[i];
    }
  }
};

void TMinistery::SendVisitor(int Destination, TVisitor* Visitor)
{
  CrowdedPlaces[Destination]->AddToQueue(Visitor);
}

void TMinistery::AddEvent(double TimeLeft, TCrowdedPlace* Subj)
{
  TEvent Event;
  Event.Subject = Subj;
  Event.time = time + TimeLeft;
  this->EventQueue.push(Event);
}

TMinistery::TMinistery()
{
  time = 0;
}

void TMinistery::Run()
{
  CrowdedPlaces[N+1]->Execute();
  while(!EventQueue.empty())
  {
    TEvent Event = EventQueue.top();
    EventQueue.pop();
    time = Event.time;
    Event.Subject->Execute();
  }
}

string TMinistery::GetStatisticData()
{
  stringstream ss;
  ss<<"Total Visitors: "<<VisitorsProcessed<<"\nMean Visits per Visitor: "
    <<MeanVisitsPerVisitor / VisitorsProcessed<<"\n";
  float s = 0;
  for(int i = 1; i <= N; i++)
  {
    s += CrowdedPlaces[i]->GetMeanQueueLength();
    ss<<"Mean Queue to Bureaucrat "<<i<<" Length: "
      <<CrowdedPlaces[i]->GetMeanQueueLength()<<"\n";
  }
  ss<<"Mean Queue Length: "<<(s / N)<<"\n";
  return ss.str();
}


istream& operator>> (istream& s, TMinistery& Ministery)
{
  // Input:
  // Number of Bureaucrats
  // Time when Ministery Closes
  // Bureaucrats
  // Entrance
  s>>Ministery.N>>Ministery.CloseTime;
  TExit* Exit = new TExit(&Ministery);
  Ministery.CrowdedPlaces.push_back(Exit);
  for(int i = 0; i < Ministery.N; i++)
  {
    TBureaucrat* Bureaucrat = new TBureaucrat(&Ministery, i + 1);
    Bureaucrat->SetBureaucratCount(Ministery.N);
    s>>*Bureaucrat;
    Ministery.CrowdedPlaces.push_back(Bureaucrat);
  }
  TEntrance* Entrance = new TEntrance(&Ministery);
  Entrance->SetBureaucratCount(Ministery.N);
  s>>*Entrance;
  Ministery.CrowdedPlaces.push_back(Entrance);
  return s;
}

//======================================================================//
// Main
//======================================================================//
int main(void)
{
#ifdef _WIN32
  rnd = new Random2(new PseudoEnthropy(GetTickCount(),666,666));
#else
  rnd = new Random2(new SeededEnthropy(new FileByteSource("/dev/urandom"))); 
#endif

  TMinistery* Ministery = new TMinistery();

  fstream f;
  f.open("in.txt", ios_base::in);
  f>>*Ministery;
  Ministery->InitStatisticData();
  Ministery->Run();
  cout<<"\nStatistics.\n"<<Ministery->GetStatisticData();


  delete Ministery;
  delete rnd;

  int i; cin>>i;

  return 0;
}