An important meeting of two countries was attended by *M* representatives
from the first country and by *N* representatives from the second
(*M* and *N* are no greater than 1000; representatives are numbered
by 1, 2, ... , *M* and by 1, 2, ... , *N*, respectively). Beforehand,
it was selected *K* pairs of negotiators. In each pair, one person
belongs to the first country, while the other person belongs to the second
country. Every representative from each country was assigned to one such
pair at least. The representatives were placed in different rooms in the
building, where the meeting was held. The technical personnel had got an
instruction to connect with direct telephone lines some pairs of room,
so that any representative should be able to use a direct telephone connection
to one, at least, representative that shares the same pairs for negotiation
with him/her. The cost of telephone connection between any two rooms is
a constant. The technical personnel should carry out their tasks with spending
minimum resources.

Write a program `CONF.EXE` that finds out
the minimum number of direct telephone lines according to the above requirements.

The** input **text file `CONF.INP` begins
with a line containing numbers *M*, *N* and *K*, separated
by a space. Every one from the next *K* lines contains one pair of
negotiators *P*1–*P*2, where *P*1 is a representative from
the first country and *P*2 is a representative from the second. The
two numbers, *P*1 and *P*2, are separated by a space.

The **output** should be written in a text file `CONF.OUT`.
This file should contain only one line with the number found by your program.

**An Example**:

`CONF.INP``
`

`3 2 4`
`1 1`
`2 1`
`3 1`
`3 2`

`CONF.OUT``
`

`3``
`

**Problem 2. Power.**

Given integers *N*, *M* and *Y* (0 < *N* <
999, 1 < *M* < 999, 0 < *Y* < 999), write a program
`POWER.EXE`, that finds out all the integers
*X* (*X* = 0, 1, ..., M -1), such that the division of
*M* by the *N*-th power of *X* gives a remainder equal to
*Y*, i.e. *X* ^*N* mod *M* = *Y*.

The **input** data are read from a text file `POWER.INP`.
The file contains integers *N*, *M* and *Y*, written in
one line and each two of them separated by a space.

The **output** should be written as a sequence of one or several
different integers each two of them separated by a space and placed in
an incresing order in an output text file `POWER.OUT`.
If such integers do not exist, your program should write in the file the
number `–1`.

**An Example:**

`POWER.INP``
`

`2 6 4``
`

`POWER.OUT``
`

`2 4`

Allowed program run time: 5 seconds.

**Problem 3. Squares**.

In the coordinate plane, *N* squares (0 <* N* < 100)
and a point *P* are given. A distance between a point *P* and
a square is defined as the smallest possible length of a straight line
segment connecting the point *P* and some point (contour or internal)
of the square. In the case, when the point* P* is internal for the
square, then the distance is assumed to be equal to 0. Some given squares
may overlap partially or completely each other. Also, some squares may
have coincidental vertices as well as having all its vertices being on
the same point. Write a program `SQUARE.EXE`,
that sets in an increasing order all the given squares according to their
distances from the point *P*.

The **input** data must be read from the text file `SQUARE.INP`.
The first line of the file contains the integer *N*. In every one
of the next *N* lines a set of 4 integers is given. They belong
to the interval (–9999, 9999). The first two of these integers are* x*-
and *y*-coordinates of some vertex of the subsequent given square.
The second two integers are *x*- and *y*-coordinates of the opposite
vertex of the same square. At the end, the file contains one more line,
in which the *x*- and *y*-coordinates of the point *P*
are given. Anywhere, every two adjacent integers, that are in one line,
are separated by a space.

The **output** data should present a sequence of numbers of all the
given squares in an order found by your program (Each square has received
its number consequently according to its appearence in the input file).
In the case, when two squares have the same distances to the point P, then
their numbers must be written in the output sequence according to their
actual increasing order. The name of the output text file should be `SQUARE.OUT`.
The numbers in it should be written in one line and any two of them, that
are adjancent, should be separated by a space.

**An Example:**

`SQUARE.INP``
`

`2`
`0 0 1 1`
`0 3 1 4`
`0 0``
`

`SQUARE.OUT`
` `
`1 2`

Allowed program run time: 5 seconds.

**Second Day.**

**Problem 1. Game.**

The following game is considered: Given are an even number of stiff paper cards. On each of them an integer is written. All the cards are placed in a line. The game is played by two players with alternating turns. At his turn, the player takes away one card that is standing in the endmost left or in the endmost right place in the line. The game is over when there is no card to be taken. At the end of the game, the winner is that player who has collected cards with a greater total sum of integers. The game is finish with neither side winning, when the sums of the two players are equal.

