/* Aikataulun muodostaminen

Tämä ohjelma etsii aikataulun, jossa mahdollisimman moni asiakas saa hänelle
sopivan ajan.
Saman ajan voi antaa enintään niin monelle asiakkaalle kuin ohjelmalle
kerrotaan.
Jos ohjelma joutuu jättämään asiakkaan ilman aikaa, niin se suosii heitä,
jotka ovat ilmoittaneet mahdollisimman paljon itselleen sopivia aikoja, ja
tasatilanteessa ensin syötteessä tulevaa.

Ajat ja asiakkaat ovat merkkijonoja, joissa ei voi olla rivinsiirtoja eikä
erottimia.
Erottimia ovat välilyönti ja puolipiste.
Samalla rivillä olevat tekstialkiot erotetaan toisistaan vähintään yhdellä
erottimella.
Syötteessä on ensin rivejä muotoa "aika luku", joilla luetellaan jaettavissa
olevat ajat ja kerrotaan kuinka monelle kukin niistä voidaan antaa.
Sitten on ainakin yksi tyhjä rivi.
Lopuksi kullekin asiakkaalle on rivi, jossa on hänen tunnuksensa ja hänelle
sopivat ajat.

Antti Valmari 23.5.2020
*/


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>


/*** Reading input from console (#define console) or cgi ***/

char inp_chr = '\0';    // most recent input character
unsigned inp_line = 0;  // number of the line it was on


#ifndef console


/* Cgi-decode the input character, reading more characters if necessary. */
inline void inp_cgi_decode(){
  // oho, tästä puuttuu jotakin
}

#endif


/* If in CGI mode, skip the first form field name and prepare for actual
  output.  That is, do everything that precedes actual input and output.
  Make inp_chr == '\n'. */
inline void inp_out_start(){
#ifndef console
  std::cout << "Content-type: text/html\n\n";
  while( std::cin.get( inp_chr ) && inp_chr != '=' );
#endif
  inp_chr = '\n'; inp_line = 1;
}


/* Read and cgi-bin-decode input until something can be delivered or the input
  ends. */
void inp_get_chr(){

  while( true ){

    /* Read next char or detect the end of input. */
    inp_chr = std::cin.get();
    if( !std::cin ){ inp_chr = '\0'; }

#ifndef console
    /* Detect new form field. */
    else if( inp_chr == '&' ){ inp_chr = '\n'; }

    /* Decode + and %-codes. */
    else{ inp_cgi_decode(); }
#endif

    /* Skip <CR> to avoid spurious double newlines. */
    if( inp_chr == '\x0d' ){ continue; }

    if( inp_chr == '\n' ){ ++inp_line; }
    return;
  }
}


inline bool inp_is_digit(){ return '0' <= inp_chr && inp_chr <= '9'; }

inline bool inp_is_separator(){ return inp_chr == ' ' || inp_chr == ';'; }

inline void inp_skip_separators(){
  while( inp_is_separator() ){ inp_get_chr(); }
}


/*** Syötteen lukeminen ***/


const unsigned max_luku = 999;  // älyttömien syötteiden havaitsemiseksi


void syotevirhe( const char *viesti, bool ohita_rivinsiirto ){
  std::cout << "\n<p class=err>Syötevirhe rivillä " <<
    inp_line - ( inp_chr == '\n' ) << ": " << viesti << '\n';
  while( inp_chr && inp_chr != '\n' ){ inp_get_chr(); }
  if( ohita_rivinsiirto && inp_chr == '\n' ){ inp_get_chr(); }
}


void lue_merkkijono( std::string & tulos ){
  inp_skip_separators();
  while( inp_chr && !inp_is_separator() && inp_chr != '\n' ){
    tulos += inp_chr; inp_get_chr();
  }
}


/* Lue etumerkitön luku. Jos luku on yli rajan, niin anna virheilmoitus.
  Raja toimii luotettavasti vain jos se ei ole liian lähellä lukualueen
  yläreunaa. */
unsigned lue_etumerkiton_luku( unsigned raja ){
  // hupsista, tästäkin puuttuu jotakin!
}


/* Käynnistä syötteen lukeminen ja ohita alussa tyhjät rivit. Aseta debug
  sen mukaan onko aivan ensimmäinen merkki ';'. */
