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 |

7 1 5 1 7 2 3 2 6 3 5 4 5 5 6 7 1 7 4 0 0 |
2 1 2 |

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.

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 |

9 12 15 8 13 7 18 11 14 10 |
5 69 |

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:**

INPUT4.TXT | OUTPUT4.TXT |

3 bba cba acc b*b*a |
(b*(b*a)) |

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:**

INPUT5.TXT |
OUTPUT5.TXT |

7 | ABACBAB |

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:**

INPUT6.TXT |
OUTPUT6.TXT |

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.