Vopsirea gardului (Pregatire lot, Cluj, aprilie 1996)

        Pacala vrea sa-si vopseasca gardul din jurul casei. El are vopsele de 
diferite culori in cantitati precizate. Pacala stie ce lungime din gard poate 
vopsi cu continutul fiecarei cutii de vopsea. El este foarte econom, adica o 
cutie de vopsea inceputa o va folosi in intregime.
        Esti rugat sa-l ajuti sa-si planifice modul in care isi va vopsi gardul. 
Daca sunt mai multe solutii, programul va trebui sa afiseze cea care necesita 
numar minim de cutii de vopsea.
        Fisierul GARDx.IN contine:
pe linia 1:             lungimea gardului (L)
pe linia 2:             numarul cutiilor de vopsea (N)
pe urmatoarele N linii: un numar intreg care reprezinta lungimea gardului care 
se poate vopsi cu vopseaua dintr-o cutie, apoi dupa un blanc, culoarea vopselei
        In fisierul GARDx.OUT sau pe prima linie a ecranului se va afisa mesajul 
SE POATE VOPSI, respectiv NU SE POATE VOPSI. In caz afirmativ, pe linia 
urmatoare se va scrie numarul cutiilor folosite (M), iar pe urmatoarele M linii 
se vor afisa culorile vopselelor folosite si lungimile corespunzatoare ale 
gardului vopsit cu culoarea respectiva. Culoarea se va desparti printr-un blanc 
de lungime. In cazul in care gardul nu se poate vopsi, pe linia a doua se va 
preciza motivul, dupa caz, cu unul din mesajele:
        - NU ESTE SUFICIENTA VOPESA
        - NU ESTE FOLOSITA INTEGRAL O CUTIE.
=============================================

Solutia 1 (Tudor Leu)
uses crt;
type tip_cutie=record
                     lung,cul:word;
               end;
var ni,no:string;
    cutie:array[1..100] of tip_cutie;
    gard:array[0..1000] of word;
    c:array[0..1000] of byte;
    i,j,k,l,s,m,n:word;
procedure citeste;
begin
    write('Intrare : ');readln(ni);
    write('Iesire  : ');readln(no);
    assign(input,ni);reset(input);
    assign(output,no);rewrite(output);
    readln(l);
    readln(n);
    for i:=1 to n do readln(cutie[i].lung,cutie[i].cul);
end;
procedure imposibil;
begin
    writeln('NU SE POATE VOPSI.');
    writeln('NU ESTE SUFICIENTA VOPSEA.');
end;
procedure rezolva;
begin
    s:=0;
    for i:=1 to n do s:=s+cutie[i].lung;
    if s<l then begin imposibil;exit end;
    for i:=1 to l do gard[i]:=maxint;
    gard[0]:=0;m:=0;c[0]:=0;
    for i:=1 to n do
       for j:=0 to m do
          if (j+cutie[i].lung<=l) and
             (gard[j]+1<gard[j+cutie[i].lung]) then begin
                          gard[j+cutie[i].lung]:=gard[j]+1;
                          c[j+cutie[i].lung]:=i;
                          if m<j+cutie[i].lung then m:=j+cutie[i].lung
                                                   end;
    if gard[l]=maxint then begin
                             writeln('NU SE POATE VOPSI.');
                             writeln('NU ESTE FOLOSITA INTEGRAL O CUTIE.')
                           end
                      else begin
                             writeln('SE POATE VOPSI.');
                             writeln(gard[l]);
                             k:=l;
                             for i:=1 to gard[l] do begin
                                writeln(cutie[c[k]].cul,' ',cutie[c[k]].lung);
                                k:=k-cutie[c[k]].lung;
                             end;
                           end;
end;
begin
     clrscr;
     citeste;
     rezolva
end.
--------------------------
Solutia 2 (Mihai Stroe)
var i,j,k,l,m,n,d:longint;
    fi,fo:text;
    s:string;
    cul:array[1..100]of string[20];
    lung:array[1..100]of word;
    a:array[0..10000]of longint;
    t:array[1..10000]of byte;
    c:char;

procedure readdata;
begin
  write('Introduceti caracterul x (si apoi ENTER) ');
  readln(s);
  assign(fi,'gard'+s+'.in');
  assign(fo,'gard'+s+'.out');
  reset(fi);
  rewrite(fo);
  readln(fi,d);
  readln(fi,n);
  for i:=1 to n do
      readln(fi,lung[i],c,cul[i]);
  close(fi);
end;

procedure solve;
begin
  for i:=1 to n do
      m:=m+lung[i];
  if m<d then
     begin
       writeln(fo,'NU SE POATE VOPSI');
       writeln(fo,'NU ESTE SUFICIENTA VOPSEA');
       close(fo);
       halt;
     end;
  a[0]:=0;
  for i:=1 to d do
      a[i]:=-1;
  for i:=1 to n do
      begin
        for j:=d downto lung[i] do
            if a[j-lung[i]]<>-1 then
               if a[j]<a[j-lung[i]]+1 then
                  begin
                    a[j]:=a[j-lung[i]]+1;
                    t[j]:=i;
                  end;
      end;
  if a[d]=-1 then
     begin
       writeln(fo,'NU SE POATE VOPSI');
       writeln(fo,'NU ESTE FOLOSITA INTEGRAL O CUTIE.');
       close(fo);
       halt;
     end;
  writeln(fo,'SE POATE VOPSI');
  writeln(fo,a[d]);
  i:=d;
  while i>0 do
    begin
      writeln(fo,cul[t[i]],' ',lung[t[i]]);
      i:=i-lung[t[i]];
    end;
  close(fo);
end;

begin
  readdata;
  solve;
end.
-------------------------------
