ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Общий форум

Could someone test this...please
Послано Vladimir Milenov Vasilev 15 дек 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
Послано Miguel Angel 18 дек 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;