University of Scranton 1999 High School Programming Contest Problems

Problem 1: What's My Score?
Problem 2: Spiral of Squares
Problem 3: Hill Removal
Problem 4: Number Representation in the Factorial Base
Problem 5: No Hassle Auto Insurance
Problem 6: Lax Security

 


Problem 1: What's My Score?

Ann, Bob, Carol, and Dave played nine holes of golf together. On the first hole, Ann teed off first, followed by Bob, then Carol, and, finally, Dave. At each subsequent hole, the order in which they teed off was in accord with the usual golfing convention, which is as follows: The golfer with the lowest score on the previous hole tees off first, followed by the golfer with the second lowest score, etc., etc. Golfers having equal scores on the previous hole tee off in the same relative order as they did on the previous hole.

A scorecard has four columns (one for each golfer) and nine rows (one for each of the nine holes). The score achieved by a given golfer on a given hole is to be recorded in the row corresponding to that hole in the column corresponding to that golfer.

Bob was responsible for keeping score. He was well aware that the scores achieved by the golfers on a given hole were to be recorded on the scorecard in the row corresponding to that hole. Unfortunately, he did not possess a proper understanding of the purpose of the four columns on the scorecard! He thought that the first column was for recording the score of the golfer who teed off first on the given hole, the second column was for recording the score of the golfer who teed off second on the given hole, etc., etc. Thus, in each row of the scorecard, Bob recorded the correct scores, but (usually, at least) in the wrong columns.

You are to develop a program that takes as input the scorecard filled out by Bob and that produces as output the "correct" scorecard.

As illustrated in the example below, your program should prompt the user to enter Bob's original scorecard. The user shall enter nine lines of data, each containing four positive integers separated from each other by at least one space. Your program should then display the correct scorecard, with one column showing hole numbers and four subsequent columns in which the scores of Ann, Bob, Carol, and Dave are displayed, in that order. Each golfer's total score (the sum of the scores on the nine holes) should be displayed at the bottom of her/his column.

Sample Program Execution:

Enter original scorecard:
4 6 5 5
5 4 6 4
4 3 6 5
4 4 3 5
5 3 4 4
5 5 5 5
4 4 4 4
4 4 4 4
2 4 3 4


Corrected scorecard:
1   4  6  5  5
2   5  4  4  6
3   6  3  4  5
4   5  4  4  3
5   4  3  4  5
6   5  5  5  5
7   4  4  4  4
8   4  4  4  4
9   3  2  4  4
 --------------
   40 35 38 41

 


Problem 2: Spiral of Squares

Imagine a grid whose cells have been numbered, starting at zero, in the outwardly-spiraling pattern illustrated below. Imagine that the spiral extends out to infinity.

               56 57 58 59 60 61 62 63 64
               55 30 31 32 33 34 35 36 65
               54 29 12 13 14 15 16 37 66
               53 28 11  2  3  4 17 38 67
               52 27 10  1  0  5 18 39 68
               51 26  9  8  7  6 19 40 69
               50 25 24 23 22 21 20 41 70
               49 48 47 46 45 44 43 42 71
               80 79 78 77 76 75 74 73 72

You are to develop a program that, given as input two nonnegative integers j and k, with neither exceeding 1000, outputs the distance on the grid between the cells numbered j and k.

By distance between two cells we mean the fewest number of steps by which it is possible to get from one to the other, assuming that in each step we can move one position in a horizontal or vertical (but not diagonal) direction.

End of input is signaled when both inputs are zero.

Sample Program Execution:

Enter two inputs:
15 42
Distance: 7

Enter two inputs:
132 132
Distance: 0

Enter two inputs:
37 25
Distance: 10

Enter two inputs:
0 0

 


Problem 3: Hill Removal

A sequence of three or more integers whose members are in strictly increasing or strictly decreasing order is called a hill . (For example, 2, 5, 8, 9 and 5, 3,-1 are hills. However, 4, 7, 7, 12 is not, because its 3rd member is no greater than its 2nd.)

A sequence of integers that is not itself a hill may contain one or more contiguous subsequences that are hills. For example, the sequence 5,3,5,9,7,4,1,2 contains as subsequences the hills 3,5,9 and 9,7,4 and 7,4,1 and 9,7,4,1.

Develop a program that, given as input a sequence of integers, rearranges them so that the resulting sequence contains no contiguous subsequences that are hills. For each input sequence, the user shall enter its length followed by the sequence itself (as illustrated below). Each number in the sequence will be separated from the next by at least one space. End of input is signaled by a sequence length of zero. The user shall not enter a sequence of length exceeding twenty.

Sample Program Execution:

Enter length of sequence: 9
Enter sequence: 5 8 5 3 7 9 12 6 8
5 8 3 7 5 9 6 12 8

Enter length of sequence: 6
Enter sequence: 1 2 3 4 5 6
1 3 2 5 4 6

Enter length of sequence: 2
Enter sequence: -1 5
-1 5

Enter length of sequence: 0

 


Problem 4: Number Representation in the Factorial Base

For a positive integer m, we define m! = 1 ⋅ 2 ⋅ 3 ⋅  ...  ⋅ m. That is, m! is the product of the positive integers 1 through m. (This is the well known factorial function.)

Interestingly, for every positive integer k there exists a unique sequence of nonnegative integers d1, d2, ..., dn, (where dj ≤ j for all j) such that

k = d1 ⋅1!  +  d2 ⋅2!  +  d3 ⋅3!  +  ...  +  dn ⋅n!

In the factorial base number system, the number k would be represented by the sequence of "digits" dn dn-1 ... d2 d1. For example, the number that we express as 523 in the standard decimal number system would be expressed by 41301 in the factorial base, corresponding to the fact that

