Let us consider a set C_N of character strings with length of
N characters each (N <= 20), satisfying the following
properties:
a) every string contains no more than two different characters: A
and B.
b) every string does not contain two adjacent characters A.
Example: If N=4, strings were ABBA, BABA, BBBB, but AABA,
ABAA and AAAB are not belonging to C_4, because of not satisfying
the condition b).
Write a program, that solves the following problems:
Problem 1. For any integer N compute the number of elements
of set C_N without generating the elements themselves.
Example. If N=20, the number of elements of C_N is
17711.
Problem 2. Output some arbitrary K different elements of C_N. The integer K should be entered by the keyboard.
Problem 3. Output the strings of C_N (1 <= N <=
10) which are symmetric relatively to its centre.
Example. For N=4: ABBA, BBBB; For N=5: ABBBA, BABAB, ABABA, BBABB.
Let us consider a set P containing points with integer coordinates (x,y) for which 0 < x < a, 0 < y < b, for some integers a and b. Write a program, that solves the following problems:
Problem 1. Input the data from text file PTS.TXT containing the coordinates of the points of P. The file has the following structure:
| row 1: | a b |
| row 2: | x_1 x_2 |
| ... | ... |
| Last (k+1)-th row | x_k y_k |
The number of points is not known before reading the data from the file.
Your program should render on the computer screen the points of P.
Problem 2. Every point of P should be colored in blue or red, so that the difference of numbers of blue and red points located on any straight line, which is parallel to one of the coordinate lines, should not be greater then 1. Your program should render on the computer screen no more than two coloring of points of P.
Problem 3. Construct a rectangle, which satisfies simultaneousely
the following two conditions:
a) Its vertices have integer coordinates and its sides are parallel
to the coordinate lines;
b) The number of points of P, which are within the rectangle
are equal to the number of points, which are outside the rectangle.
Remark: The points located on the sides of the rectangle are neither inner,
nor outer to the rectangle.
Source: Matematika i informatika, journal published by Bulgarian Ministry of Education, n. 3, 1994, pp. 68-69.
© The text is translated from Bulgarian by Emil Kelevedzhiev.
Return to the Home Page of Bulgarian Mathematics and Informatics Competitions.