University of Scranton 1992 High School Programming Contest Problems

Problem 1: Holey Squares
Problem 2: Binary to Decimal Translation
Problem 3: Summing Binary Numbers
Problem 4: Palindromic Numbers
Problem 5: Rational Arithmetic
Problem 6: Groceries: To Tax or Not To Tax

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: Holey Squares

A holey square is a square matrix each element of which is either a decimal digit or a "hole" (i.e., unoccupied). The digit in the first column of the first row (upper lefthand corner) is called the starting digit. As you scan the rows from top to bottom, each row from left to right, you find that the digits occur in succession (0 is followed by 1, which is followed by 2, ..., which is followed by 9, which is followed by 0). You also find that a hole appears immediately after each occurrence of a particular digit, called the holey digit. To illustrate, here is the holey square of size 5 (i.e., having 5 rows and 5 columns) having 7 as its starting digit and 9 as its holey digit:

7 8 9   0
1 2 3 4 5
6 7 8 9  
0 1 2 3 4
5 6 7 8 9

Develop a program that accepts as input the size, starting digit, and holey digit of a holey square, and that produces as output the corresponding holey square. The program should terminate when the user enters zero as the size.

Sample Program Execution:

Enter size: 9
Enter starting digit: 5
Enter holey digit: 5

5   6 7 8 9 0 1 2
3 4 5   6 7 8 9 0
1 2 3 4 5   6 7 8
9 0 1 2 3 4 5   6
7 8 9 0 1 2 3 4 5
  6 7 8 9 0 1 2 3
4 5   6 7 8 9 0 1
2 3 4 5   6 7 8 9
0 1 2 3 4 5   6 7


Enter size: 6
Enter starting digit: 3
Enter holey digit: 8

3 4 5 6 7 8
  9 0 1 2 3
4 5 6 7 8
9 0 1 2 3 4
5 6 7 8   9
0 1 2 3 4 5


Enter size: 0

 


Problem 2: Binary to Decimal Translation

In an electronic computer, all data is represented in binary form, i.e., as a sequence of 0's and 1's. In particular, integers are usually represented using the binary number system, as opposed to the decimal number system to which you are accustomed. These two number systems are actually very much alike. Indeed, they are both positional number systems, which means that the "contribution" made by each digit in a number depends not only upon its value but also upon its position within the number.

In the decimal (or base ten) system, we use the ten digits 0, 1, 2, ..., 9. Going from right to left, the positions in a number correspond to units of 1, 10, 100, 1000, etc. (Notice that these are the powers of 10: 100 = 1, 101 = 10, 102 = 100, 103 = 1000, etc.)  The expression 45038 is to be understood to mean

8×1  +  3×10  +  0×100  +  5×1000  +  4×10000

The binary (or base two) number system is just the same, except that we use only the two digits 0 and 1, and the positions in a number correspond to units of 1, 2, 4, 8, 16, etc. (the powers of 2). Thus, for example, 10011012 (the subscript indicates that the number is to be interpreted as one written in binary notation) is to be understood to mean

1×1  +  0×2  +  1×4  +  1×8  +  0×16  +  0×32  +  1×64

which, in decimal notation, is 77.

Develop a program that, given as input a number expressed in the binary number system, outputs the same number expressed in the decimal number system. The input will have no more than 12 digits. The program should terminate when the user enters 00 as input.

Sample Program Execution:

Enter binary number: 101011
Decimal representation: 43

Enter binary number: 0
Decimal representation: 0

Enter binary number: 10000101
Decimal representation: 133

Enter binary number: 00

 


Problem 3: Summing Binary Numbers

Develop a program that accepts as input two binary numbers and that calculates and outputs their sum (which is also to be expressed in binary form). Each input will have no more than thirty digits. The program should repeat until both inputs are zero.

As described in the previous problem, the binary number system is completely analogous to the more familiar decimal number system, in terms of how numbers are represented. Hence, it should not be surprising that the procedure for adding two decimal numbers (which you learned in elementary school) applies to binary numbers as well.

