Let us consider a computing system, that has many identical processors. All the processors use a common memory for saving numerical values of the variables A, B, ..., Z. The system works in a stepwise manner. At each step, every processor executes either an empty command or an assignment command. An assignment command has the following description:
<variable> = <arithmetic expression>
where the arithmetic expression does not contain brackets and consists of up to 2 variables and arithmetic operations. After computing the result, every processor assigns it to the left hand side variable and all the processors go over to the next commands. It is not allowed for two or more processors to execute simultaneousely commands with the same variable at the left hand side.
Let us denote the empty command by &. Executing this command, the processor idles during the current step. An aggregate of n sequences, each containing l commands, is called nprogram, if there is at least one assignment command at each step. An nprogram is designed to be executed simultaneousely by the first n processors for l steps. We say that nprogram P is equivalent to nprogram Q, if and only if both the programs starting with the same initial values of the variables A, B, ..., Z will produce the same final values for these variables.
Write a program for solving the following problems:
Input a positive integer k, (k<25) and an 1program containing k assignment commands;
Verify the correctness of the inputted commands;
Transform the inputted 1program to an equivalent of it nprogram with the minimal length (posiibly adding some appropriate empty commands) and display the obtained result;
Without lengthening the obtained nprogram from the previous problem, transform it to an equivalent mprogram with the minimal value of m and display the result.
An input 1program:
A=B+C
A=AE
B=C+D
D=DE
E=A*B
D=A*D
A 3program, that can be a possible solution for the problem 3.
A=B+C B=C+D D=DE
A=AE & &
E=A*B D=A*D &
A 2program, that can be a possible solution for the problem 4.
A=B+C B=C+D
A=AE D=DE
E=A*B D=A*D
Given are N rectangles (N > 1), that satisfy the following
conditions:
a) Each of them has sides parallel to the coordinate axes.
Each rectangle is specified by two of its vertices, which are the end points
of one of its diagonals.
b) Each rectangle has common internal points to at least
one another rectangle. There are no common vertices, sides, or parts of
sides, belonging to two or more rectangles.
Write a program for solving the following problems:
By means of a sequence of points, specify a closed piecewise straight line, that embraces a figure containing the union of all the given rectangles.
An Example:
A2B2
 
 X1
 A1B1
   X1
   A4B4
   
 
 D1C1 
 P Q

 S R 
 A3B3 
   X3  
   D4C4
   
 D3C3
 X4
 
D2C2
The union of the rectangles A_i B_i C_i D_i (i = 1, 2, 3, 4) is the figure F = A_2 B_2 X_1 B_1 X_2 B_4 C_4 D_4 X_3 X_4 C_2 D_2.
The figure F contains only one hole: PQRS.
Find out whether the figure F contains holes, i.e. closed domains within its boundaries, that are not belonging to it.
Decompose the figure F into the minimal number of nonintersecting rectangles, every two of them having at most a common side, or parts of sides, so that the union of all these rectangles would be coincide with the figure F.
Compute the perimeter and the area of the figure F.
Solving problems 3 and 4, suppose the figure F has no holes.
Source: Obuchenieto po matematika i informatika, journal published by
Bulgarian Ministry of Education, n. 4, 1990, pp. 3032.
© The text is translated from Bulgarian by Emil
Kelevedzhiev (keleved@math.bas.bg)
Return to the Home
Page of Bulgarian Mathematics and Informatics Competitions.