Imprimă pagina - lacusta oji 2005

Titlul: lacusta oji 2005
Scris de: Andreica din Februarie 27, 2005, 19:51:19

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.

Titlul: Re: lacusta oji 2005
Scris de: Mircea Pasoi din Februarie 27, 2005, 20:52:42

Citat din mesajul lui: sori

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 :-'

Titlul: lacusta oji 2005
Scris de: Andreica din Februarie 27, 2005, 21:04:02

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.

Titlul: lacusta oji 2005
Scris de: florin din Februarie 27, 2005, 23:39:51

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 :P

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 !

Titlul: lacusta oji 2005
Scris de: florin din Februarie 28, 2005, 11:36:08

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

](*,) ](*,) ](*,)

Titlul: Re: lacusta oji 2005
Scris de: Valentin Stanciu din Februarie 28, 2005, 12:22:51

Citat din mesajul lui: domino

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!

Titlul: lacusta oji 2005
Scris de: Sara Nicolae Bogdan din Februarie 28, 2005, 15:27:14

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

Titlul: lacusta oji 2005
Scris de: florin din Februarie 28, 2005, 18:09:31

Ca idee era banala , ca implementare shi mai banala = > 20 p llllloooooooolll
](*,) ](*,) ](*,)

Titlul: RÄƒspuns: lacusta oji 2005
Scris de: Constantin marian din Martie 01, 2013, 11:04:19

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Andreica din Februarie 27, 2005, 19:51:19