523    =   1 ⋅ 1!  +  0 ⋅ 2!  +  3 ⋅ 3!  +  1 ⋅ 4!  +  4 ⋅ 5!    =   1 + 0 + 18 + 24 + 480

Develop a program that takes as input a positive integer and that produces as ouput its representation in the factorial base number system, as illustrated below. (Note: The "digits" in the output may be separated by spaces.) End of input is signaled by the user entering zero.

You may assume that the user shall enter no input value whose factorial base representation requires more than seven digits.

Hint: By repeatedly applying the distributive property of multiplication over addition, you will find that the number

k = d1 ⋅ 1!  + d2 ⋅ 2!  +  ...  + dn ⋅ n!
can also be written as follows:
k = d1 + 2(d2 + 3(d3 + 4(d4 + ... + (n-1)(dn-1 + n ⋅dn) ... )
Thus, for instance, to determine the digit d1, it suffices to take the remainder of the division k/2. The remaining digits can be determined by carrying out more divisions, using the same idea. End of Hint.

Sample Program Execution:

Enter number: 1811
2 3 0 1 2 1

Enter number: 684
5 3 2 0 0

Enter number: 0

 


Problem 5: No Hassle Auto Insurance

The No Hassle Auto Insurance company believes that everyone deserves a second chance, and therefore it does not raise the rate of a driver after he is involved in his first accident or receives his first ticket. However, the rate will increase for a driver involved in a second accident or receiving a second ticket. A driver whose number of accidents plus tickets exceeds four is uninsurable.

The basic formula for the rate charged by the No Hassle company is

r = 0.02 ⋅ c ⋅ a! ⋅ t! ⋅ y
where c stands for the value of the car (see below), a stands for number of accidents, t stands for number of tickets received, and y stands for the age multiplier (see below).

Recall that 0! = 1 and, for m > 0, m! = 1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ m (i.e., the product of the integers 1 through m). This is the well known factorial function.

To calculate c (the value of the car), the purchase price and age of the car are required. Specifically, the value of a car of age zero is its purchase price. The value of a car of age greater than zero is 90 percent of its previous year's value.

To calculate y, we need the driver's age. Specifically, for a driver between the ages of 16 and 24, y = 3. For ages 25 through 34, y = 1.5. For ages 35 through 44, y = 1. For ages, 45 through 64, y = 1.5. For ages 65 and above, y = 3.

Develop a program that takes as input the purchase price and age of a car, the age of its driver, the number of accidents in which the driver has been involved, and the number of tickets the driver has received. (All these will be nonnegative integers.) As output, the program should display the insurance rate for the driver or a message indicating that she is uninsurable.

Sample Program Execution (1):

Enter purchase price of car: 20000
Enter age of car: 3
Enter age of driver: 26
Enter number of accidents: 0
Enter number of tickets: 2
Rate: 874.80

Sample Program Execution (2):

Enter purchase price of car: 12000
Enter age of car: 1
Enter age of driver: 19
Enter number of accidents: 1
Enter number of tickets: 2
Rate: 1296.00

Sample Program Execution (3):

Enter purchase price of car: 34000
Enter age of car: 6
Enter age of driver: 80
Enter number of accidents: 1
Enter number of tickets: 4
Rate: Uninsurable

 


Problem 6: Lax Security

The Lax Hazardous Waste Company must maintain a certain level of security at its plant because of the nature of the materials handled there. The main door to the plant has a keypad similar to the one shown below. To open the door, an employee must first enter her five-digit personal identification number (PIN). If the PIN is valid, the door opens. Otherwise, it does not.

                     +---+ +---+ +---+
                     | 1 | | 2 | | 3 |
                     +---+ +---+ +---+
                     +---+ +---+ +---+
                     | 4 | | 5 | | 6 |
                     +---+ +---+ +---+
                     +---+ +---+ +---+
                     | 7 | | 8 | | 9 |
                     +---+ +---+ +---+
                           +---+
                           | 0 |
                           +---+ 

However, Bocefus Lax, the company owner, is a nice guy who doesn't like to burden his employees unnecessarily. The digits on the keypad are close together and employees often enter their PIN incorrectly by pressing an adjacent button instead of the intended one. Therefore, he wants to modify the access system so that it allows an employee to open the door even if the PIN they enter is slightly incorrect. Specifically, Bocefus is willing to assume that the person using the keypad is a valid employee if the number entered has no more than one digit that is off-by-one from some valid PIN. Here, off-by-one means that, with respect to the keypad, the incorrect digit is either immediately above, below, to the right of, or to the left of the correct digit. (For example, the digits that are off-by-one from 4 are 1, 5, and 7.)

Develop a program that takes as input a list of valid PINs followed by a list of numbers that were entered on the keypad. For each number in the latter list, the program should report whether it is accepted or rejected. For each accepted number, the program reports which valid PIN it matches (exactly or approximately).

Note that a number entered on the keypad could match more than one valid PIN. For example, the PIN 22222 is off-by-one from 21222, 52222, 22223, and many others. If a number entered on the keypad matches a valid PIN exactly, that PIN should be identified. If not, but if the number approximately matches some valid PIN, report the first such valid PIN in the list.

End of input is signaled by the user entering all zeros.

Sample Program Execution:

Enter number of valid PINs: 4
10360
36243
39491
26543


Enter a number: 39491
Matches 39491

Enter a number: 36491
Matches 39491

Enter a number: 14543
No matches

Enter a number: 26243
Matches 36243

Enter a number: 00000


File translated from TEX by TTH, version 2.00.
On 16 Apr 1999, 05:45.