A plain square domain is divided by a grid into *N* by *N* small
square pixels (*N* <= 200). Each pixel has coordinates *x*
and *y* in a rectangular system of coordinates with *x* and *y*
being integers in a range 0..*N*-1. Vertical, horizontal and diagonal
(at 45 and 135 degrees) lines can be drawn by coloring in black the underlying
pixels. Two lines, obtained in this way, cannot touch each other. A vertical,
horizontal or diagonal line is specified by a pair (*a*,*), (*,*b*)
or (*a*,*b*), respectively. In this notation, *a* is the
*x*-coordinate of the intersecting point of the line by the *x*-axis
and *b* is the *y*-coordinate of the intersecting point of the
line by the *y*-axis. Some intersecting points may be located outside
the given square domain. The line (0,0) coincides with the main diagonal
line of the square. Two lines touch each other if every pixel belonging
to one of them has at least one adjacent (upper, lower, left, right, or
diagonal) pixel belonging to the other line.

A part formed by pixels of the given square domain is called closed domain if it is surrounded entirely by lines. The area of this closed domain is the count of pixels located inside it.

Write a program `P1.EXE` that inputs the size `N` of the
square and the data for `M` lines, no any two of them touching each
other. The program should compute the area of the largest closed domain.

**Input data** are read from a text file `IN1.TXT`. The first
row of this file contains the numbers *N* and *M*, divided by
a space. The next *M* rows contain the specifications of the given
lines, each one on a separate row.

The **output** file `OUT1.TXT` must contain only a value of
the computed area.

**An Example:**

IN1.TXT |
OUT1.TXT |

40 4 8 * * 28 -4 4 42 42 |
85 |

Given the set {1, 2, ... , 500}, we denote a subset of its elements by a capital letter from the alphabet A, B, ..., Z. The content of a subset we denote by a comma separated list of elements, written between brackets "{" and "}". The union and intersection of the sets A and B are represented by A+B and respectively by A*B. The complement of a subset A is denoted by -A. Using these 3 operations "+", "*", "-", brackets "(" and ")" and subset's names, we can build expressions.

Two operators are introduced:

LET <subset's name>=<list of elements>

defines a subset's name for a subset containig elements written on the right hand side.

FIND <expression>

evaluates the subset defined by <expression> using the current contents of subset's names appeared in it and outputs the number of its elements.

Write a program `P2.EXE` that inputs and executes a sequence
of the above defined operators.

**Input data** are read from a text file `IN2.TXT`. This file
contains one operator in each row and ends by special statement STOP.

The **ouput** file `OUT2.TXT` must contain the computed numbers
of elements, each on a separate row, according to the every FIND operator
in the input data.

**An Example:**

IN2.TXT |
OUT2.TXT |

LET A={18,28,38,48,58,68,78,88,98} LET B={91,92,93,94,95,96,97,98,99} FIND (-A)*B LET C={11,22,33,44,55,66,77,88,99} FIND (A+B)+C STOP |
8 24 |

The Board of the Union of Great Thinkers (BUGT) includes *N* members
(*N* <= 21), which we denote by 1, 2, ... , *N*. In order
to ensure a better management, BUGT decides to constitute *M* working
committees (*M* <= *N*). Each committee has a chairman. Any
member of BUGT might be elected in any committee, but one person cannot
be a chairman of more than one committee.

Write a program, that inputs *N*, *M* and the members of each
committee. The program should assign a chairman to each committee. It is
supposed that one feasible assignment is possible at least.

**Input data** are read from a text file `IN3.TXT`. The first
row of this file contains the numbers *N* and *M*, divided by
a space. In each one of the next *M* rows, the members of the next
committee are written as integers separated by single spaces.

**The** **output** file `OUT3.TXT` must have *M* rows,
each containing one member's number of the proposed chairman in the same
order as the committees are listed in the input file.

**An Example:**

IN3.TXT |
OUT3.TXT |

5 5 1 2 3 4 1 3 1 3 4 1 2 3 4 2 3 5 |
1 3 4 2 5 |

