A computer records the starting and finishing time of each application program in the measure of 1/100 seconds. A daily statistic is a set of pairs (a, b) of non negative integers such that 0<a<=b<8640000. The pair (a, b) means that a program started at time a and finished at time b. The time points a and b belong to busy time. Arbitrary number of programs can run in parallel. Write a program that computes a) the length (b-a+1) of the largest closed time interval [a, b] when the machine was idle and b) the length (d-c+1) of the largest closed time interval [c, d] when the machine executed at least one program. A time point t belongs to the idle time if there is no program running at time t.
The first line of text file DAY1A.DAT contains N, the number of the intervals (1<=N<=1000). Each of the rest N lines of the file contains two non negative integers, the starting and finishing time of a program.
The text file DAY1A.SOL has to contain the following two integers in this order:
a) The length (b-a+1) of the largest interval of time [a, b] when the machine was idle.
b) The length (d-c+1) of the largest closed time interval [c, d] when the machine executed at least one program.
Maximum number of points: 25.
Example input: 9 30000 35000 10000 20000 15000 16000 40000 44000 77000 220000 13000 41000 60000 67000 50000 55000 65000 70000 |
Example output: In our example input 8419999 143001 |
The students of a class have decided to form an alarm chain. Every student chooses a unique successor, to whom he directly delivers received messages. Whenever a student receives a message forwards it to his or her successor.
Such an assignment is called an alarm chain if the following holds. Suppose somebody sends a message to his or her successor, who in turns transmits the message to his or her successor, etc. The message eventually arrives to every student, including the starting student.
Clearly, not every assignment is alarm chain. Write a program which for an arbitrary input assignment, computes the minimal number of necessary modifications that transforms the input assignment to an alarm chain.
Output Data
Maximum number of points: 35.
Example input:
10 Anita>Peter Andrew>Julia David>Andrew Natalie>Gabriella Edith>David Peter>Anita Gabriella>Julius Adam>David Julia>Gabriella Julius>Julia | Example output:
The output for our 4 |
Two brothers, Alan and Bob want to share a set of gifts. Each of the gifts should be given to either Alan or Bob, and none of the gifts can be split. Each gift has a positive integer value. Let A and B denote the total value of gifts received by Alan and Bob, respectively. The aim is to minimise the absolute value of the difference A-B. Write a program which computes the values A and B.
Output Data
Maximum number of points: 40.
Example input:
7 28 7 11 8 9 7 27 | Example output:
The output for our 48 49 |
There are N trees in a garden. The shape of the garden is square with 1000 m long sides. We are looking for a rectangle with largest area that does not contain trees inside. The sides of the rectangle must be parallel to the corresponding sides of the garden. Each side of the rectangle may contain trees and may lie on a side of the garden. Trees are given by (x, y) co-ordinates of their positions measured in meter. A tree is considered to be a point without extension.
The origin of the co-ordinate system is the lower left corner of the garden and the axes are parallel to the sides.
Maximum number of points: 30.
Example input:
7 280 100 200 600 400 200 135 800 800 400 600 800 900 210 | Example output: The output for our example would be: 360000 |
The president of a company is organising a party for his employees. The company has a hierarchical structure; that is, the supervisor relation forms a tree rooted at the president. In order to make the party fun for all attendees, the president does not want both an employee and his or her supervisors to sit at the same table.
The problem is to compute the minimal number of tables necessary to make a seating arrangement that satisfies the above requirement. The input of the program is the immediate supervisor relation of the company. The supervisor relation is defined in terms of the immediate supervisor relation as follows. A person P is supervisor of a person Q if P is the immediate supervisor of Q, or there are persons P_{1}, ... ,P_{k} (1<k) such that P=P_{1}, Q=P_{k} and P_{i} is the immediate supervisor of P_{i+1} (i=1, ... ,k-1).
The number of attendees is N (1<=N<=200), and there are T (2<=T<=10) seats at each table.
Output Data
Maximum number of points: 30.
Example input:
4 13 0 1 9 9 9 2 2 1 1 7 8 8 10 | Example output: The output for our example would be: 5 |
We are given three glasses. The volume of each glass is 100 unit (cm^{3}). The first two glasses have marks, same on both glasses, each mark indicating the volume measured from the bottom up to the mark. That volume is written beside the mark.
Initially the first glass contains 100 unit volume of fluid, and the others are empty. Write a program that decides whether one unit volume of fluid can be separated in the third glass, and if so, computes the minimal number of steps needed to do it. In each step, after the operation at least one of the used glass must contain fluid up to a mark or empty. During the procedure we can keep track of the actual contents of each three glasses.
Output Data
Maximum number of points: 40.
Example input:
4 13 37 71 100 | Example output: The output for our example would be: YES 8 |