STRING MATCHING							(EST)

You are given two collections of strings, collection A and collection B. Your task is to find out if there exists a non-empty string S that is expressible as a concatenation of members of collection A as well as a concatenation of members of collection B. If there is such string, you must find the shortest one. A member of collection may occur multiple times in a concatenation.

Input data

On the first line of file MATCH.IN is integer N (0 £ N £ 100), the number of strings in collection A. On the next N lines are the members of collection A, each on separate line. On the next line is integer M (0 £ M £ 100), the number of strings in collection B. On the next M lines are the members of collection B, each on separate line. All collection members consist of capital Latin letters and have length between 1 and 50 (inclusive).

Output data
Your program must write it’s output to file MATCH.OUT. If there is no string S, the program must write 0 (zero) on the first and only line of the file. Otherwise, the first line must contain the length of the shortest possible S. The next line must contain the representation of S as concatenation of strings from collection A. The strings must be output in the order of concatenation and separated by '+' (plus) signs. The next line must contain the representation of the string as concatenation of strings from collection B in the same format as for strings from collection A. If different shortest strings are possible, you must output representation for one of them. If different representations from one collection for shortest string are possible, you must output one of them.

Evaluation
Only absolutely correct answers are accepted - if the reported string is not the shortest possible, the program scores 0 for given test. A solution that fails all tests where string S exists will score 0 for the whole problem.

Example 1
Input data(file MATCH.IN)		Output data (file MATCH.OUT)
1					0
AB
2
A
BA

Example 2
Input data(file MATCH.IN)		Output data (file MATCH.OUT)
2					5
ABC					CB+ABC
CB					CBA+BC
2
CBA
BC

TEXT CONVERTING							(LIT)

One byte (8 bits) are used to represent one text symbol (character) in the computer. The code table predetermines the code of each symbol. 
Write a program to convert the given text from code table A to code table B. 

Input Data consist of three files: A.TBL, B.TBL, A.T. In the file A.TBL you will find code table A, in the file B.TBL – code table B. Both files have unique format. Each file consists of 128 lines, one line is assigned for one symbol. 8 bit code table has 256 symbols. However it is assumed that the codes of the first 128 symbols are coincident in all the code tables, therefore their coding is not given in the files.

Below is a fragment from the file where it is described a code table 1257 which  is used in Baltic countries (the whole file can be found in the current directory).

0x80        #UNDEFINED
0x81        #UNDEFINED
0x82 0x201A #LOW SINGLE COMMA QUOTATION MARK
...
0xC6 0x0118 #LATIN CAPITAL E OGONEK
0xC7 0x0112 #LATIN CAPITAL E MACRON
0xC8 0x010C #LATIN CAPITAL C HACEK
0xC9 0x00C9 #LATIN CAPITAL E ACUTE
0xCA 0x0179 #LATIN CAPITAL Z ACUTE
0xCB 0x0116 #LATIN CAPITAL E DOT ABOVE
...
0xFE 0x017E #LATIN SMALL Z HACEK
0xFF 0x02D9 #DOT ABOVE

Each line has the following structure:
positions 1-4. Hexadecimal code of the symbol. The first two symbols 0x indicate that the number is hexadecimal, the other two represent the number. 
positions 5. Space.
positions 6-11. Hexadecimal symbol code in Unicode. 
positions 12. Space.
from the 13’th position. Comment – symbol description in English.
The comments can be ignored. 
Every symbol can be identified by its code in Unicode. In all the tables the same symbol has the same Unicode code.
All hexadecimal letters (A, B, C, D, E, F) are written in uppercase.
The lines in the table are sorted increasingly by the 8 bit code. 
If some code is not used in some code table, a line is assigned for this code. In such case instead of Unicode spaces are left and in the comment it is written UNDEFINED, for example: 

0x81        #UNDEFINED

The text to be converted is given in the file A.T. The text is written in the code table A. The file A.T does not contain any symbol marked with #UNDEFINED in A.TBL. Text file A.T contains at least 1 and no more than 1000 lines. Each line contains no more than 80 symbols and may be empty. 

Output Data – the text from the file A.T converted to the code of code table B –should be written to the file B.T. 
Instead of non-existing symbols in code table B, write symbol '#' in the result file.
The structure of the output file B.T must be exactly the same as A.T structure (i.e. the number of lines and number of symbols in corresponding lines must be the same).

DELIVERY 									(FIN) 

