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 n-program, if there is at least one assignment command at each step. An n-program is designed to be executed simultaneousely by the first n processors for l steps. We say that n-program P is equivalent to n-program 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 1-program containing k assignment commands;
Verify the correctness of the inputted commands;
Transform the inputted 1-program to an equivalent of it n-program with the minimal length (posiibly adding some appropriate empty commands) and display the obtained result;
Without lengthening the obtained n-program from the previous problem, transform it to an equivalent m-program with the minimal value of m and display the result.
An input 1-program:
A=B+C
A=A-E
B=C+D
D=D-E
E=A*B
D=A*D
A 3-program, that can be a possible solution for the problem 3.
A=B+C B=C+D D=D-E
A=A-E & &
E=A*B D=A*D &
A 2-program, that can be a possible solution for the problem 4.
A=B+C B=C+D
A=A-E D=D-E
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:
A2---------B2
| |
| |X1
| A1------------------------B1
| | | |X1
| | | A4---------------------------------B4
| | | |
| |
| D1------------------------C1 |
| |P |Q
|
| |S |R |
| A3------------------------------------B3 |
| | | X3| | |
| | | D4---------------------------------C4
| | | |
| D3------------------------------------C3
| |X4
| |
D2---------C2
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 non-intersecting 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. 30-32.
© The text is translated from Bulgarian by Emil
Kelevedzhiev (keleved@math.bas.bg)
Return to the Home
Page of Bulgarian Mathematics and Informatics Competitions.