8-th Bulgarian National Olympiad in Informatics

May, 1992

Selection round

First day

The following definition is taken for Boolean expression:

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) (A)=A(2c) P+0=P(2d) P+!P=1(2e) P*!P=0.

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

Problem 1.

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

Problem 2.

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.

Problem 3.

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.

Problem 4.

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

Second day

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:

Problem 1.

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.

Problem 2.

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.

Problem 3.

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

Problem 4.

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.