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

Обсуждение задачи 1119. Метро

Help! Why it's always wrong?
Послано meoden 16 апр 2002 15:30
It's seem a simple algo. But I can't find where my mistake's.
Here is my code. Thanks.

const maxk=1000;
var n,m,k:integer;
    a,x,y:array[1..maxk] of integer;

procedure inputdata;
var i:integer;
begin
   readln(n,m);
   readln(k);
   for i:=1 to k do readln(x[i],y[i]);
end;

procedure sort;
var i,j,tg:integer;
begin
   for i:=1 to n do
   for j:=i+1 to n do
   if (x[j]<x[i]) then
   begin
      tg:=x[i]; x[i]:=x[j]; x[j]:=tg;
      tg:=y[i]; y[i]:=y[j]; y[j]:=tg;
   end;
end;

procedure solve;
var i,j:integer;
begin
   for i:=1 to k do a[i]:=1;

   for i:=2 to k do
   for j:=1 to i-1 do
   if (x[j]<x[i]) and (y[j]<y[i]) then
   if a[i]<a[j]+1 then a[i]:=a[j]+1;
end;

procedure outputdata;
var i,max:integer;
    s:real;
begin
   max:=0;
   for i:=1 to k do if a[i]>max then max:=a[i];
   s:=(m+n-2*max)*100+sqrt(2)*100*max;
   writeln(s:0:0);
end;

begin
   inputdata;
   sort;
   solve;
   outputdata;
end.
Sort by "y" too (-)
Послано Miguel Angel 16 апр 2002 23:25
> It's seem a simple algo. But I can't find where my mistake's.
> Here is my code. Thanks.
>
> const maxk=1000;
> var n,m,k:integer;
>     a,x,y:array[1..maxk] of integer;
>
> procedure inputdata;
> var i:integer;
> begin
>    readln(n,m);
>    readln(k);
>    for i:=1 to k do readln(x[i],y[i]);
> end;
>
> procedure sort;
> var i,j,tg:integer;
> begin
>    for i:=1 to n do
>    for j:=i+1 to n do
>    if (x[j]<x[i]) then
>    begin
>       tg:=x[i]; x[i]:=x[j]; x[j]:=tg;
>       tg:=y[i]; y[i]:=y[j]; y[j]:=tg;
>    end;
> end;
>
> procedure solve;
> var i,j:integer;
> begin
>    for i:=1 to k do a[i]:=1;
>
>    for i:=2 to k do
>    for j:=1 to i-1 do
>    if (x[j]<x[i]) and (y[j]<y[i]) then
>    if a[i]<a[j]+1 then a[i]:=a[j]+1;
> end;
>
> procedure outputdata;
> var i,max:integer;
>     s:real;
> begin
>    max:=0;
>    for i:=1 to k do if a[i]>max then max:=a[i];
>    s:=(m+n-2*max)*100+sqrt(2)*100*max;
>    writeln(s:0:0);
> end;
>
> begin
>    inputdata;
>    sort;
>    solve;
>    outputdata;
> end.
But it's still WA when I sort by x and y.
Послано meoden 17 апр 2002 10:45
> > It's seem a simple algo. But I can't find where my mistake's.
> > Here is my code. Thanks.
> >
> > const maxk=1000;
> > var n,m,k:integer;
> >     a,x,y:array[1..maxk] of integer;
> >
> > procedure inputdata;
> > var i:integer;
> > begin
> >    readln(n,m);
> >    readln(k);
> >    for i:=1 to k do readln(x[i],y[i]);
> > end;
> >
> > procedure sort;
> > var i,j,tg:integer;
> > begin
> >    for i:=1 to n do
> >    for j:=i+1 to n do
> >    if (x[j]<x[i]) then
> >    begin
> >       tg:=x[i]; x[i]:=x[j]; x[j]:=tg;
> >       tg:=y[i]; y[i]:=y[j]; y[j]:=tg;
> >    end;
> > end;
> >
> > procedure solve;
> > var i,j:integer;
> > begin
> >    for i:=1 to k do a[i]:=1;
> >
> >    for i:=2 to k do
> >    for j:=1 to i-1 do
> >    if (x[j]<x[i]) and (y[j]<y[i]) then
> >    if a[i]<a[j]+1 then a[i]:=a[j]+1;
> > end;
> >
> > procedure outputdata;
> > var i,max:integer;
> >     s:real;
> > begin
> >    max:=0;
> >    for i:=1 to k do if a[i]>max then max:=a[i];
> >    s:=(m+n-2*max)*100+sqrt(2)*100*max;
> >    writeln(s:0:0);
> > end;
> >
> > begin
> >    inputdata;
> >    sort;
> >    solve;
> >    outputdata;
> > end.
I didn't run in pascal but i almost sure is this fact (+)
Послано Miguel Angel 17 апр 2002 10:58
> It's seem a simple algo. But I can't find where my mistake's.
> Here is my code. Thanks.
>
> const maxk=1000;
> var n,m,k:integer;
>     a,x,y:array[1..maxk] of integer;
>
> procedure inputdata;
> var i:integer;
> begin
>    readln(n,m);
>    readln(k);
>    for i:=1 to k do readln(x[i],y[i]);
> end;
>
> procedure sort;
> var i,j,tg:integer;
> begin
>    for i:=1 to n do
>    for j:=i+1 to n do
>    if (x[j]<x[i]) then
>    begin
>       tg:=x[i]; x[i]:=x[j]; x[j]:=tg;
>       tg:=y[i]; y[i]:=y[j]; y[j]:=tg;
>    end;
> end;
>
> procedure solve;
> var i,j:integer;
> begin
>    for i:=1 to k do a[i]:=1;
>
>    for i:=2 to k do
>    for j:=1 to i-1 do
>    if (x[j]<x[i]) and (y[j]<y[i]) then
>    if a[i]<a[j]+1 then a[i]:=a[j]+1;
> end;
>
> procedure outputdata;
> var i,max:integer;
>     s:real;
> begin
>    max:=0;
>    for i:=1 to k do if a[i]>max then max:=a[i];
>    s:=(m+n-2*max)*100+sqrt(2)*100*max;<---------------If k = 0?????
>    writeln(s:0:0);<--------this leads to 0, incorrect
> end;<---i mean, check if there're not diagonals
>
> begin
>    inputdata;
>    sort;
>    solve;
>    outputdata;
> end.
Thanks. Now I've fixed it.
Послано meoden 18 апр 2002 13:04