University of Scranton 1991 High School Programming Contest Problems

Problem 1: Fibonacci Roots
Problem 2: Determine the Mode
Problem 3: Subset Determination
Problem 4: Tiling
Problem 5: Hexadecimal Addition Warning: Under Construction
Problem 6: Speeders Beware

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: Fibonacci Roots

The first two terms in the Fibonacci sequence are 0 and 1, respectively, and each subsequent term is the sum of the previous two. Using this definition to calculate the first several terms in the sequence, we get

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Let us define the Fibonacci roots of a positive integer n to be the two smallest consecutive Fibonacci numbers whose sum is greater than or equal to n.

Develop a program that, given as input a positive integer, produces as output its Fibonacci roots. The program should repeat until the user enters zero as input.

Sample Program Execution:

Enter input: 31
Fibonacci roots: 13 21

Enter input: 89
Fibonacci roots: 34 55

Enter input: 0

 


Problem 2: Determine the Mode

In statistics, the mode of a collection of values is defined to be any value that occurs with highest frequency in the collection. The mode need not be unique, as there may be two or more values that occur with the same highest frequency.

Develop a program that, given as input a collection of integers, lists any that qualify as a mode of the collection. The program should repeat until the user indicates that the collection of numbers to be analyzed is empty.

Sample Program Execution:

Enter number of items in the collection: 16
Enter item 1: 12
Enter item 2: -34
Enter item 3: 12
Enter item 4: 9868
Enter item 5: 89
Enter item 6: 23
Enter item 7: 28973
Enter item 8: 88
Enter item 9: -7
Enter item 10: 12
Enter item 11: -7
Enter item 12: -3435
Enter item 13: 23
Enter item 14: 0
Enter item 15: 23
Enter item 16: 88

Modes: 12 23

 


Problem 3: Subset Determination

A set is collection of elements, or members. A set S is said to be a subset of the set T if every member of S is also a member of T. S is said to be a proper subset of T if S is a subset of T and, in addition, at least one of the members of T is not a member of S.

Develop a program that determines whether one set of identifiers (strings containing only upper case letters) is a proper subset of another. The user enters the identifiers in each set all at once, with the identifiers separated by commas and with the entire list enclosed in parentheses. No set given as input will contain more than ten members, and no identifier will be longer than twelve characters. The output is simply YES or NO, the former if the second set is a proper subset of the first and the latter otherwise. The program should repeat until the user enters as a first set one containing no members.

Sample Program Execution:

Enter 1st set: (APPLE,GRAPE,PEAR,ORANGE,GRAPEFRUIT)
Enter 2nd set: (ORANGE,GRAPE)
YES

Enter 1st set: (APPLE,GRAPE,PEAR,ORANGE,GRAPEFRUIT)
Enter 2nd set: (ORANGE,BANANA,GRAPE)
NO

Enter 1st set: ()

 


Problem 4: Tiling

When contractors lay floor tile in a rectangular room, they should make sure that each tile on the perimeter has the same size as the one on the opposite side of the room. This gives a more appealing look to the final result.

Develop a program that, given as input

reports the number of full and partial tiles needed to cover the floor, as well as the dimensions of the partial tiles. (All measurements are expressed in the same unit of distance, e.g., inches). The program should repeat until the user enters zero as the floor length.

Partial tiles are ones that have been cut in order to reduce either their length, their width, or both. Such tiles are to be laid only on the perimeter of the floor. (The only tiles that need to be cut twice —in order to reduce both length and width— are corner tiles, the number of which is always either zero or four.)

Tiles are to be laid out so that grout gaps exist only between adjacent tiles, and never at the perimeter of the floor area. Thus, the number of tiles in any "row" or "column" is always exactly one greater than the number of grout gaps.

Sample Program Execution:

Enter floor length: 25.0
Enter floor width: 19.0
Enter length/width of tiles: 4.75
Enter grout gap: 0.25

12 full tiles
6 length-reduced tiles of length 2.375
8 width-reduced tiles of width 1.875
4 corner tiles

Enter floor length: 324.5
Enter floor width: 200.0
Enter length/width of tile: 6.0
Enter grout gap: 0.5

1500 full tiles
0 length-reduced tiles
100 width-reduced tiles of width 2.25
0 corner tiles

Enter floor length: 128.8
Enter floor width: 171.8
Enter length/width of tile: 4.1
Enter grout gap: 0.2

1200 full tiles
0 length-reduced tiles
0 width-reduced tiles
0 corner tiles

Enter floor length: 0.0

 


Problem 5: Hexadecimal Addition

Description omitted.

Sample Program Execution:

 


Problem 6: Speeders Beware

Write a program that, given as input

determines whether or not the average speed of the automobile ---in traveling from one checkpoint to the other--- exceeded the speed limit. All inputs are real numbers. The program should repeat until the user enters zero for the distance between checkpoints.

Reminder: There are 5280 feet in a mile and 3600 seconds in an hour.

Sample Program Execution:

Enter distance between checkpoints: 50.0
Enter time between checkpoints: 0.6
Enter speed limit: 55.0
SPEEDING

Enter distance between checkpoints: 2.5
Enter time between checkpoints: 0.035
Enter speed limit: 55.0
NOT SPEEDING

Enter distance between checkpoints: 0.0