program TH;

const 
  ULOH_MAX = 20;

type 
  string20 = string[20];

  tUloha = record { struktura ulohy - vsetky potrebn info }
    popis : string20; { nazov ulohy (por. cislo) }
    p : integer; { cas spracovania ulohy }
    r : integer; { cas vstupu ulohy do systemu }
    d : integer; { pozadovany cas ukoncenia ulohy }
    w : integer; { vaha ulohy }
  end;

  pUloha = ^tUloha; { smernik na strukturu ulohy }

var
  uloh : integer; { pocet uloh v poli }
  ulohy : array [1..ULOH_MAX] of pUloha; { pole smernikov na ulohy }

{ sluzi na uvolnenie pola uloh }
procedure Koniec;
var
  i : integer;
begin
  for i := 1 to uloh do begin
    Dispose(ulohy[i]);
    ulohy[i] := nil;
  end;
  uloh := 0;
end;

{ sluzi na zinicializovanie pola uloh }
procedure Inicializacia;
var
  i : integer;
begin
  uloh := 0;
  for i := 1 to ULOH_MAX do ulohy[i] := nil;
end;

{ sluzi na nacitanie textoveho suboru uloh }
procedure Nacitaj(filename : string);
var
  t : text;
  s : string;
  i, l : integer;
  pu : pUloha;
begin
  Assign(t, filename);
  Reset(t);
  l := 0;
  while not(Eof(t)) do begin
    { nacitaj riadok zo suboru }
    readln(t, s); inc(l);
    { prazdne riadky a riadky zacinajuce '#' su ignorovane }
    if (s <> '') and (s[1] <> '#') then begin
      { alokacia pamate pre ulohu }
      New(pu);
      if pu = nil then begin
        { nedostatok pamate }
        writeln('Nepodarilo sa alokovat pamat.');
        halt(1);
      end;
      
      { nacitanie informacii o ulohe - vseky su navzajom oddelene znakom ':'}

      { najskor ide popis ulohy }
      i := Pos(':', s);
      if i = 0 then begin
        { riadok neobsahuje ':' - chyba v subore }
        writeln('Chyba v subore ', filename, ' na riadku ', l, '.');
        Halt(1);
      end;
      pu^.popis := Copy(s, 1, i - 1);
      Delete(s, 1, i);
      
      { dlzka spracovavania ulohy }
      i := Pos(':', s);
      if i = 0 then begin
        { riadok neobsahuje ':' - chyba v subore }
        writeln('Chyba v subore ', filename, ' na riadku ', l, '.');
        Halt(1);
      end;
      Val(Copy(s, 1, i - 1), pu^.p);
      Delete(s, 1, i);
      
      { cas vstupu ulohy do systemu }
      i := Pos(':', s);
      if i = 0 then begin
        { riadok neobsahuje ':' - chyba v subore }
        writeln('Chyba v subore ', filename, ' na riadku ', l, '.');
        Halt(1);
      end;
      Val(Copy(s, 1, i - 1), pu^.r);
      Delete(s, 1, i);
      
      { pozadovany cas ukoncenia ulohy }
      i := Pos(':', s);
      if i = 0 then begin
        { riadok neobsahuje ':' - chyba v subore }
        writeln('Chyba v subore ', filename, ' na riadku ', l, '.');
        Halt(1);
      end;
      Val(Copy(s, 1, i - 1), pu^.d);
      Delete(s, 1, i);
      
      { no a nakoniec vaha ulohy (nic ine tam uz nie je) }
      Val(s, pu^.w);
      
      { ulozim ulohu do zoznamu uloh }
      if uloh = ULOH_MAX then begin
        { pole uloh je plne }
        writeln('Pole uloh je uz plne - zvyste prosim konstantu ULOH_MAX.');
        Halt(1);
      end;
      inc(uloh); ulohy[uloh] := pu;
    end; { if s <> '' and s[1] <> '#' }
  end; { while not(Eof(t) }
  
  Close(t);
end;

{ sluzi na vypisanie pola uloh }
procedure Vypis;
var
  i : integer;
  t : integer; { aktualny cas }
begin
  t := 0;
  for i := 1 to uloh do begin
    { vypis nazvu, zaciatku a konca vykonavania ulohy }
    write(ulohy[i]^.popis, '<', t, ',', t + ulohy[i]^.p, '> ');
    { posun cas na koniec vykonavania ulohy }
    t := t + ulohy[i]^.p;
  end;
  writeln;
end;

{ vypocet priemernej doby pobytu ulohy v systeme }
function Fpriem : real;
var
  i : integer;
  suma : longint;
begin
  { vypocet suctu dlzok pobytu uloh v systeme 
    S = p_1 + (p_1 + p_2) + (p_1 + p_2 + p_3) + ... = n * p_1 + (n - 1) * p_2 + (n - 2) * p_3 + .... }
  suma := 0;
  for i := 1 to uloh do begin
    suma := suma + (uloh - i + 1) * ulohy[i]^.p;
  end;
  Fpriem := suma / uloh;
end;

{ minimalizacia Fpriem => usporiadat ulohy podla casu spracovania vzostupne }
procedure MinFpriem;
var
  i : integer;
  temp : pUloha;
  prehodene : boolean;
begin
  { vypis aktualne usporadanie pola uloh }
  writeln('Pociatocne riesenie:');
  writeln('Fpriem = ', Fpriem:6:2);
  Vypis;
  writeln;
  
  { idem usporiadat pole uloh - bublinkove triedenie }
  repeat
    prehodene := false;
    for i := 1 to uloh - 1 do begin
      if ulohy[i]^.p > ulohy[i+1]^.p then begin
        temp := ulohy[i];
        ulohy[i] := ulohy[i+1];
        ulohy[i+1] := temp;
        prehodene := true;
      end;
    end;
    
    writeln('Priebezne riesenie:');
    writeln('Fpriem = ', Fpriem:6:2);
    Vypis;
    writeln;
  
  { ak uz nedoslo k prehodeniu prvkov, pole je utriedene }
  until not(prehodene);

  writeln('Vysledne riesenie:');
  writeln('Fpriem = ', Fpriem:6:2);
  Vypis;
  writeln;
end;

begin
  { vypis velkosti volnej pamate }
  writeln(MemAvail);
  
  { inicializacia a nacitanie pola uloh }
  Inicializacia;
  Nacitaj('uloha.txt');
  
  { optimalizacia rozvrhu podla priemernej doby pobytu ulohy v systeme (Fpriem) }
  MinFpriem;
  
  { uvolnenie alokovanej pamate }
  Koniec;
  
  { kontrolny vypis velkosti volnej pamate }
  writeln(MemAvail);
end.