Your task is to write a program `GAME.EXE`,
that will play against a program, supplied by the jury. Your program begins
the first move of the game and your goal is to win. The game should be
fulfilled in the following way: At the beginning, your program should read
all the data from the input file and close it.After that, your program
should call several times jury's function `oppo`
in a way you have decided. The function `oppo`
has one input parameter, that should be assigned with a value 1 or 2 each
time your program calls this function. The value 1 of that parameter means
that you play a move, corresponding to taking a card from the endmost left-hand
side of the line, while the value 2 means that you play by taking a card
from the endmost right-hand side. The function `oppo`
returns a value equal to 1 or 2. This value shows how jury's program replies
to your move. The value 1 means that jury's program takes a card from the
endmost left-hand side, while the value 2 means that a card has been taken
by jury's program from the endmost right-hand side.

When your program calls the function `oppo`
for the last time, i.e. when the game is over, the function `oppo`
stops the run of your program.

The **input** data should be read from the text file `GAME.INP`.
This file has two lines. The first line contains an integer *N* (1
< *N* < 100), that is equal to the number of the given cards.
The second line contains *N* integers, ordered in the same way as
the cards are arranged from left to right. These integers are positives
in the range from 1 to 99. Any two of them, which are adjacent in the input
file, are separated by a space.

Your program should not write any output files.

Allowed run time for your program is 5 seconds.

*Remark for Turbo C/C++ programmers*: You have given two files:
`OPPO.H` and `OPPO.OBJ`.
Include the directive `#include “OPPO.H”` in
your program. Use a project file with included `GAME.CPP`
and `OPPO.OBJ`. Apply the following compiler
options: Model Small, Calling Convention C, C++ Compiler always.

*Remark for Turbo Pascal programmers:* You have given a file `U_OPPO.TPU`.
The function `oppo` has the following definition:
`function oppo(p:integer):integer;` You should
include in your program the statement: `uses u_oppo;`

*Remark for C/C++ programmers*: You have given two files: `OPPO.H`
and `OPPO.OBJ`. Include the directive
`#include “OPPO.H”` in your program. Compile
your program using the command line: `gpp <your source>
game.obj.`

*Renark for Free Pascal programmers: *You have given two files:
`U_OPPO.PPU` and `U_OPPO.O`.
The function `oppo` has the following definition:
`function oppo(p:integer):integer;` You should
include in your program the statement: `uses u_oppo;`

You can download jury's program files from here.

**Problem 2. Covering.**

Given *N* (0 < *N* < 100) segments on a straight line.
Each segment is defined by coordinates of its two endpoints *a_i*
and *b_i*, *i *= 1, ..., *N*. These coordinates are
integers within the range (-999, 999). Some segments might overlap partially
or entirely each other. Write a program `COVER.EXE`,
that finds out what is the minimal number of the given segments which should
be removed, so that any two of the remaining segments would not have any
inner common point, i.e. a point that belongs to both segments and that
is inner for one of the segments at least.

The** input **data should be read from the text file `COVER.INP`.
The first line of the file contains the integer *N*. It follows *N*
lines. Each one of them contains two integers, separated by a space. Every
such pair defines coordinates of both endpoints of the subsequent given
segment.

The **output** of your program should be written in a text file `COVER.OUT`.
In the first line of the file, an integer equal to the number of the remaining
segments should be written. It should follow so many lines in the output
file. In any one of them, the coordinates of the left-hand and the right-hand
endpoints of a subsequent remaining segment should be written. These coordinates
should be separated by a space. The coordinates of the left-hand endpoints
should be arranged according to their increasing order. In the case, when
the problem has more than one solution, your program should output only
one of them, no matter which.

**An Example**:

`COVER.INP``
`

`3`
`6 3`
`1 3`
`2 5``
`

`COVER.OUT``
`

`2`
`1 3`
`3 6`

Allowed program run time: 5 seconds.

**Problem 3. Jeep**.

A jeep in a desert region should reach a point located *N* km away.
The fuel consumption is 1 liter per km. The jeep has a fuel tank containing
*M* liters. There is an unlimited amount of fuel at the starting point.
Anywhere along the route to the final point there is an unlimited number
of unbounded empty fuel tanks. Anytime, the jeep can store some amount
of its fuel in any route fuel tank or can take fuel previousely stored
by it during its travel. Write a program `JEEP.EXE`,
that computes the minimum amount of fuel (measured in liters) necessary
to reach the final point.

The **input** data should be read from the text file `JEEP.INP`.
The file contains a line with two integers *N* and *M*, separated
by a space. The following restrictions applied: *N* < 32000, 0
< *N* < 5*M*, *M* < *N*.

The **output** of your program should be written as an integer (amount
of the fuel rounded to the nearest whole number above) in the text file
`JEEP.OUT`.

**An Example:**

`JEEP.INP``
`

`1000 500``
`

`JEEP.OUT``
`

`3838`

Allowed program run time: 5 seconds.`
`

Source is taken from the jury materials.

© The text is translated from Bulgarian by Emil
Kelevedzhiev (keleved@math.bas.bg)

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