# 11-th Bulgarian National Olympiad in Informatics

## May 6 and 7, 1995

### First day

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:

### Problem 1.

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

### Problem 2.

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^3k^4 has every decimal digit exactly for once. The notation k^3k^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.

### Problem 3.

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.

### Second day

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}

### Problem 1.

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.

### Problem 2.

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 "<".

### Problem 3.

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.