{
Solution for RACE
-------- --- ----
The data structure for a course is as follows:
CONST Max_Arrows = 100;
VAR number_of_points,number_of_arrows : INTEGER;
Arrows : ARRAY [0..Max_Arrows-1,0..1] OF INTEGER;
The number of the start point is 0,
the number of the finish point is number_of_points-1.
The i-th arrow (0 <= i <= number_of_arrows-1) goes from the point with
number Arrows[i,0] to the point with number Arrows[i,1].
The data structure for the solution of the task is as follows:
CONST Max_points = 50;
TYPE Point_array = ARRAY [0..Max_points-1] OF BOOLEAN;
VAR number_unavoidable_points,number_splitting_points : INTEGER;
unavoidable,splitting : Point_array;
number_unavoidable_points is the number of unavoidable points
(apart from the start point and the finish point).
number_splitting_points is the number of splitting points.
unavoidable[N] is TRUE iff the point with number N is an unavoidable point.
splitting[N] is TRUE iff the point with number N is a splitting point.
The main body of the program is:
BEGIN
initialisation;
read_input;
compute_results;
write_output;
finalisation;
END.
The procedure initialisation initialises the variables mentioned above
and file variables for input and output.
The procedure read_input reads the input; the variables of the data
structure for the course receive their final value.
The procedure compute_results computes the results; the variables of
the data structure for the solution of the task receive their final value.
The procedure write_output writes the output to the appropriate file.
The procedure finalisation closes the files.
We will only consider the procedure compute_results from here, as the
implementation of the other procedures is straightforward.
The procedure compute_results determines for each point (except start
point and finish point) whether it is an unavoidable point, and if so,
whether it is a splitting point (Note that each splitting point is an
unavoidable point as well).
To determine whether current_point is an unavoidable point, determine
the set S of all points which can be reached from the start point via a
path which does not contain current_point. Obviously current_point is
an unavoidable point iff the finish point is not in S.
S is determined by calling the procedure find_reachable with current_point
as argument. The result is stored in the Point_array reachable. After the
call find_reachable (current_point) the value of reachable[N] is TRUE iff
point N can be reached from the start point via a path which does not contain
current_point. By definition, reachable [current_point] is FALSE.
Careful analysis now shows that current_point is a splitting point iff
there is no arrow from a point P with reachable[P] = FALSE to a point Q
with reachable[Q] = TRUE. This is checked by the function is_splitting.
Below the complete code is given:
}
PROGRAM RACE;
CONST Max_points = 50;
Max_Arrows = 100;
TYPE Point_array = ARRAY [0..Max_points-1] OF BOOLEAN;
VAR input_file,output_file : text;
current_arrow,current_point,number_of_points,number_of_arrows,
number_unavoidable_points,number_splitting_points : INTEGER;
Arrows : ARRAY [0..Max_Arrows-1,0..1] OF INTEGER;
unavoidable,splitting : Point_array;
PROCEDURE initialisation;
BEGIN
Assign(input_file,'input.txt');
Reset(input_file);
Assign(output_file,'output.txt');
Rewrite(output_file);
number_of_points:=1;
number_of_arrows:=0;
number_unavoidable_points:=0;
number_splitting_points:=0;
FOR current_point:=0 TO Max_points-1 DO
BEGIN
splitting [current_point]:=FALSE ;
unavoidable [current_point]:=FALSE
END;
END;
PROCEDURE read_input;
VAR num : INTEGER;
BEGIN
read(input_file,num);
WHILE NOT (num = -1) DO
BEGIN
IF num = -2
THEN INC (number_of_points)
ELSE BEGIN
Arrows [number_of_arrows][0] := number_of_points-1;
Arrows [number_of_arrows][1] := num;
INC (number_of_arrows)
END;
read(input_file,num)
END;
END;
PROCEDURE write_output;
BEGIN
Write(output_file,number_unavoidable_points);
FOR current_point:=1 TO number_of_points-2 DO
IF unavoidable[current_point]
THEN write(output_file,' ',current_point);
Writeln(output_file);
Write (output_file,number_splitting_points);
FOR current_point:=1 TO number_of_points-2 DO
IF splitting[current_point]
THEN write(output_file,' ',current_point);
END;
PROCEDURE finalisation;
BEGIN
Close(input_file);
Close(output_file);
END;
PROCEDURE compute_results;
VAR reachable : Point_array;
PROCEDURE find_reachable (current_point:INTEGER);
VAR point:INTEGER;
ready:BOOLEAN;
BEGIN
FOR point:=1 TO number_of_points - 1 DO
reachable[point]:=FALSE;
reachable[0]:=TRUE;
ready:=FALSE;
WHILE NOT ready DO
BEGIN ready:=TRUE;
FOR current_arrow:=0 TO number_of_arrows-1 DO
IF reachable [Arrows[current_arrow,0]] AND
NOT reachable [Arrows[current_arrow,1]] AND
(Arrows[current_arrow,1]<>current_point)
THEN BEGIN reachable[Arrows[current_arrow,1]]:=TRUE;
ready:=FALSE
END;
END
END;
FUNCTION is_splitting:BOOLEAN;
VAR current_arrow:INTEGER;
OK:BOOLEAN;
BEGIN
current_arrow:=0;
OK:=TRUE;
WHILE (current_arrow