In Nubia, the House of Parliament has a triangular form. On the first row there is one seat, on the second row there are two seats, on the third row there are three seats and so on, whereas on the last (N-th) row there are N seats. At the last elections in the country, K red and K blue Members of Parliament were elected, where K is the greatest integer not exceeding N(N+1)/6. The rest of the Members were orange. Since no two Members had been born in the same year, it was realized that the Members could be numbered according to their ages in an ascending order; the youngest have got number 1, whereas the eldest one have got the number N(N+1)/2.

In a text file `INPUT.TXT` on each row is written an integer
N (3 < N <= 1995). This file contains the input data for solving
the following problems:

Write a program, that for each inputted integer N from `INPUT.TXT` and
for each integer M (1 <= M <= N) finds a seat for every Member of
Parliament, so that on M-th row in the House there should be exactly M
Members belonging to the same color.

Your program must output subsequently into text files `OUT1-i.TXT`
the numbers of rows containing Members with only blue, red and orange colors,
where `i` is the positional number of each subsequent value of N
in the input file `INPUT.TXT`. In the first row of every output
file must be written intervals of numbers indicated from what through what
rows the corresponding seats in the House are occupied by only blue, red
or orange Members. The format of this first row is

BLUE:a-b/RED:c-d/ORANGE:e-f\

In the rest rows you can write no more than 50 numbers, separated by /.

**An Example:**

If the input file `INPUT.TXT` contains two values 4 and
7, your program must output two files with the following exemplary content:

`OUT1-1.TXT`

BLUE:2-2/RED:3-3/ORANGE:4-4\ 1/2 3 4 |

`OUT1-2.TXT`

BLUE:2-2/RED:3-3/ORANGE:4-5\ 2/7 4/5 1/3/ 6 |

Write a program, that outputs a file `OUT2-i.TXT` for each
i-th occurrence of N in the input file. Every output file must have the
following two rows:

a) First row must contain a list of Member's numbers *k* for which
the decimal value of *k*^3*k*^4 has every decimal digit exactly
for once. The notation *k*^3*k*^4 means that the digits of 3-rd
power of *k* are glued immediately before to the digits of 4-th power
of *k*.

b) Second row must contain a list of Member's numbers *k* for which
the 5-th power of the sum of the digits of *k* is equal to the square
of *k*.

Use the sign / as a delimiter within the lists.

Write a program, that outputs a file `OUT3-i.TXT` for each
i-th occurrence of N in the input file. Every output file must contain
the greatest possible number of pairs of Member's numbers (p,q), p<q,
so that for the set P of all such pairs, the following property holds: If
(p,q) belongs to P and q<r, this implies that (q,r) does not
belong to P, for any r.

Make a visualization on the computer screen of the obtained sets P using a matrix with L rows and L columns, where L = N(N+1)/2.

Text file `SET-EXPR.TXT` consists of rows, which total count
is not known until the file will have been read completely. Each row contains
a string. Allowed charactres are capital letters, small parenthesis "("
and ")", and signs "+", "*" and "\".
Every string is interpreted as an expression defining a set by using one-letter
names of some primitive sets and operations "+" for union, "*"
for intersection and "\" for set difference.

Text file `SET-VAL.TXT` contains all primitive sets. Each
row of this file consists of set's name, sign "=" and a list
of elements, separated by commas and embraced by "{" and "}".

**An example:**

`SET-EXPR.TXT`

(A+B)*F\B (F\D)*A+B D*A |

`SET-VAL.TXT`

B={VW,ALFA,BMW} A={VW,RENAULT} F={8,TP,VW} |

Write a program, that outputs into text file `SET-RES.TXT` the
values of the expressions taken from file `SET-EXPR.TXT` computed
by using the data from `SET-VAL.TXT`. In case there are expressions
which are not correctly given, your program should output into the correspondig
row the message ERROR IN EXPRESSION(*i*), where* i*
is positional number of the non-correct expression.

Remark: The file `SET-VAL.TXT` contains definitions of all
occured in the file `SET-EXPR.TXT` primitive sets in spite
of an expression is correct or not.

Write a program, that inputs the sets from the file `SET-RES.TXT` and
outputs them into text file `CHAINES.TXT` as several sequences,
in each sequence the sets being ordered in an ascending order by inclusion.
Your program must write every such sequence on a separate row in which
the numbers of the sets must be separated by the sign "<".

Write a program, that finds the greatest by count sequence of sets
taken from the file SET-RES.TXT, in which the sets are ordered in an ascending
order by inclusion. Your program must write this sequence into text file
`BIGCHAIN.TXT` with the numbers of the sets separated by the
sign "<".

Source: Matematika i informatika, journal published by Bulgarian Ministry of Education, n. 4, 1995, pp. 75-77.

© The text is translated from Bulgarian by Emil Kelevedzhiev.

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