so - I have made my own code in Pascal - and got WA, although I have perfect agreement with the test case provided in the task. Can someone me provide the test case against which my code gives WA as it is executed by judge?
So - as judge doesn't support TStringList and any serious map-type collection, then I had to use fixed size 2D array tForwards for forwarding command data - the each row contains data about all forwards from one source and each element in row contains data about single forwards - targe, initial time and time period (extension). I have used also some additional arrays to reduce time for sorting (when one should find the path how call is forwarded).
Can some help me to get accepted this task by judge?!!!
A lot of thanks for any help in advance!!!
p.s. as I have observed - then there can be cases when some runtime error (e.g. array index outside boundaries) can be given as WA by judge) - if it is so in this case as well - then it would be so great to get know about this!!!
Code: Select all
program Prg3800(input, output);
{$APPTYPE CONSOLE}
uses
SysUtils; {Classes for TStringList}
type TExt=record
time: Integer;
ext: Integer; //duration
target: Integer;
end;
var //Forwards: array of array of TExt;
tForwards: array [1..100] of array [1..100] of TExt;
{not support for dynamic arrays in free pascal -
maybe only through pointers?}
sources: array [1..100] of Integer; //sources[i]
indices: array [1..100] of Integer; //indices[i]->tForwards[indices[i]]
numberOfSystems: SmallInt;
source,time,duration,target,extension: SmallInt;
notEndOfData,sourceFound: Boolean;
i,j,k: Integer;
numberOfRequests: Integer;
maxSource: Integer;
numberOfTimes: array [1..100] of Integer;
maxTimes: array [1..100] of Integer;
minTimes: array [1..100] of Integer;
nextI: Integer;
procedure addForwardTime(aIndex,aTime,aDuration,aTarget: Integer);
var ii,jj: Integer;
begin
if aTime>maxTimes[aIndex] then begin
tForwards[aIndex][numberOfTimes[aIndex]+1].time:=aTime;
tForwards[aIndex][numberOfTimes[aIndex]+1].ext:=aDuration;
tForwards[aIndex][numberOfTimes[aIndex]+1].target:=aTarget;
maxTimes[aIndex]:=aTime+aDuration;
if (numberOfTimes[aIndex]=0) then begin
minTimes[aIndex]:=aTime;
end;
end else begin // if...
ii:=1;
while ( aTime<tForwards[aIndex][ii].time ) do
inc(ii);
//ii - the index of the first time which is greater that the
//new time, so - time[ii] should give place for new time
for jj:=numberOfTimes[aIndex] downto ii do begin
tForwards[aIndex][jj+1].time:=tForwards[aIndex][jj].time;
tForwards[aIndex][jj+1].ext:=tForwards[aIndex][jj].ext;
tForwards[aIndex][jj+1].target:=tForwards[aIndex][jj].target;
end;
tForwards[aIndex][ii].time:=aTime;
tForwards[aIndex][ii].ext:=aDuration;
tForwards[aIndex][ii].target:=aTarget;
if (ii=1) then begin
minTimes[aIndex]:=aTime;
end;
end; // if...
numberOfTimes[aIndex]:=numberOfTimes[aIndex]+1;
end; // procedure
function findTarget(aExtension,aTime,initialTarget: Integer): Integer;
var ii,jj: Integer;
sourceHasData,timeIsFound: Boolean;
fwdIndex: Integer;
tmpTarget: Integer;
begin
if ( (aExtension>maxSource) or
(aExtension<sources[1])
) then begin
Result:=aExtension;
exit;
end;
//it is possile that we have data for this source
sourceHasData:=false;
ii:=1;
while ( (ii<=numberOfRequests) and
(not sourceHasData)
) do begin
if sources[ii]=aExtension
then sourceHasData:=true
else inc(ii); //MXX
end;
if (not sourceHasData) then begin
Result:=aExtension;
exit;
end else begin
//extension has additional data - so - check time
fwdIndex:=indices[ii];
if ( (aTime<minTimes[ii]) or
(aTime>maxTimes[ii])
) then begin
Result:=aExtension;
exit;
end else begin
timeIsFound:=false;
jj:=1;
// in while condition: ii changed to jj!!! and added =
while ( (jj<=numberOfTimes[ii]) and
(not timeIsFound)
) do begin
if ( (aTime>=tForwards[fwdIndex][jj].time) and
(aTime<=(tForwards[fwdIndex][jj].time+
tForwards[fwdIndex][jj].ext)
)
) then begin
timeIsFound:=true;
tmpTarget:=tForwards[fwdIndex][jj].target;
end else begin
inc(jj);
end;
end; //while
if timeIsFound then begin
if tmpTarget=initialTarget then begin
Result:=9999;
exit;
end else begin
Result:=findTarget(tmpTarget,aTime,initialTarget);
exit;
end;
end else begin
Result:=aExtension;
exit;
end; //if timeIsFound then...
end; //check - whether time is inside interval about which we have data
end; //if (not sourceHasData) then ...
end; //function
function intToSpecString(num: integer): string;
{the result for number with more than 4 cipher is not specified}
var res: String;
begin
res:=intToStr(num);
case length(res) of
0: res:='0000';
1: res:='000'+res;
2: res:='00'+res;
3: res:='0'+res;
end;
Result:=res;
end; //function
begin
{
AssignFile(Input, 'in03__.txt');
Reset(Input);
AssignFile(Output, 'out03__.txt');
Rewrite(Output);
}
{for each i there is entry in indices[...] and sources[...], where
sources[...] contain the actual values of source, but indices[...] - the
index at which the forwarding data from that source is located at tForwards
array.
tForwards is 2D array - one row for each source and in this row: - one
element for each actual forwarding, all the forwardings are ordered in row;
the number of forwardings from source is contained in numberOfTimes[...]}
writeln('CALL FORWARDING OUTPUT');
numberOfRequests:=0;
for i:=1 to 100 do
numberOfTimes[i]:=0;
read(numberOfSystems);
readln;
for i:=1 to numberOfSystems do begin
writeln('SYSTEM '+IntToStr(i));
notEndOfData:=true;
// making data structure
while(notEndOfData) do begin
read(source);
if (source<>0) then begin
read(time);
read(duration);
read(target);
//add entry to data structure;
j:=1;
sourceFound:=false;
while ( (source<=maxSource) and //MXX - in both tests = added
(j<=numberOfRequests) and
(not sourceFound)
) do begin
if (source=sources[j])
then sourceFound:=true;
inc(j);
end;
if sourceFound then begin
//entry is found - so - simply add time/duration/extension data
addForwardTime(indices[j-1],time,duration,target);
end else begin
//no entry is found for source - so add new entry -
//check - where to put it - at the top of array - or iside it
if (source<maxSource) then begin
//the new element is inserted inside the array - nextI is the
//place where new source is going
nextI:=0;
while source>sources[nextI] do Inc(nextI);
for k:=numberOfRequests downto nextI do begin
indices[k+1]:=indices[k];
end;
indices[nextI]:=numberOfRequests+1;
addForwardTime(indices[nextI],time,duration,target);
numberOfRequests:=numberOfRequests+1;
end else begin //if (source<maxSource)...
//the new element is put at the top of array
indices[numberOfRequests+1]:=numberOfRequests+1;
sources[numberOfRequests+1]:=source;
maxSource:=source;
addForwardTime(indices[numberOfRequests+1],time,duration,target);
numberOfRequests:=numberOfRequests+1;
end; //if (source<maxSource)...
end; // if sourceFound...
end else begin // if source<>0 ...
notEndOfData:=false;
end; // if source<>0 ...
readln;
end; // while ...
//now we have data structure - we are employing it for call target
//determination
notEndOfData:=true;
while (notEndOfData) do begin
read(time);
if (time<>9000) then begin
read(extension);
target:=findTarget(extension,time,extension);
writeln('AT '+intToSpecString(time)+
' CALL TO '+intToSpecString(extension)+
' RINGS '+intToSpecString(target));
end else begin
notEndOfData:=false;
end;
readln;
end;
end; // for ... numberOfSystems
writeln('END OF OUTPUT');
end.
