University of Scranton
1993 High School Programming Contest Problems

Problem 1: Wrap Around Numbers
Problem 2: Oh only have Oh's for a
Problem 3: Back in the Saddle Again
Problem 4: Ten's Complements
Problem 5: Cash Register
Problem 6: Right Triangles

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: Wrap Around Numbers

Let's define a trip through a number to be constructed as follows: Visit the leftmost digit of the number. That digit tells you which digit to visit next: move to the right, wrapping around to the left end of the number if necessary, as many places as the value of the digit. Continue this process until some digit is visited for a second time. If all digits have been visited, the number qualifies as a wrap around number. Otherwise, it does not.

For example, consider the number 32741. We visit the leftmost digit, which tells us to next visit the digit three places to the right, which is the 4. Next we visit the 7 (which is four places to the right of the 4), then the 1, then the 3 again. The trip has returned to a digit for the second time without having visited all the digits. (The 2 was never visited.) Thus, 32741 is not a wrap around number. On the other hand, 3233 is a wrap around number, as we would first visit the leftmost 3, then the rightmost 3, then the middle 3, then the 2, and then return to the rightmost 3. All four digits are visited.

Write a program that accepts as input a positive integer having at most twelve digits and that reports whether or not it is a wrap around number. The program should repeat until the user enters zero as input.

Sample Program Execution:

Enter input: 872
872 IS a wrap around number.

Enter input: 351267853
351267853 IS NOT a wrap around number.

Enter input: 0

 


Problem 2: Oh only have Oh's for a

The term plaintext refers to a message in "ordinary" form. The term ciphertext refers to an encoded form of some plaintext. The process of translating plaintext to ciphertext is called encoding and the inverse process is called decoding.

Develop a program that, given as input a string of characters (serving as plaintext), outputs its ciphertext, according to the following encoding scheme:

You may assume that the plaintext given as input contains no lower case letters and has length no greater than 40. The program should repeat until the user enters plaintext of length zero.

Sample Program Execution:

Enter plaintext: YOUR CAT IS AN IDIOT.
Ciphertext: YUAR CET OS EN ODOUT.

Enter plaintext:

 


Problem 3: Back in the Saddle Again

Let A be an m × n integer array. (This means that A is a (two-dimensional) table having m rows and n columns each element of which is an integer.) A saddle point of A is an element that is

It is not difficult to prove that, in any two-dimensional integer array, there can be at most one saddle point of each of the two types.

Develop a program that, given as input a two-dimensional integer array, reports (in the format shown below) which of its elements are saddle points. The program should repeat until the user indicates that the array to be processed has zero rows. No array given as input will exceed 20 rows or 20 columns.

Sample Program Execution:

Enter number of rows: 4
Enter number of columns: 3
Row 1: 2 -3 -8
Row 2: 0 -7 -4
Row 3: 3 6 1
Row 4: 7 5 -2

Type 1 saddle point: row 2 column 1
Type 2 saddle point: row 3 column 3

Enter number of rows: 3
Enter number of columns: 5
Row 1: 1 0 3 2 6
Row 2: 7 2 6 9 6
Row 3: 2 -4 -8 4 3

Type 1 saddle point: none
Type 2 saddle point: row 2 column 2

Enter number of rows: 2
Enter number of columns: 2
Row 1: 0 6
Row 2: 7 2

Type 1 saddle point: none
Type 2 saddle point: none

Enter number of rows: 0

 


Problem 4: Ten's Complements

The ten's complement of a nonnegative integer n is the integer formed by subtracting each digit of n from 9 and then adding one to the result. For example, the ten's complement of 35 is 64 + 1, or 65.

Note that the ten's complement of 27 is 73 but that the ten's complement of 0027 is 9973. Thus, the ten's complement of a number depends upon how many leading zeros we include in expressing it. (For this reason it is more accurate to say that each representation of a number has a ten's complement than to say that each number has a ten's complement.)

Develop a program that, given as input a nonnegative integer having no more than 20 digits, outputs its ten's complement. The program should repeat until the user enters 000 as input.

Sample Program Execution:

Enter number: 83078
Ten's complement: 16922

Enter number: 0083078
Ten's complement: 9916922

Enter number: 300
Ten's complement: 700

Enter number: 000
Ten's complement: 1000

 


Problem 5: Cash Register

Write a program that "makes change" from a cash register for a series of purchases. In order to keep the problem relatively simple, you are to assume that the cash register has an unlimited supply of one dollar bills. (In particular, this means that the amount of change, in coins, returned to a customer should never exceed 99 cents.)

