University of Scranton 1994 High School Programming Contest Problems

Problem 1: Perfect Numbers
Problem 2: Add Them Up
Problem 3: English Mathematical Parser
Problem 4: Conjugates
Problem 5: Wraparound Numbers
Problem 6: Square Roots

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: Perfect Numbers

A positive integer is said to be a perfect number if it is equal to the sum of its positive divisors less than itself. For example, 28 is perfect, because

28 = 1 + 2 + 4 + 7 + 14

On the other hand, 12 is not perfect, because

12 ≠ 1 + 2 + 3 + 4 + 6

You are to write a program that prompts the user to enter a positive integer and responds by reporting whether or not the given number is perfect. The program should terminate when the user enters 0.

Sample Program Execution:

Enter a positive integer: 12
12 IS NOT perfect.

Enter a positive integer: 28
28 IS perfect.

Enter a positive integer: 0

 


Problem 2: Add Them Up

Develop a program that takes as input two "long" nonnegative integers and ouputs their sum. The inputs will be no longer than 30 digits. (Thus, their sum will be no longer than 31 digits.) The program should repeat until the user enters zero for both inputs.

Sample Program Execution:

1st input: 10371
2nd input: 315
Result: 10686

1st input: 54696543201678654789456
2nd input: 82067690004564356875434
Result: 136764233206243011664890

1st input: 0
2nd input: 0
Result: 0

 


Problem 3: English Mathematical Parser

Develop a program that reads an arithmetic expression written in English, such as

NINE  PLUS  SEVEN

and that outputs the number that is the result of evaluating the expression.

More precisely, the input will be a one-digit number, written as a word in upper case letters, followed by a space, followed by one of the words "PLUS", "MINUS", "TIMES", or "DIVIDED-BY", followed by a space, followed by another one-digit number, written as a word in upper case letters.

Here, "DIVIDED-BY" means integer division. (Example: 8 divided by 3 is 2.)  The spellings for one-digit numbers are as follows: "ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", and "NINE". You may assume that no input expression will call for division by zero. Your program should repeat until the user enters an expression that evaluates to zero.

Sample Program Execution:

Input: NINE PLUS FOUR
Result: 13

Input: FIVE MINUS SEVEN
Result: -2

Input: EIGHT DIVIDED-BY THREE
Result: 2

Input: ZERO TIMES SIX
Result: 0

 


Problem 4: Conjugates

Two strings X and Y are said to be conjugates if, by shifting the symbols of Y in a cyclic fashion zero or more times, you can arrive at X. For example, the strings ababba and abbaab are conjugates because by shifting the symbols of the latter two positions to the right (or, equivalently, four positions to the left), you arrive at the former. On the other hand, ababba and abaabb are not conjugates, as you can easily verify. It is clear from the definition that two strings cannot be conjugates unless they have the same length.

You are to develop a program that prompts the user to enter two strings (the maximum length for a string is 20 characters) and that responds by reporting whether the two are conjugates. The program terminates when the user enters the empty string.

Sample Program Execution:

Enter 1st string: ababba
Enter 2nd string: abbaab
The two strings are conjugates.

Enter 1st string: ababba
Enter 2nd string: abaabb
The two strings are NOT conjugates.

Enter 1st string: ababbbbacabba
Enter 2nd string: acbabaabb
The two strings are NOT conjugates.

Enter 1st string:

 


Problem 5: Wraparound Numbers

Let us consider each digit in a positive integer to be:

  1. a "place" we can visit, and
  2. an instruction telling us how many places to the right we should move (wrapping around to the leftmost digit when necessary) to find the next place to visit.

For example, take the number 2635. Let us begin by visiting its leftmost digit, 2. It tells us that we should next visit the digit two places to its right, which is the 3. The 3 tells us to move three places to the right, which (wrapping around) lands us on the 6. We then move six places to the right (again wrapping around) to land on the 5. Moving five places to the right (which involves wrapping around twice) lands us on the 2. Notice that we are back to where we started and that every digit has been visited. This property characterizes the so-called wraparound numbers. That is, a wraparound number is a positive integer having the property that, if we begin by visiting its leftmost digit and proceed to visit its digits according to the rule we followed in the example above, all digits will be visited, and, furthermore, the first digit to be visited for a second time will be the leftmost one. Thus, 2635 is a wraparound number.

For another example, take 21674. It is not a wraparound number, because if we begin by visiting the 2, we will next visit the 6, then the 7, then the 2, then the 6, then the 7, etc., etc., never having visited the 1 or the 4. As a last example, take 12. It is not a wraparound number, because we would visit the 1, then the 2, and then the 2 again, failing to return to the leftmost digit.

You are to write a program that prompts the user to enter a positive integer and that responds by telling whether or not it is a wraparound number. The program should terminate when the user enters the number 0.

Sample Program Execution:

Please enter a number: 2635
2635 IS a wraparound number.

Please enter a number: 21674
21674 IS NOT a wraparound number.

Please enter a number: 0

 


Problem 6: Square Roots

Develop a program that takes as input a positive integer and outputs an approximation to its square root. Your program may not include a call to any built-in root-finding subprogram that may be available in your programming language environment.

The value computed by your program is considered to be correct if it satisfies at least one of the following conditions:

The program should terminate when the user enters zero as input.

Sample Program Execution:

Enter an integer: 9
Square root is 3.0008

Enter an integer: 27
Square root is 5.196

Enter an integer: 0