Tasks of the 2nd Central European Olympiad in Informatics

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.

Input data

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.

Output Data

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.

9

30000 35000

10000 20000

15000 16000

40000 44000

77000 220000

13000 41000

60000 67000

50000 55000

65000 70000

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.

Input data

The first line of the text file DAY1B.DAT contains N, the number of the students (1<=N<256). Each of the following N lines contains two names (strings) separated by the character '>'. The second name terminated by end-of-line character. The names are at most 20 characters long. A line of the form A>B means that the successor of student A is B, i.e. A directly delivers messages to B.

Output Data

Write the minimal number of necessary modifications to the text file DAY1B.SOL as an integer.

Maximum number of points: 35.

10

Anita>Peter

Andrew>Julia

David>Andrew

Natalie>Gabriella

Edith>David

Peter>Anita

Gabriella>Julius

Adam>David

Julia>Gabriella

Julius>Julia

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.

Input data

The first line of the text file DAY1C.DAT contains N, the number of the gifts (1<=N<= 100). The rest of the input contains N positive integers, the values of the gifts. Each value is <=200.

Output Data

Write the two integers A and B to the text file DAY1C.SOL.

Maximum number of points: 40.

7

28 7 11 8 9 7 27

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.

Input data

The first line of text file DAY2A.DAT contains N, the number of the trees (1<=N<=600). In each of the next N lines you will find integer co-ordinates (x, y) (0<x<1000, 0<y<1000), the positions of the trees.

Output Data

Write the area of the largest rectangle as an integer value in the text file DAY2A.SOL.

Maximum number of points: 30.

7

280 100

200 600

400 200

135 800

800 400

600 800

900 210

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₁, ... ,P_k (1<k) such that P=P₁, 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.

Input data

The employees of the company are identified by the first N (1<=N<=200) natural numbers. The president of the company is identified by number 1, and has no supervisor. The first line of the text file DAY2B.DAT contains T, the number of seats per table (2<=T<=10). The second line contains the number N (1<=N<=200) of the attendees, each employee identified by numbers from 1 to N will attend the party. In the third line you find N numbers. The i-th number in the line is the immediate supervisor of the i-th person. The first number in the line is 0, indicating that the president has no supervisor.

Output Data

Write the minimal number of tables needed to seat all attendees in the specified way in the text file DAY2B.SOL.

Maximum number of points: 30.

4

13

0 1 9 9 9 2 2 1 1 7 8 8 10

5

We are given three glasses. The volume of each glass is 100 unit (cm³). 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.

Input data

The first line of the text file DAY2C.DAT contains N, the number of the marks on the first two glasses (1<=N<=20) . The rest of the file contains N integers in increasing order; that is the volumes corresponding to the marks on the glasses. For each volume mark V the inequalities (1<=V<=100) hold and the largest value is 100.

Output Data

Write the string "YES" into the first line of the text file DAY2C.SOL if one unit can be separated in the third glass and write "NO" otherwise. If the answer is yes for the first question then write the minimal number of steps in the second line.

Maximum number of points: 40.

4

13 37 71 100

YES

8