The program should begin by reading a set of inputs that indicates how many quarters, dimes, nickels, and pennies can be found, initially, in the cash register. That will be followed by a series of cash register transactions, each of which occurs as a result of a customer purchase. Each transaction consists of two steps: first, the customer pays (i.e., tenders cash) for the purchase, and, second, the customer is given correct change. The first step of each transaction is described by six inputs:

  1. purchase price, in dollars (real number with at most two digits after decimal point),
  2. amount tendered, in dollars (real number with at most two digits after decimal point),
  3. number of quarters tendered (nonnegative integer)
  4. number of dimes tendered (nonnegative integer)
  5. number of nickels tendered (nonnegative integer)
  6. number of pennies tendered (nonnegative integer)
The number of quarters, dimes, etc., tendered by the customer is important, because your program must keep track of how many of each kind of coin are available in the cash register for making change.

The second step of each transaction is reported, as output, by your program. Specifically, the program should display the total amount of change to be returned to the customer, followed by the number of quarters, dimes, nickels, and pennies used in making that change. The number of coins used in making change should be the minimum possible. This depends not only upon the amount of change, but also upon how many of each kind of coin are currently available in the cash register. For example, if 56 cents are to be returned, the preferred solution is to use two quarters, one nickel, and one penny (a total of four coins). However, if the register has only one quarter, then that quarter, plus 31 cents in available dimes, nickels, and pennies would be used to make change. (This would require at least five coins.) If it is not possible to make exact change with the coins available in the cash register, the transaction is voided (meaning that the coins tendered by the customer are given back) and a relevant message is displayed. (See example below.)

You may assume that the inputs describing a transaction are "valid". For example, the amount tendered cannot be less than the purchase price. Also, the number of quarters, etc., tendered must be consistent with the amount tendered. For example, if the amount tendered is 13.72, then the values of the coins tendered must add up to some number of dollars (no more than 13) and 72 cents.

A number of observations about the sample program execution below may be helpful. Notice that, in the first transaction, the customer tendered over a dollar in coins. This is acceptable. Notice that the second transaction was voided because the cash register had too few pennies to make four cents change. (There were initially five pennies in the register, but two were removed in making change for the first purchase, leaving only three.) Notice that, in the third transaction, one dime and two nickels were used in making change, rather than two dimes. This is due to the fact that there was only one dime remaining in the register after the second transaction.

Sample Program Execution:

Initial Number of Quarters: 6
Initial Number of Dimes: 3
Initial Number of Nickels: 12
Initial Number of Pennies: 5

Purchase Price: 16.27
Amount Tendered: 21.50
Quarters Tendered: 6
Dimes Tendered: 0
Nickels Tendered: 0
Pennies Tendered: 0

Change Due: 5.23
Quarters returned: 0
Dimes returned: 2
Nickels returned: 0
Pennies returned: 3

Purchase Price: 0.51
Amount Tendered: 0.55
Quarters Tendered: 2
Dimes Tendered: 0
Nickels Tendered: 1
Pennies Tendered: 0

Change Due: 0.04
TRANSACTION VOIDED: CANNOT MAKE EXACT CHANGE

Purchase Price: 3.30
Amount Tendered: 5.00
Quarters Tendered: 0
Dimes Tendered: 0
Nickels Tendered: 0
Pennies Tendered: 0

Change Due: 1.70
Quarters returned: 2
Dimes returned: 1
Nickels returned: 2
Pennies returned: 0

Purchase Price: 0.00

 


Problem 6: Right Triangles

Write a program that, given as input three distinct points on the cartesian plane ---(x1y1), (x2y2), and (x3y3)--- reports whether the triangle they form is a right triangle.

The program should repeat until the user's input is such that the three points are not all distinct.

Recall that a triangle is a right triangle if and only if the square of the length of its longest side is equal to the sum of the squares of the lengths of its other two sides.

Sample Program Execution:

Enter x1: 5.5
Enter y1: 3.0
Enter x2: 1.5
Enter y2: 3.0
Enter x3: 5.5
Enter y3: 6.0
RIGHT TRIANGLE

Enter x1: -1.0
Enter y1: 3.0
Enter x2: 4.5
Enter y2: 3.0
Enter x3: 7.0
Enter y3: -3.7
NOT RIGHT TRIANGLE

Enter x1: 0.0
Enter y1: 0.0
Enter x2: 4.5
Enter y2: 3.0
Enter x3: 0.0
Enter y3: 0.0