University of Scranton 1996 High School Programming Contest Problems

Problem 1: Calendar Creation
Problem 2: Regular Expressions
Problem 3: Complex Numbers
Problem 4: First-Come-First-Served Scheduling
Problem 5: Kill Your Neighbor
Problem 6: Zeckendorf's Theorem

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: Calendar Creation

Develop a program to create a calendar for one month. Your program will accept two inputs. The first input is the number of the month for which you will create the calendar. January is represented by 1, February by 2, and so on. The second input is the year for which you will create the calendar. The year is any positive integer between 1500 and 9999, inclusive. Your program should display a calendar representing that month, in the same form as shown in the example below. Your program should accept input and provide output until the user enters 0 as the month.

For our purposes, you are to assume that any year divisible by 4 is a leap year and that the Gregorian calendar applies all the way back to the year 1500. In the output, it is not necessary for the month name and year (March, 2012 in the example below) to be centered exactly above your calendar, but it should appear above the calendar. It may be helpful to note that January 1, 1500, was a Thursday and that the number of days in each month is as follows: January, March, May, July, August, October, and December each have 31; April, June, September, and November each have 30; February has 28 in non-leap years and 29 in leap years.

Sample Program Execution:

Enter Month: 3
Enter Year: 2012

       March, 2012
  S   M   T   W   T   F   S
                  1   2   3
  4   5   6   7   8   9  10
 11  12  13  14  15  16  17
 18  19  20  21  22  23  24
 25  26  27  28  29  30  31
Enter Month: 0

 


Problem 2: Regular Expressions

In theoretical computer science, a regular expression is a sequence of characters that denotes a set of strings. In the regular expressions that we consider here, the letters a and b are literals; meanwhile, parentheses, ( and ) , indicate repetition. For example, the expression (ab) denotes the set of strings

{ab, abab, ababab, . . . }.

This set includes any string that can be formed by repeating ab one or more times. Another example is bba(aa)bab, which denotes the set

{bbaaabab, bbaaaaabab, . . . }.

This set includes any string that begins with bba, ends with bab, and has one or more repetitions of aa in between. An even more complicated example is b(ab)b(ba), which denotes the set

{babbba, bababbba, babbbaba, . . . }.

This set includes any string that begins with b, which is followed by one or more repetitions of ab, which is followed by b, which is followed by one or more repetitions of ba.

A string is said to match a regular expression if it is a member of the set denoted by the regular expression. You are to develop a program that tells whether or not a given string matches a given regular expression. The first input is a regular expression (of a certain restricted form--see below for details). The second input is a nonnull string containing only the letters a and b. Your program should accept input and provide output until the user enters a null string for the regular expression.

To make the problem a little easier, we restrict attention to regular expressions of a certain form. Specifically, you may assume that any regular expression given as input is of the form

r1 r2 r3 … rk

where k>0 and where, for each j satisfying 0<j<=k, rj is a nonnull string of a’s and b’s, possibly surrounded by a pair of parentheses. (In other words, you need not concern yourself with regular expressions in which some parenthesized sub-expression is nested inside another, as in the expression (ab(ba)b)). Furthermore, you may assume that, if rj is of the form (x), then x is not a prefix of any string that matches the regular expression

rj+1 rj+2 … rk

For example, ab(aa)(b)abba is a valid input, as aa is NOT a prefix of any string matching the expression (b)abba and b is NOT a prefix of any string matching the expression abba. However, abba(aa)b(bbb)b(b)aab is not valid input, because bbb IS a prefix of a string matching the expression b(b)aab.

Hint: Break the regular expression into parts. For example, break aab(bb)abab into the sub-expressions aab, (bb), and abab. Then, starting with the first sub-expression, compare the sub-expression to the appropriate part of the test string.

Sample Program Execution:

Regular Expression: aab(ba)bb(a)b
Test String: aabbababbab

The test string matches the regular expression

Regular Expression: bba(bb)aa
Test String: bbabbbbbba

The test string does NOT match the regular expression

Regular Expression:

 


Problem 3: Complex Numbers

A complex number is a number a+bi where i = square root of -1. a is the real part of the complex number and b is the imaginary part of the complex number. When multiplying two complex numbers together, remember the acronym FOIL ("first times first, outer times outer, inner times inner, last times last"). That is,

(a+bi)(x+yi) = (ax - by) + i(ay + bx)

Write a program that evaluates a complex number raised to a given power. The first input is an integer representing the real part of the complex number. The second input is an integer representing the imaginary part of the complex number. The third input is an integer greater than or equal to 1 and represents the power to which the complex number is to be raised. Your program should accept input and provide output until the user enters -100 for the real part of the complex number.

Sample Program Execution:

Real Part: 5
Imaginary Part: -2
Power: 3

65 - 142i

Real Part: -100

 


Problem 4: First-Come-First-Served Scheduling

In operating systems, a process is defined as a program that is running in memory. Even though a computer can run multiple processes at the same time, only one process can actually be using the CPU at any given time. As a result, operating systems theory provides several methods of scheduling or allocating CPU time to each process. The simplest of these is called the First-Come-First-Served algorithm. This algorithm works by taking the first process to arrive and letting it run until it finishes. The second process in line cannot use the CPU until the first process has finished. A process is said to arrive when it is loaded into memory and begins looking for CPU time. When a process has arrived but is waiting to use the CPU, it is said to be in a wait state.

For example, let Process1 have an arrival time of 3 and a running time of 4 time units. Let Process 2 have an arrival time of 5 and a running time of 5 time units. Since Process1 arrived before Process2, it will go first. Since Process2 arrived while Process1 is running, it has to wait. The chart below gives a graphical representation of the two processes running where R=process running and W=process waiting.

                       1
             1 3 5 7 9 1
