With a rectangular coordinate system *Oxy* in the plane, a list
of *N* rectangles is given. Their sides are parallel to the coordinate
axes. Some rectangles may overlap each other, but any two of them cannot
have a common vertex and any two of their sides cannot have a common part
that is a line segment Two sides from different rectangles may intersect
themselves at one point at most, and this point cannot be a vertex. A point
is called contour point for a given rectangle if this point belongs to
rectangle's side or coincides with rectangle's vertex. A contour of a given
rectangle is the set of all of its contour points. The configuration of
all the given rectangles has the following property: starting from an arbitrary
contour point of any rectangle, it is possible to arrive at any other contour
point of any other rectangle by moving along contours.

Write programme CONTOUR.EXE for travelling over all the contour points so that the sum of the passed distances is minimal.

The **input data** are read from text file CONTOUR.INP. In the first
row of this file, the number *N* (0<*N*<20) of the
rectangles is written. Each one of the next *N* rows contains 4 integers.
The first two of them are x- and y- coordinates of some vertex of the subsequent
rectangle, while the next two integers in the same row are x- and y- coordinates
of the corresponding opposite vertex.

The **output** must be saved as text file CONTOUR.OUT. In the first
row of this file, an integer *M* must be written, indicating
the number of segments in the found itinerary. After the first row, *M*+1
rows must come next, each of them containing a pair of x- and y- coordinates
of the consecutive vertex of the piecewise straight line by which all the
contour points are traversed.

All the numbers meaning coordinates in the input and output files are written as fixed point numbers with no more than 3 decimal digits before and after the decimal point. Numbers written on a shared row are separated by a single space.

Input:

`2
0. 3. 3. 0.
2. 4. 4. -1.`

Output:

`10
0. 0.
0. 3.
2. 3.
2. -1.
4. -1.
4. 4.
2. 4.
2. 3.
3. 3.
3. 0.
0. 0.`

A finite sequence of positive integers is given. Some of these integers may be equal to others in the sequence. Write programme EQUAL.EXE that distributes the given integers into subsequences so that the number of these subsequences should be the largest possible one, all the subsequences should have the same number of elements and the sum of the elements in each subsequence should be equal to the sum of elements of any other subsequence. Each integer from the initially given sequence should stand in exactly one of the obtained subsequences.

The **input data** are read from text file EQUAL.INP. In the first
row of this file, the number *N* (0<*N*<100) of the
integers in the given sequence is written. Each one of the next *N*
rows contains a consecutive element of the sequence. Each one of these
integers is positive and less than 999.

The **output** must be saved as text file EQUAL.OUT. In the first
row of this file, an integer *M* must be written, indicating
the number of the found subsequences. In each one of the next *M*
rows, the elements of a next subsequence must be placed; all the elements
of one subsequence in one row, separating any two neighbouring elements
by a single space.

Example 1:
EQUAL.INP 4 |
Example 1:
EQUAL.INP 4 |

EQUAL.OUT
2 |
EQUAL.OUT
4 |

A town has *M* streets (*M*<2000) and *N* crossing
points denoted by 1, 2,..., *N *(*N *< 1000). Each street
connects two crossing points. Each crossing point has an altitude above
sea level expressed by an integer in the interval [100, 200]. The length
of each street is given by an integer in the interval [10, 1000]. At one
time, a heavy rain fell over all the streets. The quantity of water
fallen onto a street was equal to street's length. If an endpoint of a
street is lower situated than the other endpoint, then all the water run
into the lower endpoint. If the two endpoints have the same altitude, then
the water run into both of them in an equal manner. If there exists a crossing
point such that several streets go away from it connecting other crossing
points with a lower altitude, then all the water run into these crossing
points in an equal manner. If there exists a crossing point such that all
the streets, that go away from it, have their other endpoints with altitudes
that are higher or equal to the altitude of the first crossing point, then
all the water disappears (runs into the sewerage system).

Write programme FLOW.EXE that finds out all the crossing points, where the water disappears, and output the quantity of disappeared water for every crossing point of that kind.

The **input data** are read from text file FLOW.INP. In the first
row of this file, the numbers *N* and *M* are given, separated
by a single space. Each one of the next *N* rows contains the altitude
of the subsequent crossing point, all of them being ordered by their numbers.
Each one of the last *M* rows describes a street and contains 3 values: the
numbers of both the endpoints and street's length. These values are separated
by a single space.

The **output** must be saved as text file FLOW.OUT and this file
must contains as many rows as the crossing points are. Each one of these
rows must contains two values: crossing point's number and the quantity
of disappeared water (approximated to the 4-th decimal digit after the
decimal point). The rows must be arranged in an increasing order according
crossing point's numbers.

