13-th Bulgarian National Olympiad in Informatics

May 3 and 4, 1997

Problem 1. Executive body.

A company has N (1 <= N <= 100) members, denoted by 1, 2, ... , N. About some pairs (i, j) of members we know, that the member i is able to argue the member j into accepting of any decision concerning company policy. In this case we say that the member i dominates the member j. If i dominates j, this does not necessarily imply that j dominates i. But, if i dominates j and j dominates k, we assume that i dominates k.Write a program for choosing an executive body of the company, containing a minimal number of members, in such a way, that for any member m of the company there exists at least one member of the executive body, which dominates m.

Input data are read from a text file INP. At first position of the first row in this file an integer N is given. At first position in each next row a pair (i,j) is given as two integers, divided by a space. The file ends by a row containing 0 0.

Output must be written into a text file OUT and this file must contain one integer at the beginning of each row. At the first row, this integer must be equal to the minimal count of members in the executive body, whereas at the following rows, member's numbers must be consequently written in their ascending order.

An example:

Input Output
 1 5
 1 7
 2 3
 2 6
 3 5
 4 5
 5 6
 7 1
 7 4
 0 0

Problem 2. Module programs.

A programming language X is an interpreting type language. The programs, written in it, have module structure with no more than 256 modules in one program. Each module has a size of no more than 1K bytes and each row is no longer than 255 bytes. The source of each module is a text file entitled by the name of the module. This name is a character string, containing no more than 8 arbitrary letters or digits. During the execution time, the interpreter loads the sources in a buffer and begins the execution starting from a module, referred as main. Any called module is loaded in the buffer immediately after the calling module. The module removes itself from the buffer as soon as it terminates its execution. A call of a module is invoked by a command

CALL <name of a module>

This command is written in a single row in the source of a calling module. It is not allowed recursion calls, neither immediately (SUB1 calls SUB1), nor indirectly (SUB1 calls SUB2, SUB2 calls SUB3, ..., SUBn calls SUB1). Write a program for finding out the minimal length of the buffer, that is enough to ensure loading of all the modules, required for a correct execution of a given program.

Remark: When a row of program's source is being loaded into the buffer, one more invisible character, besides the visible ones, is being inserted.

The input text file INP contains the name of the main module.
The output must be written into a text file OUT and must contain only one number: the length of the buffer in bytes, found by your program.

An example. Assume the following files are located in the current directory, in which your program is running:

A(24)    B(14)    C(27)    D(17)    E(35)     F(13)

**       **       ****     ***      *******   *
CALL B   ***      CALL E   **       ******    **
***      CALL C   ***      CALL F   *******   **
CALL F            CALL D   **       ****      ****
**                ***               ****** 

The lengths in bytes of the files are written in brackets. Nonessential parts are signed by *'s. When calling your program with an input file INP containing a string "A", your output should be 100.

Problem 3. Sidewalk.

Along a sidewalk there was planted a line of N young trees (1 <= N <= 1000), numbered by 1, 2, ... , N. After a year the forestry officer find the height of each tree different from the height of any other. The officer decides to cut off some trees, so that the rest of them would satisfy the condition: starting from the tree with the smallest number, tree's heights should increase up to a tree numbered by i, and then decrease down to the end of the line. In some cases, it might not exist a tree on the left hand side or on the right hand side of the i-th tree. The forestry officer tends to preserve as many trees as possible. When there are more than one possibilities, each including an equal number of trees to be cut off, the officer will choose such of them, that ensures the remaining trees to have the greatest total sum of their heights. Write a program, that outputs an optimal plan for cutting off.

Input data are read from a text file INP. At the first position in the first row of the file it is written a positive integer N. In the beginning of each of the next N rows it is written the height of each tree in the same order as their order in the line.

Output must be written into a text file OUT and this file must contain only one row with two integers devided by a space; one integer for the number of remaining trees, another for the total sum of heights of these remaining trees.

An Example:

Input Output
5  69  

Problem 4. Groupoid.

A set of N elements (2 <= N <= 7) is called a groupoid if a binary operation * is defined which takes any two elements from the set as inputs and returns a single element belonging to the same set. We denote the elements of the groupoid by the first N small letters of the alphabet. In general case the operation * is neither associative, nor commutative. Write a program, that determines if it is possible to put brackets in a given expression of elements from the groupoid, so that the computed result would be equal to a (the first element in the groupoid).

For an example, if the operation * in a groupoid of 3 elements is defined by

* a b c
a b b a
b c b a
c a c c

then the expression b*b*a can be presented as (a*(b*a)) = a, but also ((b*b)*a) = c.

Input data. The number N of the elements is written at the first row of the input file INPUT4.TXT. The next N rows describe the binary operation by a table form. At the last row it is written an expression containing up to 100 characters without brackets.

Output OUTPUT4.TXT must contain a possible distribution of brackets.

An Example:


Problem 5. Strings.

A string may contain only 3 type of characters: A, B and C. Write a program, that finds a string containing N characters (3 <= N <= 97), so that the string does not contain any two identical adjacent substrings.

Input data: File INPUT5.TXT containing one integer N.

Output: File OUTPUT5.TXT must contain only one row with the output string.

An Example:


Problem 6. Ordering.

Given N objects (2 <= N <= 11), any two of them can be tied by one of the relations "=" or ">". How many different arrangements are possible? For example, if N = 2 then there exist 3 different arrangements: A=B, A>B, B>A.

Input data: File INPUT6.TXT containing one integer N.

Output: File OUTPUT6.TXT must contain one integer for the number of possible arrangements.

An Example:

3 13

Source: Matematika i informatika, journal published by Bulgarian Ministry of Education, n. 3-4, 1997, pp. 82-87.

© The text is translated from Bulgarian by Emil Kelevedzhiev.

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