1996 Programming Contest

Results

Fourteen teams from various schools in Idaho participated in the first High School programming contest. There were a total of 40 students and the teams were from the following schools:

The first place team was from New Plymouth High School. They finished problem 1 correctly (and ahead of other teams).
The team members were Adam Alderson(sr.), Paul Alderson (jr.).

The second place team was from Borah High School. They finished problem 1 correctly (and ahead of rest of the teams).
The team members were Cornelius Krull (jr.), Bryce Butler-Dawson (jr.), Dave Davenport (jr.).

Additionally, five more teams were able to complete the program for problem one correctly.

The Problems

Here are the problems used in the competition.





Problem 1: Balanced Words

Assume that we divide letters A--Z into two groups: the first 13 letters (A--M) and the second 13 letters (N--Z). Now, we define a ``balanced word'' as one with no two consecutive letters from the same group. In other words, every letter from the first group must be surrounded on both sides by a letter from the second group (unless it is the first or the last letter of a word) and vice versa. For example, the words APT and TEA are not balanced, but the words TAP and ATE are.

The Input

Each input line contains a word. Assume that the word starts in column 1, will not exceed column 40, and contains only the lower-case and upper-case letters ( the lower and upper-case letter should be considered the same when checking for ``balanced word''). End of data is indicated by `\#' on a line by itself.

The Output

Print each word and a message indicating whether or not it is balanced.

Sample Input 

NOG
PARK
NERD
SAD
TIP
TOP
#
Sample Output 

NOG is not balanced
PARK is balanced
NERD is balanced
SAD is not balanced
TIP is balanced
TOP is not balanced

Problem 2: Clash of Rectangles

Given two rectangles (in the same plane), find the total area covered by the two rectangles. If the two rectangles overlap (i.e. intersect or have a portion in common), the common area should be counted once (and not twice) int the total. Assume that if the two rectangles have a common portion, the common portion is a rectangle as well.

The Input

The input is divided into sets. Each input set consists of two rectangles. Each input line contains the x and y coordinates for the four vertices of a rectangle, i.e., four (x y) pairs arranged as follows.

 x1 y1 x2 y1 x1 y2 x_2 y2
End of data is indicated by a -1 on a line by itself.

The Output

Print the total area for each input set.

Sample Input 

2  2  5  2  2  4  5  4
8  3 10  3  8  4 10  4
4  4  9  4  4  5  9  5
7  2 10  2  7  6 10  6
1  1  5  1  1  5  5  5
2  0  4  0  2  7  4  7
-1
Sample Output

Total Area = 8 Total Area = 15 Total Area = 22

Problem 3: Rare Order

A rare book collector recently discovered a book written in an unfamiliar language that used the same characters as the English language. The book contained a short index, but the ordering of the items in the index was different from what one would expect if the characters were ordered the same way as in the English alphabet. The collector tried to use the index to determine the ordering of the characters (i.e., the collating sequence) of the strange alphabet, then gave up with frustration at the tedium of the task. You are to write a program to complete the collector's work. In particular, your program will take a set of strings that has been sorted according to a particular collating sequence and determine what that sequence is.

The Input

The input consists of an ordered list of strings of upper-case letters, one string per line. Each string contains at most 20 characters. The end of the list is signaled by a line that is the single character `#'. Not all letters of the English alphabet may be used. However the list will imply a complete ordering among the letters that are used.

The Output

The output should consist of a single line containing the upper-case letters in the order that specifies the collating sequence used to produce the input data file. Sample Input 

XWY
ZX
ZXY
ZXW
YWWX
#
Sample Output 

XZYW