There is a large amount of packets that need to be delivered, within a certain time limit if possible. There are two vehicles available for making the deliveries, a small van and a large lorry. 
Each packet is either small or large. A small packet can be delivered either with the van or with the lorry, but a big one requires the lorry. For each packet we know the amount of time it would take to deliver it; we call this the time requirement of the packet. One vehicle can deliver only one packet at a time. 
We are also given a deadline, which is the total amount of time within which we should deliver as many packets as possible. We do not care about what happens after the deadline 
Thus, from our point of view, the deliveries take place as follows. 
•	A certain amount of small packets will be delivered by the van, and the total time requirement of these packets must not exceed the deadline, and 
•	a certain amount of small and large packets will be delivered by the lorry, and the total time requirement of these packets must also not exceed the deadline. 
The task in this problem is to determine the largest total amount of packets that can be delivered in this manner. 

Input data 
The input will be in the file DELIVERY.IN. 
The first input line contains a single integer T (1 £ T £ 1000) - the deadline. 
The second input line contains a single integer N (1£ N£500) - the total number of small packets. 
The input lines 3 through N+2 each contain a single integer between 1 and 1000 (inclusive). These are the time requirements of the small packets. Time requirements are given in ascending order. 
The input line number N+3 contains a single integer M (1£M£500) - the total number of large packets. 
The input lines N+4 through N+M+3 each contain a single integer between 1 and 1000 (inclusive). These are the time requirements of the large packets. These time requirements are also given in ascending order. 

Output data 
The only line of the output file DELIVERY.OUT should contain a single integer - the largest number of packets that can be delivered within the deadline.

Example
Input data(file DELIVERY.IN)	Output data(file DELIVERY.OUT)
10					8
8
2
2
2
2
2
4
4
4
4
3
3
6
6
The deadline is 10 time units. There are 8 small packets: 5 with time requirement 2 and 3 with time requirement 4. There are 4 large packets, 2 with time requirement 3 and 2 with time requirement 6. 
The 8 packets can be delivered in 10 time units by delivering the small packets with time requirement 2 with the van, and using the lorry to deliver one small packet with time requirement 4 and 2 large packets with time requirement 3. 

LAZY COURSE SELECTION						(USA)

When students enroll in a university, they are usually confused by the complexity of the rules for earning a degree. A degree in Computer Science, for instance, has many requirements, and each requirement can be satisfied by many courses. To complicate things further, any single course may satisfy several of the requirements at once. These rules are presented to students when they enter, and the students are left to pick the courses which will earn them a degree.

Since most good programmers are lazy, an entering Computer Science student will want to take as few courses as possible. You should write a program to help a lazy Computer Science freshman select courses to earn a degree.

Courses are numbered by consecutive integers from 1 to C (total number of available courses). Given a description of which courses satisfy which requirements, your program should recommend a set of courses so that every requirement for the degree is fulfilled by at least one recommended course. If there is any requirement left unfulfilled, then the poor student does not get a degree, and the solution is considered invalid and scores zero points. If a solution is determined to be valid, then points are awarded based on the quality of the solution: the fewer courses the student must take, the more points the solution earns.

Note that you will almost certainly not be able to find the optimum answer for some of the test cases within the given run time limit. You should try to get as good a solution as you can in time, making sure your program outputs it and exits before time runs out.

Input data
The first line of the file LAZY.IN contains two space separated integers, C and R. C is the number of courses available to the student (1 £ C £ 200), and R is the number of requirements for a degree (1 £ R £ 100).
The rest of the file contains C lines, one for each course (the first is for course number 1, up through the last for course number C). Each line has R space separated integers (the first is for requirement 1, the last for requirement R).
The r'th integer on the files c+1'st line is 1 if course c fulfills requirement r, and 0 otherwise.

Output data
Output file LAZY.OUT should contain two lines. The first line should contain a single integer N - the recommended number of courses for the student to take. The second line should contain N integers separated by single space character indicating the N recommended course numbers. Course numbers may be in any order. 

Example
Input data(file LAZY.IN)  		Output data(file LAZY.OUT)
4 3					2
0 1 0				2 3
1 1 0
0 1 1
0 0 1