bool debug = false;   // kun true, niin ohjelma perustelee jos ei anna aikaa
void aloita_lukeminen(){
  inp_out_start(); inp_get_chr();
  if( inp_chr == ';' ){ debug = true; inp_get_chr(); }
  while( inp_chr == '\n' ){ inp_get_chr(); }
}


/* Ajoille käytetään myös juoksevia numeroita ykkösestä alkaen siten, että
  kukin aika saa niin monta numeroa kuinka monelle sen voi varata. Ajat
  esitetään kuvauksena ajan nimeltä tietueelle, jossa on ajalle sallittujen
  varausten määrä ja niistä ensimmäisen juokseva numero. Kuvauksen pari löytyy
  juoksevan numeron perusteella taulukon numerosta_aikaan kautta. */
struct aika_tyyppi{
  unsigned maara, eka, pula_kierros, pula_aste;
  aika_tyyppi(): maara(0), eka(0), pula_kierros(0), pula_aste(0) {}
};
std::map< std::string, aika_tyyppi > ajat;
typedef std::map< std::string, aika_tyyppi >::iterator ajat_iter;
std::vector< ajat_iter > numerosta_aikaan;
unsigned pula_kierros = 0;  // aikojen pula_kierros verrataan tähän


unsigned aikoja = 0;  // ajat on numeroitu 1, ..., aikoja

void hae_aikakoodit(){

  /* Lue aikojen kuvaukset riveittäin ja laske syntyvien aikojen määrä. */
  aikoja = 0;
  while( inp_chr && inp_chr != '\n' ){

    /* Lue ja tarkasta ajan nimi. */
    std::string ak; lue_merkkijono( ak );
    if( ajat.find( ak ) != ajat.end() ){
      syotevirhe( "samanniminen aika on jo luotu", true ); continue;
    }

    /* Lue ajalle sallittujen varausten määrä ja anna niille numerot. */
    unsigned ii = aikoja + 1;
    ajat[ ak ].maara = lue_etumerkiton_luku( max_luku );
    ajat[ ak ].eka = ii; aikoja += ajat[ ak ].maara;
    ajat_iter it = ajat.find( ak );
    numerosta_aikaan.resize( aikoja + 1 );
    for( ; ii <= aikoja; ++ii ){ numerosta_aikaan[ ii ] = it; }

    /* Tarkasta rivin loppuosan syntaksi. */
    inp_skip_separators();
    if( inp_chr == '\n' ){ inp_get_chr(); }
    else if( inp_chr ){
      syotevirhe( "rivin piti olla muotoa aikakoodi;määrä", true );
    }

  }
}


/* Asiakkaan tiedot */
struct asiakas_tyyppi{
  std::string tunnus;
  std::vector< unsigned > sopivat_ajat;
  std::vector< ajat_iter > sopivat_lokerot;
  bool operator <( const asiakas_tyyppi & toinen ) const {
    return sopivat_lokerot.size() > toinen.sopivat_lokerot.size();
  }
};


/* Asiakkaat numeroidaan 1, 2, ... asiakkaat[0] on varmasti olemassa, mutta
  jää käyttämättä. */
std::vector< asiakas_tyyppi > asiakkaat(1);


/* Lue ja tulkitse asiakkaiden tiedot muuttujaan asiakkaat. */
void hae_sopivat_ajat(){

  /* Lue asiakkaiden tietoja niin kauan kuin syötettä riittää. */
  unsigned asiakas = 0;
  inp_skip_separators();
  while( inp_chr ){

    /* Ohita tyhjät rivit. */
    if( inp_chr == '\n' ){ inp_get_chr(); inp_skip_separators(); continue; }

    /* Luo uusi asiakas. */
    ++asiakas; asiakkaat.resize( asiakas + 1 );

    /* Lue asiakkaan tunniste. */
    lue_merkkijono( asiakkaat[ asiakas ].tunnus );

    /* Lue asiakkaan ajat. */
    while( inp_chr && inp_chr != '\n' ){
      std::string ak; lue_merkkijono( ak );
      ajat_iter it = ajat.find( ak );
      if( it == ajat.end() ){
        syotevirhe( "tuntematon aikakoodi", false ); break;
      }
      asiakkaat[ asiakas ].sopivat_lokerot.push_back( it );
      unsigned ii = it->second.eka, ohi = ii + it->second.maara;
      for( ; ii < ohi; ++ii ){
        asiakkaat[ asiakas ].sopivat_ajat.push_back( ii );
      }
    }
    if( inp_chr ){ inp_get_chr(); }

  }

  /* Järjestä asiakkaat eniten sopivia aikoja ilmoittanut ensin. */
  std::vector< asiakas_tyyppi >::iterator ait = asiakkaat.begin();
  ++ait; std::stable_sort( ait, asiakkaat.end() );

}


