lacusta oji 2005

[•sori]

La problema lacusta de la OJI , eu am facut un lee pana la ultima linie exceptand coltu dreapta-jos.Intr-o matrice cost retineam costul minim.
La sf. afisam minimul dintre costurile ultimei linii + valoarea din coltul dreapta jos (cea initiala);  
                Am luat 60 puncte .    Ce am gresit? sau Ce as putea face in plus pentru 100 ? Imi afiseaza gresit la celelalte teste .   Nu mi-am permis sa testez pas cu pas pentru ca cel mai mic test picat are o matrice a[100][35]. Nu vreau sa pierd craciunu.

[•domino]

La problema lacusta de la OJI , eu am facut un lee pana la ultima linie exceptand coltu dreapta-jos.Intr-o matrice cost retineam costul minim.
La sf. afisam minimul dintre costurile ultimei linii + valoarea din coltul dreapta jos (cea initiala);  
                Am luat 60 puncte .    Ce am gresit? sau Ce as putea face in plus pentru 100 ? Imi afiseaza gresit la celelalte teste .   Nu mi-am permis sa testez pas cu pas pentru ca cel mai mic test picat are o matrice a[100][35]. Nu vreau sa pierd craciunu.

Eu ma gandeam la o dinamica A[j] = cost minim sa ajungi in (i, j) si  ultima miscare facuta ca sa ajungi in (i, j) sa fie o deplasare pe orizontala. Si ar veni ceva de genu A[j] = min(A[i - 1][k] + M[k]) + M[j] (M e matricea initiala) .. sper sa fie ok  

[•sori]

Din cate stiu eu algoritmul lui Lee e dinamic. Poate gresesc....

Matricea mea cost[j] calcula intradevar costul minim sa ajung in (i,j)
dar in matricea initiala eu trebuia sa fac un salt si o deplasare in jos(exceptand ultima linie in care trebuia sa fac doar un salt).

Asa am facut si mi-a dat doar 60 puncte.Am cautat solutie dar n-am gasit decat teste si tester.

[•fbkk]

E departe d a fi solutie oficiala dar ia testele

Cod:

program p1130101;
const MAX_WORD = 65530;
var inp,out: text;
    a: array[1..100,1..100] of byte;
    d: array[1..100,1..100] of word;
    m,n,i,j: byte;
    min2,j_min: word;

procedure mat_cob;   { transforma matricea in mat coborari }
var i,j: byte;
begin
  for i:=1 to m-1 do
      for j:=1 to n do
          d[i,j] := a[i+1,j] + a[i,j];
  d[1,1] := MAX_WORD;
end;

function get_l_min(i: byte): word;
var j: byte;
    min: word;
begin
  min := MAX_WORD;
  min2 := MAX_WORD;
  for j:=1 to n do
      if d[i,j] < min then
         begin
           { min2 := min; } { min2 NU este intotdeauna det corect }
           { greseala FATALA :((( }
           min := d[i,j];
           j_min:= j;
         end;

  for j:=1 to n do             { varianta corecta }       
      if (d[i,j] < min2) and (j <> j_min) then
         min2 := d[i,j];       {  /varianta corecta  :((( }

  get_l_min := min;
end;

procedure get_min;
var i,j: byte;
    l_min : word;
begin

  for i:=2 to m-1 do
      begin
        l_min := get_l_min(i-1);
        for j:=1 to n do
            if j <> j_min then
               d[i,j] := d[i,j] + l_min
            else
               d[i,j] := d[i,j] + min2;
      end;
  d[m-1,n] := MAX_WORD;

end;

begin
  assign(inp, 'lacusta.in');
  reset(inp);
  assign(out, 'lacusta.out');
  rewrite(out);

  readln(inp, m,n);
  for i:=1 to m do
      begin
        for j:=1 to n do
            read(inp,a[i,j]);
        readln(inp);
      end;

  mat_cob;
  get_min;

{  writeln('*********************************');
  for i:=1 to m do
      begin
        for j:=1 to n do
            write(d[i,j]:6);
        writeln;
      end; }

  if (m = 0) or (n = 0) then
     writeln(out,0)
  else
     writeln(out,get_l_min(m-1)+a[1,1]+a[m,n]);

  close(inp);
  close(out);
end.

Fara commentarii (explicatii) ,exact ca o solutie oficiala

d este a doua matrice in d[i,j] tin initial suma(a[i,j]+a[i+1,j]) adica costul coborarii d la a[i,j] la a[i+1,j] ;
Shi dupa aia d[i,j] -> d[i,j]  + min(d[i-1,1..n])
drumul minim il gasesti ca fiind min(d[m-1,1..n]) (adica minimul de pe ultima linie)
La solutia finala adaugi primul shi ultimul element al matricei (prin care oricum treci)
O PD BANALA care merge in O(N*M);
Si p care am luat 20 p      

Sper ca te-a ajutat !
P.S.: daca ai nevoie de  o varianta C sa zici !

[•fbkk]

LOL Rezolvarea mea e exact sol oficiala , pe care o gasesti la
http://olimpiada.info/oji2005/index.php?cid=arhiva
,doar ca implementata in pascal  LOOOLLLLLLL

     

[•svalentin]

Eu ma gandeam la o dinamica A[j] = cost minim sa ajungi in (i, j) si  ultima miscare facuta ca sa ajungi in (i, j) sa fie o deplasare pe orizontala. Si ar veni ceva de genu A[j] = min(A[i - 1][k] + M[k]) + M[j] (M e matricea initiala) .. sper sa fie ok  

Asta am facut si eu, dar mai trebuie sa ai grija sa nu iei elementul exact de deasupra ta! (adica k diferit de j) si pt linia 2 sa nu iei k=1, iar pt penultima linie sa nu iei ultimul element!

[•sarabogdan]

Fix asta am gresit eu.....am luat asa numai 60!
De eram mai atent ma calificam

[•fbkk]

Ca idee era banala , ca implementare shi mai banala = > 20 p llllloooooooolll
     

[•mariancon]

type matrice=array[1..255,1..255] of word;
var f,g: text;
     a,d:matrice;
    m,n,i,j: byte;
   max,min2,j_min: word;
 
procedure combin;
var i,j: byte;
begin
  for i:=1 to m-1 do
      for j:=1 to n do
          d[i,j] := a[i+1,j] + a[i,j];
  d[1,1] :=max;
end;
 
function get_l_min(i: byte): word;
var j: byte;
    min: word;
begin
  min := max;
  min2 := max;
  for j:=1 to n do
      if d[i,j] < min then
         begin
           min := d[i,j];
           j_min:= j;
         end;
 
  for j:=1 to n do
      if (d[i,j] < min2) and (j <> j_min) then
         min2 := d[i,j];
 
  get_l_min := min;
end;
 
procedure min;
var i,j: byte;
    l_min : word;
begin
 
  for i:=2 to m-1 do
      begin
        l_min := get_l_min(i-1);
        for j:=1 to n do
            if j <> j_min then
               d[i,j] := d[i,j] + l_min
            else
               d[i,j] := d[i,j] + min2;
      end;
  d[m-1,n] :=max;
 
end;
 
begin
  assign(f, 'lacusta.in');
  reset(f);
  assign(g, 'lacusta.out');
  rewrite(g);
  max:=65530;
  readln(f,m,n);
  for i:=1 to m do
      begin
        for j:=1 to n do
            read(f,a[i,j]);
        readln(f);
      end;
 
  combin;
  min;
 
 
 
     writeln(g,get_l_min(m-1)+a[1,1]+a[m,n]);
 
  close(f);
  close(g);
end.
solutia oficiala in pascal iei 100p cu ea