ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1298. Knight

Posted by REM 8 Jun 2005 20:07
Program Acm_Timus_Ru_1298;
const dy:array [1..8] of integer=(-2,-2,-1,1,2,2,1,-1);
dx:array [1..8] of integer=(-1,1,2,2,1,-1,-2,-2);
g:array [1..8] of char=('a','b','c','d','e','f','g','h');

var a:array [-5..15,-5..15] of longint;
k,i,j,ip,min,h,x,y,rem:longint;
n                     : longint;
p                     : boolean;

Function mo(x,y:integer):boolean;
Begin
if (x>n) or (x<1) or (y>n) or (y<1) then mo:=false
else mo:=a[x,y]=0;
End;

Function hm(x,y:integer):byte;
Var i:integer;
Begin
k:=0;
if not(mo(x,y)) then k:=n*n
else for i:=1 to 8 do
if mo(x+dx[i],y+dy[i]) then k:=k+1;
hm:=k;
End;

BEGIN
if (n>=1) and (n<=8) then
begin
fillchar(a,sizeof(a),0);
x:=1;y:=1;
for i:=1 to n*n do
begin
min:=n*n;
a[x,y]:=i;
for j:=1 to 8 do
begin
h:=hm(x+dx[j],y+dy[j]);
if h<min then
begin
ip:=j;
min:=h;
end;
end;
x:=x+dx[ip];
y:=y+dy[ip];
end;
p:=true;
for i:=1 to n do
for j:=1 to n do
if a[i,j]=0 then p:=false;
if p=false then begin writeln('IMPOSSIBLE');end
else
for k:=1 to n*n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]=k then writeln(g[i],j);
end
else
writeln('IMPOSSIBLE');
END.
Posted by Nirjon 8 Jun 2005 23:14
I think the problem is here-

x:=x+dx[ip];
y:=y+dy[ip];

may be ip is invalid since it might not be updated. When all the neighbor squares return hm()>=min value, ip will not get updated.
Posted by KingPin 9 Jun 2005 01:50
It's very intresting!
I compiled given source code both on
Delphi and FreePascal and checked each
program on every possible tests (n from 1 to 8)
and I didn't get Access Violation.
I am really confused if this code get Access Violation
on Timus Judge System.
Posted by REM 9 Jun 2005 23:05
It's very interesting, I wrote a new program in which answers for 5,6,7,8 were constants (which I defined by my program which gets Crash on a server), and I got AC.
Posted by KingPin 9 Jun 2005 23:36
Can you give some clarification to this situation?
Is it a crash of the program or a Judge?
For n=2 the 'ip' variable is not initialized!
Posted by Vladimir Yakovlev (USU) 10 Jun 2005 08:20
Add ip:=7862341 line after BEGIN, and you'll get crash in both Delphi and FreePascal.
Re: For n=2 the 'ip' variable is not initialized!
Posted by KingPin 10 Jun 2005 13:50
I know that ip was not initialized.
Delphi gave that warning, but why
does the same program run different on
my home machine and on timus server.

I have no crashes on all possible tests.

How do you compile sources exactly?
Re: For n=2 the 'ip' variable is not initialized!
Posted by Vladimir Yakovlev (USU) 11 Jun 2005 16:55
If variable is not initialized it may have arbitrary value, that depends on many factors. It must work different on different machines!