/*** Aikojen vekslaus ***/

/* varaaja[i] on 0 tai ajan i varanneen asiakkaan numero. */
std::vector< unsigned > varaaja;


void vekslaa_ajat(){
  varaaja.resize( aikoja + 1 );
  std::vector< unsigned >
    jono( aikoja + 1 ),       // leveyteen ensin -haun työjono
    edellinen( aikoja + 1 );  // vekslauspolku takaperin
  std::vector< unsigned > kokeiltu( aikoja + 1 );
    // aika i on tutkittu kierroksella kokeiltu[i]

  /* Vekslaa asiakkaat mukaan yksi kerrallaan. */
  for(
    unsigned vekslattava = 1; vekslattava < asiakkaat.size(); ++vekslattava
  ){

    /* Varaa uudelle asiakkaalle aika 0 ja laita aika 0 työjonoon. */
    varaaja[ 0 ] = vekslattava; jono[ 0 ] = 0;
    unsigned jono_eka = 0, jono_vapaa = 1;

    /* Kokeile työjonon aikojen vaihtamista yksi kerrallaan. */
    while( jono_eka < jono_vapaa ){
      unsigned aika1 = jono[ jono_eka ], asiakas = varaaja[ aika1 ];
      ++jono_eka;

      /* Yritä löytää jonon kärjen ajan varaajalle toinen aika. */
      for(
        unsigned ii = 0; ii < asiakkaat[ asiakas ].sopivat_ajat.size(); ++ii
      ){
        unsigned aika2 = asiakkaat[ asiakas ].sopivat_ajat[ ii ];

        /* Jos aika on vapaa, siirrä ajat polkua pitkin. */
        if( !varaaja[ aika2 ] ){
          while( aika2 ){
            varaaja[ aika2 ] = varaaja[ aika1 ]; aika2 = aika1;
            aika1 = edellinen[ aika2 ];
          }
          jono_vapaa = 0;   // keskeytetään työjonon tutkiminen
          break;            // keskeytetään jonon kärjen asiakkaan tutkiminen
        }

        /* Jos varatun ajan siirto on tutkimatta, lisää aika työjonoon. */
        else if( kokeiltu[ aika2 ] < vekslattava ){
          kokeiltu[ aika2 ] = vekslattava; edellinen[ aika2 ] = aika1;
          jono[ jono_vapaa ] = aika2; ++jono_vapaa;
        }

      }

    }

    /* Jos debug-moodissa eikä aikaa saatu järjestettyä, niin tulosta syy. */
    ++pula_kierros;
    for( unsigned ii = 0; ii < jono_vapaa; ++ii ){
      unsigned as = varaaja[ jono[ ii ] ];
      for(
        unsigned jj = 0; jj < asiakkaat[ as ].sopivat_lokerot.size(); ++jj
      ){
        ajat_iter it = asiakkaat[ as ].sopivat_lokerot[ jj ];
        if( it->second.pula_kierros < pula_kierros ){
          it->second.pula_kierros = pula_kierros; ++it->second.pula_aste;
        }
      }
    }
    if( debug && jono_vapaa ){
      std::cout << "<p>Mahdoton joukko:\n";
      for( unsigned ii = 0; ii < jono_vapaa; ++ii ){
        std::cout << "  " << asiakkaat[ varaaja[ jono[ ii ] ] ].tunnus <<
          '\n';
      }
    }

  }

}


/*** Vastauksen tulostus sekä pääohjelma ***/

bool pula_vertaa( const ajat_iter it1, const ajat_iter it2 ){
  if( it1->second.pula_aste > it2->second.pula_aste ){ return true; }
  if( it1->second.pula_aste < it2->second.pula_aste ){ return false; }
  return it1->second.eka < it2->second.eka;
}

