University of Scranton 1997 High School Programming Contest Problems

Problem 1: Lines in a Plane
Problem 2: Union and Intersection of Sets
Problem 3: Bakery Scheduling
Problem 4: Permutation Representation
Problem 5: Polynomial Multiplication
Problem 6: Word Find

In each problem description, given is a "sample program execution" showing a dialog between the user and a program that solves the problem correctly. In each such dialog, text that is underlined corresponds to input provided by the user. Text that is not underlined corresponds to output produced by the program.

 


Problem 1: Lines in a Plane

In euclidean geometry, two lines on a plane are related in exactly one of three ways: The two lines either

You are to develop a program that takes as input two lines (each described by a pair of points on the cartesian coordinate plane) and that reports which of the three possible relationships holds between the two lines. The user supplies as input the eight real numbers x1, y1, x2, y2, x3, y3, x4, and y4. The eight numbers represent two lines: the line through the points (x1, y1) and (x2, y2) and the line through the points (x3, y3) and (x4, y4).

After providing its output, the program should ask whether the user wishes to submit another instance of the problem. The user is to reply either "yes" or "no"; in response, the program should take the appropriate action.

Sample Program Execution:

Enter x1: 0.0
Enter y1: 0.0
Enter x2: 1.0
Enter y2: 3.0
Enter x3: -1.0
Enter y3: -1.0
Enter x4: 10.0
Enter y4: 2.0
The lines are intersecting.

Another instance? yes

Enter x1: 0.0
Enter y1: 0.0
Enter x2: 1.1
Enter y2: 1.1
Enter x3: 3.95
Enter y3: 3.95
Enter x4: 4.0
Enter y4: 4.0
The lines coincide.

Another instance? yes

Enter x1: 1.0
Enter y1: -1.5
Enter x2: 1.0
Enter y2: 10.01
Enter x3: -5.0
Enter y3: -5.0
Enter x4: -5.0
Enter y4: 4.77
The lines are parallel.

Another instance? no

 


Problem 2: Union and Intersection of Sets

In mathematics, a set is any collection of objects in which no object appears more than once. One could speak about the set of whole numbers, or the set of students in a class, or the set of molecules in a drop of water. A common way of describing a small set is to list its members, enclosing them within curly braces. For example, { a, e, i, o, u } is the set of vowels in our alphabet. The order in which the members are listed is irrelevant, so we also could express this set as { i, u, a, o, e }.

The intersection of two sets is defined to be the set consisting of all objects that appear in both sets. For example, the intersection of { 1, 2, 4, 5, 12 } and { 3, 4, 9, 12, 17, 22 } is { 4, 12 }.

The union of two sets is defined to be the set consisting of all objects that appear in either of the two sets. For example, the union of { Fred, Alice, Joe } and { Emily, Mary, Fred } is { Mary, Fred, Alice, Emily, Joe }.

You are to develop a program that asks the user to input two sets; the program then displays the two sets, followed by their intersection and their union. To input a set, the user enters the size of the set (i.e., the number of distinct members), followed by each member of the set, as in the example below. The user is not to enter the same member twice. The program should repeat until the user enters -1 as the size of the first set.

You may assume that no set given as input by the user contains more than twenty (20) members. You may also assume that no item entered by the user has length more than eight characters. In outputting a set, your program may list its members in any order. In place of curly braces, you may use parentheses. Commas between members are optional. Finally, be sure that your program handles the empty set (i.e., the set with no members) correctly.

Sample Program Execution:

Enter size of first set: 3
Enter item 1 of first set: Charles
Enter item 2 of first set: garage
Enter item 3 of first set: 55
Enter size of second set: 0
The first set is { Charles, garage, 55 }
The second set is { }
Their intersection is { }
Their union is { Charles, garage, 55 }

Enter size of first set: 3
Enter item 1 of first set: A
Enter item 2 of first set: BB
Enter item 3 of first set: CCC
Enter size of second set: 4
Enter item 1 of second set: A
Enter item 2 of second set: E
Enter item 3 of second set: BB
Enter item 4 of second set: RR
The first set is { A, BB, CCC }
The second set is { A, E, BB, RR }
Their intersection is { A, BB }
Their union is { A, BB, CCC, E, RR }

Enter size of first set: -1

 


Problem 3: Bakery Scheduling

A baker wishes to arise in the morning and enter into her computer the list of baking tasks that she must complete that day, how long each will take, and at what time of day each is "due" to be finished, so that the computer can produce an effective schedule of her day. You are to develop a scheduling program for the baker to use. It must produce a schedule according to a few simple rules:

The baker will input the number of baking tasks she has for the day, which you may assume is no more than eight. Then she will input, for each task, its "name" (a description of no longer than forty characters), its due time, and its duration (how long it will take). Times of day will be given in the standard format, <hours>:<minutes> (e.g., 8:00, 11:30). Durations will be given in units of hours, to the nearest half hour. You may assume that the baking tasks entered as input by the user are such that it is possible to complete all of them (in one day) in accord with the rules given above. The schedule produced as output by your program should list, for each baking task, its name together with its starting and ending times, in chronological order.

Sample Program Execution:

Enter number of orders: 4
Enter name of order 1: Jones wedding cake
Enter due time of order 1: 12:00
Enter duration of order 1: 2.0
Enter name of order 2: Fortucci Restaurant bread
Enter due time of order 2: 11:00
Enter duration of order 2: 1.0
Enter name of order 3: Cookie Monster cookies
Enter due time of order 3: 3:30
Enter duration of order 3: 2.5
Enter name of order 4: Smith family doughnuts
Enter due time of order 4: 4:00
Enter duration of order 4: 1.0

Work on Fortucci Restaurant bread from 8:00 to 9:00
Work on Jones wedding cake from 9:00 to 11:00
Work on Smith family doughnuts from 11:00 to 12:00
Work on Cookie Monster cookies from 1:00 to 3:30

 


Problem 4: Permutation Representation

A permutation is a sequence of n integers (a1, a2, a3, ..., an) in which each of the integers between 1 and n appears exactly once. (The number n can be any positive integer.) One can view a permutation as a function f such that, for each i between 1 and n, f(i) = ai. (That is, f maps each position into the value at that position.) For example, the function f corresponding to the permutation (3, 6, 5, 4, 1, 2) is such that f(1) = 3, f(2) = 6, f(3) = 5, ..., and f(6) = 2.

It turns out that every permutation is simply a collection of cycles. A cycle is a sequence of numbers such that if f is applied to any except the last of them, it yields the next one, and if f is applied to the last one, it yields the first. Thus, the permutation given above has as one of its cycles <1, 3, 5>, because f(1) = 3, f(3) = 5, and f(5) = 1. Its other two cycles are <2, 6> and <4>.

Develop a program that takes as input a permutation of length no more than 16 (in the manner illustrated below) and that outputs the cyclic representation of that permutation. The cyclic representation of a permutation is simply a list of the cycles of which it is composed. Your output should list each cycle, one per line, with its smallest element first. Cycles should be listed in increasing order with respect to their smallest elements.

The program should repeat until the user specifies that the next permutation to be processed has length zero.

Sample Program Execution:

Enter length of permutation: 8
Enter f(1): 7
Enter f(2): 8
Enter f(3): 5
Enter f(4): 3
Enter f(5): 4
Enter f(6): 6
Enter f(7): 2
Enter f(8): 1
Cyclic representation is:
<1 7 2 8>
<3 5 4>
<6>

Enter length of permutation: 0

 


Problem 5: Polynomial Multiplication

A polynomial is a sum of terms, where each term is a coefficient multiplied by the variable x raised to some nonnegative integer power. The largest such power is referred to as the degree of the polynomial. The product of the polynomials

a0 + a1x + a2x2 + ... + amxm   and   b0 + b1x + b2x2 + ... + bnxn
is the polynomial
c0 + c1x + c2x2 + ... + cm+nxm+n
where, for each k from 0 to m+n,
ck = a0bk + a1bk-1 + a2bk-2 + ... + akb0

For this to make sense you must assume that ak = 0 for k > m and that bk = 0 for k > n. Notice that the sum of the degrees of two polynomials equals the degree of their product.

Develop a program that, in the manner illustrated below, takes as input the coefficients of two polynomials, each of degree no more than ten, and outputs their product. All coefficients will be integers. Terms in the product having coefficients of zero should not be shown. As illustrated, use the circumflex character ("^") to indicate exponentiation.

Sample Program Execution:

Enter degree of first polynomial: 2
Enter coefficient of 0-power term: 5
Enter coefficient of 1-power term: 2
Enter coefficient of 2-power term: -1
Enter degree of second polynomial: 3
Enter coefficient of 0-power term: 0
Enter coefficient of 1-power term: 0
Enter coefficient of 2-power term: 1
Enter coefficient of 3-power term: -2

Product is 5 x^2 - 8 x^3 - 5 x^4 + 2 x^5

 


Problem 6: Word Find

In the newspaper, one often runs across a word-find puzzle, which is a grid of letters through which you search in order to find each word appearing in a given list. Each word in the list is "hidden" in the grid so that it extends either straight to the right, left, up, or down, or along any of the four diagonal directions. A word-find is illustrated below, with the word "computer" hidden in it, shown in boldface.

R T W W I L N B Z C
I E K K L M J E W Q
P Q T S R S F E Q Z
L K E U F I M C V C
X T I L P Q E R D S
Y M B F E M X S J H
H G E W B Q O S U S
M C V E U I C C P I

Develop a program that takes as input a grid, as illustrated below. You may assume that the grid will have no more than ten rows and no more than ten columns. Once the grid has been input by the user, the program should ask the user to enter a word. If the word occurs at least one time in the grid, the program should report the beginning and ending locations of one such occurrence. If the word fails to occur in the grid, the program should report that fact. The program should continue searching for words until the user enters the empty string.

In the sample execution below, the input grid is

H E L P
R I I F
E Q L D

Sample Program Execution:

Enter width of grid: 4
Enter height of grid: 3
Enter grid location 1, 1: H
Enter grid location 1, 2: E
Enter grid location 1, 3: L
Enter grid location 1, 4: P
Enter grid location 2, 1: R
Enter grid location 2, 2: I
Enter grid location 2, 3: I
Enter grid location 2, 4: F
Enter grid location 3, 1: E
Enter grid location 3, 2: Q
Enter grid location 3, 3: L
Enter grid location 3, 4: D

Enter word to search for: HELP
Word begins at location 1, 1 and ends at location 1, 4

Enter word to search for: DIE
Word begins at location 3, 4 and ends at location 1, 2

Enter word to search for: PINKY
Word does not occur in the grid

Enter word to search for: