ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Common Board

Could someone test this...please
Posted by Vladimir Milenov Vasilev 15 Dec 2001 23:30
It is about the ministry. I can't uderstand what is wrong with my
solution. If you could please test it. Thanks!!!

program ministry;
{$N+}
const mi=100;ma=500;
var n,m,i,j,k,p,pom:integer;
    max,min,sum:extended;
    a:array[1..mi,1..ma]of longint;
    b:array[1..mi,1..ma]of extended;
    dir,brnext:array[1..mi,1..ma]of integer;
    {t:text;}
begin
{assign(t,'ministry.in');
reset(t);}
readln({t,}n,m);
for k:=1 to n do
for p:=1 to m do
begin
read({t,}a[k,p]);
brnext[k,p]:=p;
dir[k,p]:=0;
end;
{close(t);
assign(t,'ministry.out');
rewrite(t);}
if n=1
 then
  begin
   max:=a[1,1];
   pom:=1;
   for i:=1 to m do
    if  a[1,i]<max
     then
      begin
       max:=a[1,i];
       pom:=i;
      end;
   writeln({t,}pom);
   {close(t);}
   exit;
  end;
for k:=1 to m do b[n,k]:=a[n,k];
for i:=n-1 downto 1 do
 begin
  for j:=1 to m do
   begin
    min:=b[i+1,j]+a[i,j];
    sum:=a[i,j];
    for pom:=j-1 downto 1 do
     begin
      sum:=sum+a[i,pom];
      if (sum+b[i+1,pom]<min)
       then
        begin
         min:=sum+b[i+1,pom];
         brnext[i,j]:=pom;
        end;
     end;
    sum:=a[i,j];
    for pom:=j+1 to m do
     begin
      sum:=sum+a[i,pom];
      if(sum+b[i+1,pom]<min)
       then
        begin
         min:=sum+b[i+1,pom];
         brnext[i,j]:=pom;
         dir[i,j]:=1;
        end;
      end;
    b[i,j]:=min;
   end;
 end;
{for pom:=n downto 1 do
 begin
  for i:=1 to m-1 do write(t,b[pom,i]:1:3,' ');
  writeln(t,b[pom,m]:1:3);
 end;}
pom:=1;
min:=b[1,1];
for i:=2 to m do
 if (b[1,i]<min)
  then
   begin
    pom:=i;
    min:=b[1,i];
   end;
writeln({t,}pom);
for i:=2 to n-1 do
 begin
  writeln({t,}pom);
  if dir[i,pom]=0 then for j:=pom-1 downto brnext[i,pom] do writeln
({t,}j)
  else for j:=pom+1 to brnext[i,pom]do writeln({t,}j);
  if dir[i,pom]=0 then pom:=brnext[i,pom]
  else pom:=brnext[i,pom]
 end;
writeln({t,}pom);
{close(t);}
end.
Re: Could someone test this...please
Posted by Miguel Angel 18 Dec 2001 11:02
You are not counting the value acumulated until the data, you may have
b[i,j] = b[i+1,j]+a[i,j]
and then use this value b[i,j] to check to their sides, not, a[i,j]
Hope this help you :)

for k:=1 to m do b[n,k]:=a[n,k];
for i:=n-1 downto 1 do
 begin
  for j:=1 to m do
   begin
    min:=b[i+1,j]+a[i,j];
    sum:=a[i,j];   /*************Use min************/
    for pom:=j-1 downto 1 do
     begin
      sum:=sum+a[i,pom];/**Use min*/
      if (sum+b[i+1,pom]<min)
       then
        begin
         min:=sum+b[i+1,pom];
         brnext[i,j]:=pom;
        end;
     end;
    sum:=a[i,j];
    for pom:=j+1 to m do
     begin
      sum:=sum+a[i,pom];
      if(sum+b[i+1,pom]<min)
       then
        begin
         min:=sum+b[i+1,pom];
         brnext[i,j]:=pom;
         dir[i,j]:=1;
        end;
      end;
    b[i,j]:=min;
   end;
 end;