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.