FLOW.INP

`5 7
130
110
150
110
180
1 2 50
1 3 50
2 3 70
2 4 30
2 5 60
3 5 40
4 5 20`

FLOW.OUT

`2 285.0000
4 35.0000`

With a rectangular coordinate system *Oxy* in the plane, a point
*A* and a set of several non-zero vectors are given. The point *A*
is different from the beginning of the coordinate system.

Write programme SUM.EXE that finds out a sum containing some of the
given vectors so that if the beginning of the obtained vector-sum is placed
onto the beginning of the coordinate system, the endpoint of the sum will
coincide with the point *A*. It is not obligatory that all the given
vectors will participate in the sum. Moreover, any given vector may participate
not only once, but up to 5 times.

The **input data** are read from text file SUM.INP. In the first
row of this file, two numbers *x* and *y* are given, meaning
the x- and y- coordinates of the point *A*. The next row contains
number *N* (0 < *N *< 15) of the given vectors. Each
one of the next *N* rows contains 2 values: x- and y- coordinates
of the subsequent vector.

The **output** must be saved as text file SUM.OUT. In the first row
of this file, it must be written number *M *that is equal to the count
of the used vectors or 0, when the problem has no solution. If *M *>
0, the file must contain *M* more rows. Each one of them must contain
3 values: x- and y- coordinates of the consecutive used vector and a multiple,
that shows how many times this vector participates in the sum.

All the numbers meaning coordinates in the input and output files are written as fixed point numbers with no more than 3 decimal digits before and after the decimal point. Numbers written on a shared row are separated by a single space.

SUM.INP

`5. 5.
2
-1. -1.
1. 1.`

SUM.OUT

`1
1. 1. 5`

A transportation company maintains a bus line between two towns with several intermediate stops. The costs of tickets for travelling between any two of these stops are announced. A passenger must travel from the beginning to the end of the bus line. If the passenger wills, he may not buy a ticket for the whole travel at once. Instead, he can buy tickets for travelling between pairs of stops, chosen by him. At any time during his travel, he must have a valid ticket for the current part of the line between the stops. The passenger is not allowed to have more than one ticket at the same time. Moreover, he cannot go back between any two stops.

Write program TICKETS.EXE that finds how the tickets should be bought, so that the whole travel would be the cheapest one.

The **input data** are read from text file TICKETS.INP. In the first
row of this file, the number *N* (1 < *N* < 50) of
stops is written. It includes the initial and final stops. It follows *N*(*N*`-`1)/2
rows in the file. Each one of them contains 3 values, separated by a single
space: two stop's numbers and ticket's cost for travelling between them.
All the possible costs between any two stops are written in these rows.
The stops are numbered by 1 through N. The initial stop has number 1, while
the last one has number *N*. The ticket's cost is a fixed point number,
with no more than 3 decimal digits before the decimal point and with exactly
2 digits after the decimal point.

The **output** must be saved as text file TICKETS.OUT. In the first
row of this file, the number *M* of the bought tickets must be written.
Each one of the next *M* rows must contain two values: a pair of stop's
numbers for which a ticket is bought.

TICKETS.INP

`4
1 2 3.00
1 3 9.00
1 4 9.00
2 3 7.00
2 4 16.00
3 4 10.00`

TICKETS.OUT

`2
1 3
3 4`

In a town, all the houses are divided into two regions. At town's governing body, a question was posed, if it is possible to build a straight street separating both regions. This street should not pass across the houses.

Write program STREET.EXE that solves the posed problem.

The **input data** are read from text file STREET.INP. From the beginning
of the file, the coordinates of the houses belonging to the first region
are written; each house in a separate row. After that, a row containing
0 0 folows. Starting from the next row of the file and going to the end,
the coordinates of the houses belonging to the second region are written;
again, each house in a separate row. Every coordinate value is an integer,
no greater than 5000. The number of houses in any of both regions is no
greater than 10000.

The **output** must be saved as text file STREET.OUT. It must contain
a single row with 4 values, x1, y1, x2, y2, where either x1, y1, and x2,
y2 are coordinates of any two different street's points (fixed point numbers
with no more than 2 decimal digits after the decimal point), or each one
of these four numbers must be 0 in case the street cannot be built.

STREET.INP

`10 10
10 15
30 12
23 13
0 0
34 14
18 28
29 20
37 22
38 26`

STREET.OUT

`35.0 10.0 18.0 25
`

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.