The following definition is taken for *Boolean expression*:

(1) `<BoolExpr> ::= <Term>|<BoolExpr>+<Term>
`

The conjunction, disjunction and negation operations are denoted by signs "+", "*" and "!", respectively. The following rules are supposed to be satisfied:

(2a) `A*(B+C)=A*B+A*C
`(2b)

In the above formulas, A, B and C are Boolean variables and P is any Boolean expression.

Input character string `Expr` and output a message dispaying,
whether this string is a Boolean expression according to the above definition
(1).

Use string `Expr` from the previous problem. If this string is
a Boollean expression, input by the keyboard all necessary values for its
variables, then compute it and output the result.

Execute on `Expr` a sequence of transformations, each based on
some of rules 2a, 2b, 2c, 2d or 2e, as many times as possible. At each
step, your program should display the obtained expression and the rule,
that has been applied to.

Reduce `Expr` to a disjunction of conjunctions. Each conjunction
must contain only variables or their negations.

Endless white flat strip of a conveyer transports dark flat machine
parts. The parts are of different shapes and sizes. The conveyer moves
in a stepwise manner. At each step, an optical device scans all the 10
adjacent positions crosswise of the conveyer strip. As a result, a 10 bit
binary vector is obtained representing an image of the strip with the mashine
parts. Each white point is encoded by 0, whereas each black one by 1. The
mashine parts are placed on the strip without touching each other. They
can occupy arbitrary locations, but two identical parts are appeared always
in the same orientation. A particular type of a mashine part differs from
another type by 3 parameters L, W and S:

L is a visible length of the part in the lengthwise direction,
L < 21;

W is a visible width of the part in the crosswise direction,
W < 11;

S is a visible area, S < 101.

Two machine parts are considered to be of the same type, if their parameters
L, W and S are respectively equal. A unit measure for length is the
scanning step. This unit is the same in both lengthwise and crosswise directions.
A unit measure for area is the area of one scanned possition.

**An example:**

-----------------0-xxxxxxxxxxxxxxxxxxxxx---------------- ---------xxx-----0-x--xxxx------------------------------ -------xxxxxx----0-xxxxxxx------xxxxxxxxxx--xxxxxxxxxx-- ---------x--xx---0-xxxxxxx------xxxxxxxxxx-----------x-- ---------xxxxx---0---------------------xxxxx---------x-- -----------------0------xxxxxxxxxx------xxxxx--------x-- -----------------0------xxxxxxxxxx-------xxxxx-------x-- -----------------0------xx-----xxx--------xxxxx------x-- -----------------0------xxxx--xxxx---------xxxxx-----x-- -----------------0------xxxxxxxxxx-------------------x-- scanning <- direction of movement line

Write a program, that solves the following problems:

Simulate actions of the optical scanning device at each step of the
conveyer movement. Use `TEST.TXT` as an input file. This file contains
10 character rows with "-" and "x" signs, like those
given at the above example. Display on the computer screen each newly inputted
row.

At each step of the conveyer movement, update the current values of the parameters L, W and S for each mashine part passing under the scanning line and ouput these values on the computer screen.

At each step of the conveyer movement, output the count of parts by types distinguished up to the current step.

Determine how many parts passed under the scanning line have internal cuts.

Source: Obuchenieto po matematika i informatika, journal published by
Bulgarian Ministry of Education, n. 4, 1992, pp. 63-65.

© The text is translated from Bulgarian by Emil
Kelevedzhiev (keleved@math.bas.bg)

Return to the Home
Page of Bulgarian Mathematics and Informatics Competitions.