Let us denote by {a_i} the sequence ot the prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... . The members of another sequence {b_i} are composed by the elements of {a_i} binding together every subsequent pair: 23, 57, 1113, 1719, 2329, 3137, ... . One more sequence {c_i} we define as a subsequence of {b_i}, which members are all the prime numbers belonging to {b_i}. We have c_1 = 23, c_2 = 3137, ... . Write a program, that for a given j (1 <= j <= 150) computes the value of c_j.

The **input** file `INPUT.TXT` contains one number j.

The **output** file `OUTPUT.TXT` must contain the value
of c_ j.

**An Example:**

INPUT.TXT |
OUTPUT.TXT |

5 | 167173 |

Let us consider a game. Given *n* chips (0 < *n* <=
70) and a constant number *m* (0 < *m* <= 20), two
players, A and B, make subsequently moves. The player A starts first. On
his move, each player thinks of some positive integer *k,* *k*
<= min(*m*,*n*), and this is the number of chips he take away.
It is not allowed to use twice the same number *k,* i.e. such number
that has been already used at some previous move, in spite of whom that
move was belonged to. The game ends, when none of the players can make
a move. The player, who has made the last move, is the winner.

The **input** file `INPUT.TXT` contains two numbers,
*n* and *m*, written at first row and separated by a space.

Write a program, that reports which player has a winning strategy and
writes into the output file `OUTPUT.TXT `the following data:

Row 1 contains who has a winning strategy.

The next rows must contain all the possible moves of A in increasing order, each followed either by the word "winning" or by one winning move replied by B.

**Example 1:**

INPUT.TXT |
OUTPUT.TXT |

3 2 | B wins 1 2 2 1 |

**Example 2:**

INPUT.TXT |
OUTPUT.TXT |

7 4 | A wins 1 winning 2 winning 3 4 4 3 |

A man loses his way in a maze. The maze is a rectangular array with
*m* by *n* cells. Each cell can be

-- a *wall*; crossing this cell is not allowed;

-- a *floor*; free crossing is possible;

-- a *gate*; crossing is not permitted until a proper key is turned
on (see the cell-key below). When this key is turned on, the gate becomes
open and the man can pass through it as this is a floor. The gate remains
open during the next 20 moves. After expiring the time (i.e. number of
moves), the key must be turned on in order to become the gate open again.
If the gate is being closed while the man is within it, he cannot pass.
If the man enter a cell-key with the corresponding gate being open, then
the closing counter for this gate is reset agian to 20.

-- a *cell-key*; it corresponds to a specific gate. When the man enter
a cell-key, the corresponding gate becomes open and remains in this state
for the next 20 moves. Each gate has only one key and vice-versa, i.e.
there are not two keys for any gate, neither a gate without a key nor a
key without a corresponding gate.

Write a program, that find the shortest path to escape from the maze.

**Input data** are read from a text file `INPUT.TXT`. The
first row of this file contains man's coordinates (*x*, *y*;
1 <= *x* <= *m*, 1 <= *y* <= *n*). The
cell (*x*,*y*) is a floor. The second row contains two numbers,
*m* and *n* (*m*, *n* <= 50), the width and the
length of the maze. Each of the next *n* rows contains a set of*
m* numbers. Every integer in them describes a cell of the maze:

-1 is a wall;

0 is a floor;

1 thru 20 are gates;

101 thru 120 are cell-keys; A number *j* (101 <= *j* <=
120) means that this key is intended for the gate numbered by *j*-100.

The **output** file `OUTPUT.TXT` must contain one integer,
which is equal to the length of the shortest path to escape from the maze
or 0 if an escape is not possible.

**An Example:**

INPUT.TXT |
OUTPUT.TXT |

2 28 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 7 0 0 0 -1 0 -1 -1 107 -1 -1 -1 -1 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 |
21 |

Source: Matematika i informatika, journal published by Bulgarian Ministry of Education, n. 3, 1998, pp. 53-57.

© The text is translated from Bulgarian by Emil Kelevedzhiev.

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