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

Discussion of Problem 1125. Hopscotch

Why my program is so slow?
Posted by Happy New Year! Russia. 4 Jan 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 ....(+)
Posted by shitty.Mishka 4 Jan 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.
Posted by Happy New Year! Russia. 4 Jan 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!