Indeed, just as with decimal numbers, we "line up" the two addends (so that digits in corresponding positions appear one above the other) and proceed from the rightmost (i.e., least significant) to the leftmost (i.e., most significant) position. (If one number has more digits than the other, we pad the latter with leading zero's.)

For each position, we add the incoming carry to the sum of the two digits in that position (one for each addend), yielding one of the values zero (002), one (012), two (102), or three (112). The digit of lesser significance goes into the corresponding position of the result; the digit of greater significance is carried into the next position.

Sample Program Execution:

1st number: 101101011
2nd number: 101101
Sum: 110011000

1st number: 1111
2nd number: 1010
Sum: 11001

1st number: 0
2nd number: 0

 


Problem 4: Palindromic Numbers

A palindrome is a string of characters that reads the same forwards as backwards. For example, if we ignore spaces, the phrase "may a moody baby doom a yam" is a palindrome. Here, we consider those palindromes consisting entirely of the digits 0 through 9 and not beginning with 0. Examples are 72427, 5, and 9009. Any number corresponding to such a palindrome is said to be a palindromic number. Note:  By this definition, numbers such as 3300, which could also be written with leading zeros as 003300, do not qualify as being palindromic.

Develop a program that takes as input a positive integer and that reports whether or not that integer is palindromic. The program should repeat until the user enters zero as input.

Sample Program Execution:

Enter number: 81248
NOT PALINDROMIC

Enter number: 4
PALINDROMIC

Enter number: 30
NOT PALINDROMIC

Enter number: 405504
PALINDROMIC

Enter number: 0

 


Problem 5: Rational Arithmetic

A rational number is the ratio of two integers, the second of which is nonzero. We usually express such a number in the form n/d, i.e., as a fraction. We refer to n as the numerator and to d as the denominator. If d>1 and the greatest common divisor of n and d is one, we say that n/d is in simplest form. The simplest form of n/1 is n (with no denominator).

Most programming languages have built-in facilities for representing and manipulating integers so that calculations performed upon them yield exact results. The same is not true of real numbers. Indeed, a "real" number stored in a computer is only an approximation to the number it is intended to represent. This is due to the fact that, in general, to represent a real number exactly requires infinitely many digits, whereas a computer has only a finite memory capacity.

Few programming languages have built-in facilities for dealing with rational numbers. This is not necessarily an oversight: due to the fact that all rational numbers are also real numbers, a programmer may use a language's built-in facilities for real numbers in order to manipulate rationals. Results of calculations will be only approximations, however. This problem challenges you to remedy this situation by developing a program that performs exact arithmetic upon rational numbers!

Write a program that accepts as input a sequence of four nonnegative integers n1, d1, n2, d2, followed by a symbol op, which must be one of the four basic arithmetic operators (+, -, *, or /). The program should evaluate the expression

n1/d1  op  n2/d2

and display the result, which must be in simplest form. The required format for input and output is illustrated below. The program should terminate when the user enters 0 for either of the inputs d1 or d2

Sample Program Execution:

Enter Expression: 25 45 8 99 +
25/45 + 8/99 = 7/11

Enter Expression: 7 9 18 28 *
7/9 * 18/28 = 1/2

Enter Expression: 12 13 3 26 /
12/13 / 3/26 = 8

Enter Expression: 5 0 2 1 -

 


Problem 6: Groceries: To Tax or Not To Tax

Among the items sold at grocery stores, some are taxable and some are not. Thus, when you make a purchase, the final bill is the sum of the prices of the non-taxable items plus the sum of the prices of the taxable items, plus the tax on the taxable items.

Develop a program that calculates a grocery store bill. As input, the user supplies the number of items purchased and, for each item, its price (in dollars) and either Y or N to indicate whether or not, respectively, it is taxable. A tax rate of 6% is to be applied to the sum of the prices of the taxable items. Tax should be rounded to the nearest hundredth of a dollar (i.e., cent). Notice that in the two examples below, 6% of the cost of the taxable items is $0.4506 and $0.4572, respectively, which round to $0.45 and $0.46, respectively. The program should repeat until the user enters zero for the number of items purchased.

Sample Program Execution:

Number of items purchased: 4
Price of item 1: 2.39
Taxable? : N
Price of item 2: 3.12
Taxable? : Y
Price of item 3: 4.39
Taxable? : Y
Price of item 4: 2.09
Taxable? : N

Subtotal is 11.99
Tax is 0.45
Grand total is 12.44

Number of items purchased: 3
Price of item 1: 5.61
Taxable? : Y
Price of item 2: 2.01
Taxable? : Y
Price of item 3: 3.28
Taxable? : N

Subtotal is 10.90
Tax is 0.46
Grand total is 11.36

Number of items purchased: 0