void tarkasta_ja_tulosta_ajat(){

  /* Selvitä asiakkaiden määrä. */
  unsigned asiakkaita = asiakkaat.size() - 1;

  /* Selvitä asiakkaiden varaamat ajat ja tarkasta, että mitään aikaa ei ole
    varattu kahdesti. */
  std::vector< unsigned > varaus( asiakkaita + 1 );
  for( unsigned ai = 1; ai <= aikoja; ++ai ){
    unsigned as = varaaja[ ai ];
    if( as ){
      if( varaus[ as ] ){
        std::cout << "<p class=err>??? Ohjelmavirhe: tuplavaraus\n";
      }else{ varaus[ as ] = ai; }
    }
  }

  /* Tulosta ilman aikaa jääneet asiakkaat. */
  unsigned ilman = 0;
  for( unsigned as = 1; as <= asiakkaita; ++as ){
    if( !varaus[ as ] ){ ++ilman; }
  }
  if( !ilman ){ std::cout << "<p style=color:green>Jokainen sai ajan\n"; }
  else{
    std::cout << "\n<p class=err>" << ilman <<
      " asiakasta jäi ilman aikaa\n<pre class=err>\n";
    for( unsigned as = 1; as <= asiakkaita; ++as ){
      if( !varaus[ as ] ){ std::cout << asiakkaat[ as ].tunnus << '\n'; }
    }
    std::cout << "</pre>\n";
  }

  /* Tulosta onnistuneet varaukset asiakkaan funktiona. */
  std::cout << "\n<p>Asiakkaiden saamat ajat\n<pre>\n";
  for( unsigned as = 1; as <= asiakkaita; ++as ){
    unsigned ii = varaus[ as ];
    if( ii ){
      std::cout << asiakkaat[ as ].tunnus << ';' <<
      numerosta_aikaan[ ii ]->first << '\n';
    }
  }
  std::cout << "</pre>\n";

  /* Tulosta onnistuneet varaukset ajan funktiona. */
  std::cout << "\n<p>Varaukset ajan funktiona\n<pre>";
  ajat_iter it1 = ajat.end();
  for( unsigned ii = 1; ii <= aikoja; ++ii ){
    unsigned as = varaaja[ ii ];
    if( as ){
      ajat_iter it2 = numerosta_aikaan[ ii ];
      if( it1 != it2 ){ std::cout << '\n' << it2->first; it1 = it2; }
      std::cout << ';' << asiakkaat[ as ].tunnus;
    }
  }
  std::cout << "\n</pre>\n";

  /* Tulosta lisäaikaheuristiikka. */
  std::vector< ajat_iter > pula_ajat;
  if( ilman ){
    std::cout << "\n<p>Ehdotuksia mihin kannattaa lisätä aikoja, luku on"
      << " epävarma heuristiikka\n<pre>\n";
    for( ajat_iter it = ajat.begin(); it != ajat.end(); ++it ){
      pula_ajat.push_back( it );
    }
    std::sort( pula_ajat.begin(), pula_ajat.end(), pula_vertaa );
    for( unsigned ii = 0; ii < pula_ajat.size(); ++ii ){
      ajat_iter it = pula_ajat[ ii ];
      if( !( it->second.pula_aste ) ){ break; }
      std::cout << it->first << ' ' << it->second.pula_aste << '\n';
    }
    
    std::cout << "</pre>\n";
  }

}


/* Pääohjelma */
int main(){
  aloita_lukeminen();
  std::cout << "<!DOCTYPE html>\n<html lang=fi>\n<head>\n";
  std::cout << "<meta charset=UTF-8>\n";
  std::cout << "<title>Aikataulutietoja</title>\n";
  std::cout << "<style>\nbody { font-family: sans-serif }\n";
  std::cout << "h1 { color:blue }\n.err { color:red }\n</style>\n";
  std::cout << "</head>\n<body>\n\n<h1>Aikataulutietoja</h1>\n";
  hae_aikakoodit();
  hae_sopivat_ajat();
  vekslaa_ajat();
  tarkasta_ja_tulosta_ajat();
  std::cout << "\n</body>\n</html>\n";
}