A competitor in the Olympiad in Informatics has made his estimation about how long time (in seconds) he needs to solve each one of the given problems. His goal is to choose several problems, so that he could get the maximal number of points not exceeding the total allowed time to work, that could not be greater than 4 hours.

The first row of the **input** file `INPUT1.TXT` contains
a positive number for the total time to work. Each one of the next rows
contains two integers, separated by a single space. Their meanings are
the estimated time and the maximum of points given for the each subsequent
problem. The number of rows in the file cannot exceed 1996.

**Output** file `OUTPUT1.TXT` must contain an integer for
the greatest possible total score of points.

Given are no more than 50 rectangles. Is it possible to cover some square using the rectangles by rotating and shifting them? It is not allowed to overlape rectangles as well to remain gaps on the square. Every rectangle must participate in the covering and no part of any rectangle should go out of the square.

The **input** file `INPUT2.TXT` contains several sets of test
data. Each row of the file consists of two nonnegative integers meaning
the length and the width of the subsequent rectangle. Every data set ends
by a pair of zeros.

**Output** file `OUTPUT2.TXT` must contain one number in each
its row for every data set and its value must be equal to the length of
the side of the square, if the covering is possible, and zero, otherwise.

Find the smallest positive integer such that after dividing it by a number of a given set of integers (the set cannot consist of more than 45 elements), it gives the corresponding nonegative remainder.

Each row of the **input** file `INPUT3.TXT` contains a pair
of nonnegative integers, the subsequent divisor and remainder.

**Output file** `OUTPUT3.TXT `must contain the wanted smallest
positive integer.

Using a digitizing device, the coordinates of *N* points (3 <=
*N* <= 100) are taken down. These points can form a convex
polygon. Starting from the first point, the ploting device must draw the
mentioned convex polygon moving the drawing pen clockwise. Which order
of rendering must be applied to join up the points?

The **input** file `INPUT4.TXT` contains *N* rows.
The *i*-th row consists of two integers, separated by one space at
least. These integers are the coordinates of *i*-th point.

**Output file** `OUTPUT4.TXT` must have *N* rows,
each consisting of an integer meaning the subsequent number of the point
drawn by the ploting device.

Find the intersection of *N* convex polygons (1 <= *N*
<= 50).

The **input** file `INPUT5.TXT` consists of one or more
sets of data. Each row of the file contains a pair of nonnegative integers,
separated by one space at least. These integers are coordinates of polygon's
vertex. Every data set describes exactly one convex polygon with *M*
vertices (1 <= *M* <= 50). The end of any data set is marked
by pair -1 -1.

**Output file **`OUTPUT5.TXT` must contain the coordinates
of the vertices of the obtained intersection. The vertices must be placed
subsequently in the clockwise order, starting from that one having the
smallest first coordinate. If there are two or more such vertices, then
at first position must be placed that having the smallest second coordinate.
Each row of the output file must contain two floating point numbers, each
having exactly two digits after the decimal point. These two numbers must
be separated by one space exactly. If the intersection is empty then your
program must output -1 -1.

At a competition in Legoland the competitor must build a tower of high
*H* (1 <= *H* <= 2000) using *N* (1 <=
*N* <= *H*) legocubes, that he can put one of top of
the other. Which sizes of legocubes the competitor should choose so that
the total volume of the tower were minimal.

The **input** file `INPUT6.TXT` consists of two rows
with integers *N* and *H*, respectively.

**Output file** `OUTPUT6.TXT` must consist of *N*
rows, each containing an integer showing the size (length of the edge) of
the corresponding legocube.

Source: Matematika i informatika, journal published by Bulgarian Ministry of Education, n. 4, 1996, pp. 53-54.

© The text is translated from Bulgarian by Emil Kelevedzhiev.

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