There are 4 available courses and 3 requirements: course 1 fulfills only requirement 2, course 2 fulfills requirements 1 and 2, course 3 fulfills requirements 2 and 3 and course 4 fulfills only requirement 3.
Only two courses (#2 and #3) are recommended.

EXPRESSIONS									(POL)

Let X be the smallest set defined as follows
•	an empty string belongs to X,
•	if A, B belong to X then both, (A) and AB, belong to X.

The elements of X are called correctly built parenthesis expressions.
The following strings are correctly built parenthesis expressions:
()(())()
(()(()))

The expressions below are not correctly built  parenthesis expressions:
(()))(()
())(()

Let E be a correctly built parenthesis expression. 
The length of E is the number of single parenthesis in E.
The depth D(E) of E is defined as follows:

      ì  0                if E is empty
D(E)= í  D(A)+1           if E = (A), and A is in X
      î  max(D(A),D(B))   if E = AB, and A, B are in X

What is the number of correctly built parenthesis expressions of length n and depth d, for given  positive integers n and d?

Task
Write a program which
•	reads two integers n and d from the text file PAR.IN;
•	computes the number of correctly built parenthesis expressions of length n and depth d;
•	writes the result into the text file PAR.OUT

Input data
The only line of the input file PAR.IN contains two integers n and d separated by a single space character, 2 £ n £ 38, 1 £ d £ 19.

Output data
The only line of the output file PAR.OUT should contain a single integer - the number of correctly built parenthesis expressions of length n and depth d.

Example
Input data (file PAR.IN)	Output data (file PAR.OUT)
6 2				3

There are exactly three correctly built parenthesis expressions of length 6 and depth 2:
(())()
()(())
(()())

NEW FUN										(LAT)

Programmers often are asked to rewrite old program and the new program version must keep its functionality. It is nice, if such program is well documented and source code is available. But not always life is so lucky.
You must rewrite earlier written function FUN about which is known the following: 
1) FUN's arguments are 4 positive integers a1,a2,a3 and a4,
2) FUN's value is one of its arguments values,
3) FUN realizes one function of the following kind:
IF ai op aj THEN FUN:=ak ELSE FUN:=am ;
where possible op values are < , £ , > , ³ , = , ¹   , and 1 £i,j,k,m£4.
If i=1, j=2, k=4, m=1, and op is '¹', then function
IF a1¹a2 THEN FUN:=a4 ELSE FUN:=a1;  			(¶)
is realized and we will obtain, for example, FUN(2,1,1,3) = 3, FUN(4,4,2,3) = 4.
It is known, that in practice the existing version is too slow and works properly only if its argument values doesn't exceed 5. You are asked to write a new function version which have to work properly for all positive integer values which doesn't exceed 32767. 
Old FUN version is written so, that this, exactly which function is realized depends on data file in the current catalog FUN.DAT - so it will not be enough if you will write version for one fixed FUN.DAT. New version must work properly for any valid FUN.DAT .
Your program will always work in the same environment as old FUN, so you, for example, may include in your program old FUN calls (of course, keeping in mind restrictions for argument values). You can asume that in the current catalog always will be valid file FUN.DAT and your new program never will be used without it.
You must write program which realizes the same function as old FUN (for any valid FUN.DAT) and for argument values given in input file counts function values and output them to output file.
Input data
In the first line of text file NEWFUN.IN number of argument sets N (1£N£1000) is given. In the each of the following N lines one argument set (four positive integer values separated by single space characters) is given. All argument values are less or equal to 32767. 
Output data
Text file NEWFUN.OUT must contain exactly N rows. In the i-th file row one positive integer - "new FUN" value for i-th argument set must be written.
Environment and example
On your diskettes files which realize old FUN (FUNIT.TPU, FUNIT.OBJ, FUNIT.H, FUN.DAT) are given. Given FUN.DAT corresponds to function described earlier in example (¶). In the files MAIN.PAS, MAIN.C and DEMO.PRJ old FUN version call examples are given.
Input data (File newFUN.in)	Output data(File newFUN.out)
5					3
2 1 1 3				4
4 4 2 3				32766
32767 1 1 32766		6
6 6 6 6				10
7 8 9 10

Remark: In the given example the last three sets will not be processed properly by old FUN version.

THE MOBILE									(SWE)

In figure 1 you can see a mobile in perfect balance. The mobile have five weights 1 kg, 2 kg ... 5  kg. The distance between two marks is 1 m. You can check the balance through this calculation 

  -3·3 + -1·5 + 2·(1+2+4)=0
  -2·1 + -1·2 + 1·4=0

When you get a mobile problem you will get the stucture of the mobile from a character string. The mobile in figure 1 is described in this way

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

You have to calculate the weights and give the answer as another character string. From figure 1 with the five weights the answer is

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

You will now write a program reading a description of a mobile from an input file, calculate the weights and writing the answer to an output file.

•	If there are n weights in the mobile you must use the weights from 1 kg to n kg exactly once
•	n 17
•	The input string will be given as a single line in the input file MOBILE.IN. All numbers are integers which values are between -50 and 50 (inclusive).
•	The output string will be given as a single line in the output file MOBILE.OUT, without extra spaces.
•	You can assume that for each given test data at least one solution exists. If more than one solution is possible, you must output one of them.

Here you will have two additional examples with input and output string.

Input data (file MOBILE.IN)
(-3(-1(-1(-1,1,2),3),2),3(-2,1,2),6(-2,3))

Output data (file MOBILE.OUT)
((((8,6,1),5),10),(9,4,7),(3,2))

Input data (file MOBILE.IN) 
(-8,-4(-5,-3,-1,1),-2(-1,1,3),2(-1(-3,-2,1(-2,1,3)),1,3),6)

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