(*

Gli autobus (IOI 1994)
Copyright (C) 2000 Paolo Boldi

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*)
program Ioi9422;

(* Uno schedule Š una coppia <s,p> dove s Š l'istante del primo passaggio
   e p Š la frequenza. Diremo che lo schedule <s,p> Š ammissibile sse
   gli istanti s,s+p,s+2p,... sono registrati. Quanti sono gli schedule
   ammissibili? Notate che s<p; inoltre il secondo passaggio avviene a s+p
   e quindi deve essere s+p<=59, cioe' p<=59-s.
   Da questo si ha s<59-s, cioe' s<=29.
   Gli schedule ammissibili sono al massimo quanto tutte le coppie della forma
   <s,p>, con s<=29 e s+1<=p<=59-s.
   Quindi sono 58+56+54+...+2, cioe' 2(1+2+...+29)=29*30=870.
   Gli schedule ammissibili vengono precalcolati (procedura ammissibili)
   e messi nell'array sch. Per ogni schedule viene anche calcolato (campo
   pass) il numero complessivo di passaggi che verrebbero registrati
   per quello schedule *)


const maxbus=17;
      maxsch=870;
      nomefin='input-6.txt';
      nomefout='myout-6.txt';
      DEBUG=false;

type
    schedule=record
                   s,p,pass: byte;
             end;
var
   rec: array [0..59] of byte; (* Numero passaggi all'istante 0,1... *)
   passaggi: word;    (* Numero complessivo di passaggi *)
   nsch: word;          (* Numero schedule ammissibili *)
   sch: array [1..maxsch] of schedule;     (* Schedule ammissibili *)

procedure inp;
(* Lettura dell'input *)
var f: text;
    i,j: integer;
begin
     assign(f,nomefin);
     reset(f);
     read(f,passaggi);
     for i:=0 to 59 do rec[i]:=0;
     for i:=1 to passaggi do
         begin
              read(f,j);
              inc(rec[j]);
         end;
     close(f)
end;

function ammissibile(s: schedule; c: integer; var pass: byte): boolean;
(* Guarda se lo schedule s Š ammissibile rispetto a rec. Inoltre, aggiunge
   c ad ogni elemento di rec che soddisfa lo schedule (l'effetto non Š
   determinato se lo schedule non Š ammissibile, quindi si assume che lo
   sia se c<>0). In pass viene calcolato il numero di passaggi relativi
   a quello schedule (se e' ammissibile) *)
var t: byte;
    amm: boolean;
begin
     t:=s.s;
     pass:=0;
     amm:=true;
     while (t<60) and (amm) do
           begin
                if (rec[t]=0) and (c=0) then amm:=false;
                inc(pass);
                rec[t]:=rec[t]+c;
                passaggi:=passaggi+c;
                t:=t+s.p
           end;
     ammissibile:=amm
end;

procedure ammissibili;
(* Calcola tutti gli schedule ammissibili rispetto a rec e li mette nell'array
   sch *)
var s: schedule;
    pass: byte;
begin
     nsch:=0;
     for s.s:=0 to 29 do
         for s.p:=s.s+1 to 59-s.s do
             if (ammissibile(s,0,pass)) then
                begin
                     inc(nsch);
                     sch[nsch]:=s;
                     sch[nsch].pass:=pass
                end
end;

procedure ordinaammissibili;
(* L'array sch viene ordinato in ordine descrescente di pass.
   Ordinamento per selezione *)
var i,j,maxi: word;
    t: schedule;
begin
     for i:=1 to nsch-1 do
         begin
              maxi:=i;
              for j:=i+1 to nsch do
                  if (sch[j].pass>sch[maxi].pass) then maxi:=j;
              t:=sch[maxi]; sch[maxi]:=sch[i]; sch[i]:=t
         end
end;

(* Una soluzione Š una sequenza di al pi— 17 schedule, in cui la prima sia
   ammissibile rispetto a rec, la seconda ammissibile rispetto a rec dopo la
   prima ecc. *)

type
    soluzione=record
                    nbus: byte;
                    bus: array [1..17] of word
              end;

var
   ottimo: soluzione;

procedure outsol(var f: text; sol: soluzione);
(* Output sul file f della soluzione sol *)
var i: byte;
begin
     for i:=1 to sol.nbus do
         writeln(f,sch[sol.bus[i]].s,' ',sch[sol.bus[i]].p);
end;

procedure cercaottimo(sol: soluzione);
(* Quando la procedura viene invocata, sol Š una soluzione parziale, e
   rec Š aggiornato in base agli schedule di sol. Se sol Š una soluzione
   non definitiva, prova a prolungarla *)
var start,i: word;
    unused: byte;
begin
     if (passaggi=0) then
        (* Si tratta di una soluzione completa *)
        begin
             if (sol.nbus<ottimo.nbus) then
                begin
                     ottimo:=sol;
                     if (DEBUG) then
                        begin
                             writeln('Ottimo corrente: ');
                             outsol(output,ottimo)
                        end
                end
        end
     else
     if (sol.nbus+1<ottimo.nbus) and (sol.nbus<17) then
        (* La soluzione pu• dare luogo a un ottimo: proviamo
           a prolungarla *)
        begin
             if (sol.nbus=0) then start:=1 else start:=sol.bus[sol.nbus];
             inc(sol.nbus);
             for i:=start to nsch do
                 begin
                 if (sch[i].pass*(ottimo.nbus-sol.nbus)<passaggi)
                    then break;
                 (* Inutile tentare di prolungare la soluzione con schedules
                    di indice i o maggiore: troppo pochi passaggi! *)
                 if (ammissibile(sch[i],0,unused)) then
                    begin
                         ammissibile(sch[i],-1,unused);
                         sol.bus[sol.nbus]:=i;
                         cercaottimo(sol);
                         ammissibile(sch[i],1,unused)
                    end
                 end
        end
end;

procedure outputtest(sol: soluzione);
(* Chiamato solo se DEBUG. Produce un file text.txt che deve essere identico
   al file di input (sol Š la soluzione che viene scritta) *)
var rec: array [0..59] of byte;
    passaggi: word;
    i,j,t: byte;
    f: text;
begin
     passaggi:=0;
     for i:=0 to 59 do rec[i]:=0;
     for i:=1 to sol.nbus do
         begin
              t:=sch[sol.bus[i]].s;
              while (t<60) do
                    begin
                         inc(rec[t]);
                         inc(passaggi);
                         t:=t+sch[sol.bus[i]].p
                    end
         end;
     assign(f,'test.txt');
     rewrite(f);
     writeln(f,passaggi);
     for i:=0 to 59 do
         for j:=1 to rec[i] do
             write(f,i,' ');
     close(f)
end;

var sol: soluzione;
    f: text;

begin
     inp;
     ammissibili;
     ordinaammissibili;
     ottimo.nbus:=100;
     sol.nbus:=0;
     cercaottimo(sol);
     assign(f,nomefout);
     rewrite(f);
     outsol(f,ottimo);
     close(f);
     if (DEBUG) then outputtest(ottimo)
end.