Process1       RRRR
Process2         WWRRRRR  

Your job is to implement a program that will simulate First-Come-First-Served scheduling and display the chart as shown in the example on the next page. The first input is an integer less than or equal to 10 representing the number of processes you will have to schedule. Then, starting with the first process, accept the arrival time of the process and then the running time of that process. The arrival time of the process is an integer greater than or equal to 1 and represents the time at which a process begins looking for CPU time. The running time is an integer greater than or equal to 1 and represents the number of time units a process needs to run.

Assume that all processes are always entered in the order they arrive. Therefore, Process1 will always arrive before or at the same time Process2 arrives. Also, if two process have the same arrival time, then the process entered first will go first. In other words, if Process2 and Process3 both arrive at time 12, then Process2 will run first since it was entered first in the input.

Assume that the space immediately following the colon (see example on next page) represents time 1, the second space represents time 2, and so on. Therefore, if a process is running at time 5, then an R should be in the fifth space following the colon. If a process is waiting, then display a W in that space. If a process is neither running nor waiting then display nothing for that space. Your program should accept input and provide output until the user enters 0 for the number of processes.

Sample Program Execution:

Number of Processes: 5

Starting Time for Process 1: 1
Running  Time for Process 1: 2
Starting Time for Process 2: 2
Running  Time for Process 2: 4
Starting Time for Process 3: 2
Running  Time for Process 3: 6
Starting Time for Process 4: 13
Running  Time for Process 4: 3
Starting Time for Process 5: 15
Running  Time for Process 5: 2

1: RR
2:  WRRRR
3:  WWWWWRRRRRR
4:             RRR
5:               WRR
Number of Processes: 0

 


Problem 5: Kill Your Neighbor

The planet Zendar is inhabited by beings (Zendarians) who are distinguishable from one another only by way of two attributes: murderousness and mortalness. With respect to the murderousness attribute, each Zendarian is either murderous or gentle. As for mortalness, each Zendarian is either mortal or immortal. A murderous Zendarian is capable of killing a mortal Zendarian. A gentle Zendarian is incapable of killing. An immortal Zendarian cannot be killed.

On the annual Feast of Zendar, a group of Zendarians is drafted to play the game Kill Your Neighbor. It works as follows. The players form a circle, with one player designated to be at position #1. Starting there, the positions are numbered consecutively going clockwise around the circle. The player at position #1 is first to take a turn. In taking a turn, a player behaves as follows: If he is gentle, he does nothing; if he is murderous, he walks around the circle, in the clockwise direction, until encountering a mortal Zendarian, whom he immediately kills. Then he returns to his original position. The next player entitled to take a turn is the first still-living Zendarian encountered in walking around the circle, in the clockwise direction, from the position of the Zendarian who just finished his turn. Note that at most one killing takes place on each turn, and no one commits suicide. (That would be immoral, after all.)

The game ends when stability is reached, i.e., when no more killings can occur.

To illustrate how the game is played, the table below shows the "history" of one game involving six Zendarians. The initial configuration of the game is shown, as is the situation resulting from each turn in which someone was killed. The two-character code describing each still-living player is described in the paragraph below. A player who has died is represented by a D.

    1   2   3   4   5   6
   -----------------------
1. MM  GM  GM  MM  GI  MI   initial configuration
2. MM   D  GM  MM  GI  MI   1 killed 2
3.  D   D  GM  MM  GI  MI   4 killed 1
4.  D   D   D  MM  GI  MI   6 killed 3
5.  D   D   D   D  GI  MI   6 killed 4  

Write a program that, given as input the initial configuration of a game of Kill Your Neighbor, reports which players remain alive at the end of the game. The first input is the number of Zendarians involved in the game. This number will be at least one but no more than 20. For each player, the program will prompt the user to enter a two-character string describing him. The user must enter either M or G (for murderous or gentle, respectively) as the first character and either M or I as the second (for mortal or immortal, respectively).

Sample Program Execution:

Number of Zendarians: 10

Zendarian 1: MM
Zendarian 2: GI
Zendarian 3: MI
Zendarian 4: MI
Zendarian 5: GM
Zendarian 6: MM
Zendarian 7: MM
Zendarian 8: GM
Zendarian 9: MM
Zendarian 10: MI

Zendarians alive at the end: 2 3 4 10

Number of Zendarians: 0

 


Problem 6: Zeckendorf's Theorem

Recall that the Fibonacci Sequence (0, 1, 1, 2, 3, 5, 8, 13, . . . ) is the sequence having 0 and 1 as its first two elements and in which each subsequent element in the sequence is the sum of the two preceding elements.

According to a theorem by Zeckendorf, any positive integer can be expressed as the sum of one or more Fibonacci numbers such that For example, the (only) Zeckendorf sum of 14 is 13 + 1. Although 5+3+2+2+2 = 14, it is not a Zeckendorf sum, on at least two separate grounds. First, 2 is used three times, while the definition prohibits even two occurrences of the same number. Second, 3 and 5 are consecutive Fibonacci numbers, while the definition prohibits the use of two such numbers.

Develop a program that accepts as input a nonnegative integer and that produces as output a Zeckendorf sum of that integer. The values in the sum should be written in decreasing order, with plus signs ("+") between them (as illustrated below). Your program should repeat until the user enters -1.

Sample Program Execution:

Enter a number: 30

21 + 8 + 1

Enter a number: 515

377 + 89 + 34 + 13 + 2

Enter a number: -1