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.