15-th Bulgarian National Olympiad in Informatics

May 15 and 16, 1999


Final round

Problem 1. The Maximal Square

A square table with N by N cells (3 <= N <= 60) contains integers. Each of them belongs to the interval [-9, 9]. Any square part of the table, that consists of K subsequent rows and K subsequent columns (1 <= K <= N), is called a square. The total sum of all the integers located in the cells of a square, is called a sum of the square.

Write a program SQR.EXE that finds out the maximal sum of a square within a given table.

The input data are read from text file SQR.INP. In the first row of this file, there is written the size N of the table. Each one of the next N rows contains N integers representing the corresponding row of the table. The integers are separated by a space.

The output must be written into a text file SQR.OUT with a single row containing the obtained maximal sum.

An example:

Input:

4
2 -8 4 -6
7 1 -5 3
-9 7 6 5
8 3 2 -4

Output:

20


Problem 2. Servicing stations

A company offers personal computers for sale in N towns (3 <= N <= 35). The towns are denoted by 1, 2, ..., N. There are direct routes connecting M pairs from among these towns. The company decides to build servicing stations in several towns, so that for any town X, there would be a station located either in X or in some immediately neighbouring town of X.

Write a program BAS.EXE for finding out the minumum number of stations, which the company has to build, so that the above condition holds.

The input data are read from text file BAS.INP. In the first row of this file, there are written number N of towns and number M of pairs of towns directly connected each other. The integers N and M are separated by a space. Every one of the next M rows contains a pair of connected towns, one pair per row. The pair consists of two integers for town's numbers, separated by a space.

The output must be written into a text file BAS.OUT with a single row containing the obtained minimum.

An example:

Input:

8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8

Output:

2


Problem 3. Point of view

In the plane, there are given N straight line segments (1 <= N <= 1000). Their endpoints have nonnegative integer coordinates not exceeding 20000. The line of each segment and the coordinate axes form together a right isosceles triangle. No any two segments have a common point.

We say, that a segment is visible from the origin O of the coordinate system, if there exists a point X on the segment, so that line segment OX does not intersect any other given segment.

Write a program GLE.EXE, that on given set of line segments, finds out the number of these segments, which are visible from the origin O.

The input data are read from text file GLE.INP. The first row contains number N of the segments. Any one of the next N rows contains four positive integers, X1, Y1, X2 and Y2, separated by a space. The first pair represents coordinates of one endpoint, whereas the second pair represents coordinates of another endpoint of the corresponding segment.

The output must be written into a text file GLE.OUT with a single row containing the obtained result.

An example:

Input:

4
3 13 11 5
14 1 10 5
10 14 20 4
5 6 10 1

Output:

3


Problem 4. Fruits

Visiting the fruit market, an eminent professor in mathematics always buys pieces of fruit in such a way, that they form a package exactly weighing a kilogram. His student decides to behave in the same way. The professor can perform all the necessary computations in his mind, but the student needs a portable computer.

The student can weigh in grams every piece of fruit he found on display and then enter the obtained values into a computer program. Help the student writing this computer program for finding out whether a package of exactly one kilogram could be formed. If it is possible, the program should output how to combine pieces in order to prepare the package.

Input data are read from text file FRUITS.IN. The first row of this file contains number N of pieces (1 <=N <= 50). At each one of the next N rows, an integer (between 1 and 1000) is given for the weight of the corresponding piece of fruit.

An example input:

5
200
300
200
400
500

Output must be written into a text file FRUITS.OUT. This file should contain the world NO, if it is not possible to satisfy the requirements, or weights of a found combination, each row containing a number from among the input, which total sum is equal to 1000.

An example output:

500
200
300


Problem 5. Star

A board contains 48 triangular cells. In each cell, there is written a digit (in a range from 0 through 9). Every cell belongs to two or three lines. These lines are marked by letters from A through L.

An example is depicted on the Figure. There, the cell containing digit 9, belongs to lines D, G and I. The cell containing digit 7, belongs to lines B and I.

For each line, A, B, C, ..., L, we consider the largest digit lying on it. In the above example, the largest digit for line A is 5, for line B is 7, for line E is 6, for line H is 0, for line J is 8 and so on.

Write a program, that inputs the largest digit for any one of the depicted 12 lines. The program should find out the smallest and the largest possible sum of digits located in all the cells of the board.

Input

The first row of text file STAR.IN contains 12 digits, each two of them separated by a space. The first of these digits means the largest one in line A, the second means the largest one in line B, and so on, the last digit means the largest one in line L.

Example

5 7 8 9 6 1 9 0 9 8 4 6

Output

Your program must write into the output file STAR.OUT the values of the smallest and of the largest possible sum of digits located in the cells of the board. These two values should be separated by one space exactly. If there does not exists a solution, your program must outputs the words NO SOLUTION instead of the above two values.

Example

40 172


Problem 6. Scales

On the figure, there is depicted a complicated device for weighing. The device stands in a state of equilibrium. This means, that a balance exists for any arm of the device. In the example, there are 5 weights, respectively by 1, 2, 3, 4, and 5 kilograms. The distance between any two adjacent marked points is 1 meter.

We can check the balance through the following computations:

-3*3 + (-1)*5 + 2*(1+2+4) = 0   (upper arm)
-2*1 + (-1)*2 + 1*4 = 0   (lower arm)

The structure of the device is given by a string. For the device on the Figure, the string is the following:

(-3,-1,2(-2,-1,1))

Find out which weights should be hanged, so that the device will stand in a state of balance. Write the answer as a string. For example, a solution for the above given example is

(3,5,(1,2,4))

Write a program, that inputs the structure of a device using the input text file, then computes the weights and outputs the result into a file.

If there are places for N weights, you should use weights from 1 through N kilograms, each weight exactly once. Suppose N <= 17 and assume that there are no more than 7 weights in each arm. If there exists more than one solution, you should output one of them.

Input

In a single row of input file MOBILE.IN, there is given a string representing the structure of the device. All numbers are integers in a range from -50 through 50.

Output

Write without spaces into output file MOBILE.OUT the string found by your program.

Examples:

MOBILE.IN
(-3(-1(-1(-1,1,2),3),2),3(-2,1,2),6(-2,3))
MOBILE.OUT
((((8,6,1),5),10),(9,4,7),(3,2))

MOBILE.IN
(-8,-4(-5,-3,-1,1),-2(-1,1,3),2(-1(-3,-2,1(-2,1,3)),1,3),6)
MOBILE.OUT
(10,(1,2,4,15),(14,5,3),((6,8,(16,11,7)),9,13),12)


Source is taken from the site iNFORMATIkA:
(http://www2.math.bas.bg/inf/resource/sources/olymp/99round4/tasks.zip)
© The text is translated from Bulgarian by Emil Kelevedzhiev (keleved@math.bas.bg)
Return to the Home Page of Bulgarian Mathematics and Informatics Competitions.