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

Обсуждение задачи 1125. Классики

Why my program is so slow?
Послано Happy New Year! Russia. 4 янв 2002 01:14
My program:

Program t1125;

Const MaxN=50;

Var n,m,i,j,k  :longint;
    u,v,mov    :longint;
    pole       :array[1..MaxN,1..MaxN] of char;
    ch         :char;
    ok         :boolean;

Function Can(x1,y1,x2,y2:integer):boolean;
var dx,dy,dxy :integer;
    ok :boolean;
 begin
  if (x1=x2)or(y1=y2) then begin
   can:=true;
   exit;
  end;
  dx:=abs(x1-x2);
  dy:=abs(y1-y2);
  dxy:=trunc(sqrt(dx*dx+dy*dy));
  Can:= dxy*dxy = dx*dx + dy*dy ;
 end;

begin
assign(input,'1125.in');reset(input);
read(m,n);
for i:=1 to m do
 for j:=1 to n do begin
  ch:=' ';
  while (ch<>'W')and(ch<>'B') do read(ch);
  pole[i,j]:=ch;
 end;
for i:=1 to m do
 for j:=1 to n do begin
  read(k);
  if k mod 2=1 then
   for u:=1 to m do
    for v:=1 to n do
     if can(i,j,u,v) then begin
      if pole[u,v]='W' then
       pole[u,v]:='B' else pole[u,v]:='W';
     end;
 end;
for i:=1 to m do begin
 for j:=1 to n do
  write(pole[i,j]);
 writeln;
end;
end.
There are many ways to optimize your program, but I think the easiest is ....(+)
Послано shitty.Mishka 4 янв 2002 02:01
The easiest way, I suppose, is to create an array a: [0..5000] of
longint and in the beginning of the program fill it like this:
a[i]:=Trunc(Sqrt(i)), and then in procedure can use precalculated
values of Sqrt, beacuse Sqrt procedure is quite slow. Actually, you
don't really need to use it, but even with such a poor optimization
you'll get AC ;)
Good luck!
Thank you very much for your help !!! I get AC.
Послано Happy New Year! Russia. 4 янв 2002 02:18
> The easiest way, I suppose, is to create an array a: [0..5000] of
> longint and in the beginning of the program fill it like this:
> a[i]:=Trunc(Sqrt(i)), and then in procedure can use precalculated
> values of Sqrt, beacuse Sqrt procedure is quite slow. Actually, you
> don't really need to use it, but even with such a poor optimization
> you'll get AC ;)
> Good luck!