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 2 8 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.