2001 Xavier University Programming Contest 2001 Xavier University Programming Contest

Problem: Getting Chorded

The "names" of the notes on a standard 88-key piano keyboard start with A (the lowest note on the keyboard) and then proceed sequentially with A# (A-sharp), B, C, C#, D, D#, E, F, F#, G, and finally G#. After the first 12 notes are named, the pattern repeats, proceeding through the last key, which is named C.

Some notes have other common names. A# may also be called B\flat (B-flat), C# may be called D\flat, D# may be called E\flat, F# may be called G\flat, and G# may be called A\flat. (There are still other names, like C##, but we won't worry about those here!)

Most music includes chords, or groups of notes played at the same time. Many of these chords are given standard names. For example, the notes C, E, and G sounded together are called a C Major chord. While the particular C, E and G in the chord are frequently close together on the keyboard, for our purposes here, any C, E, and G played at the same time will constitute a C Major chord. It is the spacing between the notes on the keyboard that distinguishes a Major chord from others. As you can see, there are exactly three notes skipped between the C and the E (namely C#, D and D#), and then only two skipped between the E and the G (namely F and F#). If we start with a different note, say F#, we can easily tell that the notes in an F# Major chord are F#, A#, and C# (skipping G, G#, and A between F# and A#, and skipping B and C between A# and C#).

Another frequently encountered chord is the Minor chord. C Minor, for example, is played by sounding C, D#, and G. As you can see, C# and D are skipped between C and D#, and E, F and F# are skipped between D# and G. You should now be able to tell that the notes in an F# Minor chord are F#, A, and C#.

In this problem you will be presented with a sequence of lines, each containing the names of three notes. You are to identify if these three notes, taken together, form a Major or Minor chord. If they do, you will display the name of the chord. If they don't you'll also report that fact. Remember that the notes need not appear in the usual sequence. Case will be ignored in the input, and the symbol \flat will be indicated by the letter b. A blank or blanks will appear between the notes on each line, and may also precede the first note on the line or follow the third note on the line. Each line except the last will contain exactly three properly formed notes, so you need not check for errors. The last line will be entirely blank, and marks the end of the input data. The output is to be in the same style as shown in the examples below; do not use \flat to name chords-use only # when necessary.

Sample Input

C E G 
C E   F# 
G       C       E 
C Eb G 
c# a f# 
   f g#      C 

Sample Output

C E G is a C Major chord.
C E F# is unrecognized.
G C E is a C Major chord.
C Eb G is a C Minor chord.
c# a f# is a F# Minor chord.
f g# C is a F Minor chord.

Problem: Word Crosses

A word cross is formed by printing a pair of words, the first horizontally and the second vertically, so that they share a common letter. A leading word cross is one where the common letter is as near as possible to the beginning of the horizontal word, and, for this letter, as close as possible to the beginning of the vertical word. Thus DEFER and PREFECT would cross on the first 'E' in each word, PREFECT and DEFER would cross on the 'R'. Double leading word crosses use two pairs of words arranged so that the two horizontal words are on the same line and each pair forms a leading word cross.

Write a program that will read in sets of four words and form them (if possible) into double leading word crosses.

Input will consist of a series of lines, each line containing four words (two pairs). A word consists of 1 to 10 upper case letters, and will be separated from its neighbors by at least one space. The file will be terminated by a line consisting of a single #.

Output will consist of a series of double leading word crosses as defined above. Leave exactly three spaces between the horizontal words. If it is not possible to form both crosses, write the message `Unable to make two crosses'. Leave one blank line between output sets.

Sample Input

MATCHES  CHEESECAKE  PICNIC  EXCUSES
PEANUT  BANANA   VACUUM  GREEDY
A   VANISHING  LETTER TRICK
#

Sample Output

 C
 H
 E
 E
 S
 E          E
 C          X
MATCHES   PICNIC
 K          U
 E          S
            E
            S

Unable to make two crosses

V
A   LETTER
N     R
I     I
S     C
H     K
I
N
G

Problem: Trip Routing

Your employer, the California Car Club (CCC), has decided to provide a trip routing service to its members. Your job is to write a program which reads a list of departure point-destination point pairs and calculates the shortest routes between them. For each trip, your program will print a report which itemises the names of each city passed through, with route names and leg distances.

Input to your program will be in two parts. The first part is a map in the form of a list of highway segments. Each segment is designated by a line containing four fields which are separated by commas. The first two fields are 1-20 characters each, and are the names of the cities which are at each end of the highway segment. The third field is the 1-10 character name of the route. The fourth field is the number of miles between the two endpoints, expressed as a positive integer. The highway segment list will be terminated by an empty line.

The second part of the input is a list of departure point-destination point pairs, one per line. The departure point is given first, followed by a comma and the destination point. Each of the cities is guaranteed to have appeared in the first part of the input data, and there will be a path that connects them. The list is terminated by the end of file.

The output should be a series of reports, one for each departure point-destination point pair in the input. Each report should be in exactly the same form as those in the example below. There should be two blank lines before each report.

There will be no extraneous blanks in the input. There will be no more than 100 cities in the map and no more than 200 highway segments.

Sample input

San Luis Obispo,Bakersfield,CA-58,117
Bakersfield,Mojave,CA-58,65
Mojave,Barstow,CA-58,70
Barstow,Baker,I-15,62
Baker,Las Vegas,I-15,92
San Luis Obispo,Santa Barbara,US-101,106
San Luis Obispo,Santa Barbara,CA-1,113
Santa Barbara,Los Angeles,US-101,95
Bakersfield,Wheeler Ridge,CA-99,24
Wheeler Ridge,Los Angeles,I-5,88
Mojave,Los Angeles,CA-14,94
Los Angeles,San Bernardino,I-10,65
San Bernardino,Barstow,I-15,73
Los Angeles,San Diego,I-5,121
San Bernardino,San Diego,I-15,103

Santa Barbara,Las Vegas
San Diego,Los Angeles
San Luis Obispo,Los Angeles

Sample output

From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
Santa Barbara        Los Angeles          US-101        95
Los Angeles          San Bernardino       I-10          65
San Bernardino       Barstow              I-15          73
Barstow              Baker                I-15          62
Baker                Las Vegas            I-15          92
                                                     -----
                                          Total        387


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
San Diego            Los Angeles          I-5          121
                                                     -----
                                          Total        121


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
San Luis Obispo      Santa Barbara        US-101       106
Santa Barbara        Los Angeles          US-101        95 
                                                     -----
                                          Total        201

Problem: Finding Ratios

If you ever see a televised report on stock market activity, you'll hear the anchorperson say something like ``Gainers outnumbered losers 14 to 9,'' which means that for every 14 stocks that increased in value that day, approximately 9 other stocks declined in value. Often, as you hear that, you'll see on the screen something like this:

Gainers: 1498 Losers: 902

You'll notice that the anchorperson could have said ``Gainers outnumbered losers 5 to 3'', which is a more accurate approximation of what really happened.  After all, the exact ratio of winners to losers is (to the nearest millionth) 1.660754, and she reported a ratio of 14 to 9, which is 1.555555, for an error of 0.105199; she could have said ``5 to 3'', and introduced an error of only 1.666667-1.660754=0.005913.  The estimate ``5 to 3'' is not as accurate as ``1498 to 902'' of course; evidently, another goal is to use small integers to express the ratio. So, why did the anchorperson say ``14 to 9?''  Because her algorithm is to lop off the last two digits of each number and use those as the approximate ratio.

What the anchorperson needs is a list of rational approximations of increasing accuracy, so that she can pick one to read on the air. Specifically, she needs a sequence {a1, a2, ..., an} where a1 is a rational number with denominator 1 that most exactly matches the true ratio of winners to losers (rounding up in case of ties), ai+1 is the rational number with least denominator that provides a more accurate approximation than ai, and an is the exact ratio, expressed with the least possible denominator.  Given this sequence, the anchorperson can decide which ratio gives the best tradeoff between accuracy and simplicity.

For example, if 5 stocks rose in price and 4 fell, the best approximation with denominator 1 is 1/1; that is, for every stock that fell, about one rose.  This answer differs from the exact answer by 0.25 (1.0 vs 1.25).  The best approximations with two in the denominator are 2/2 and 3/2, but neither is an improvement on the ratio 1/1, so neither would be considered.  The best approximation with three in the denominator 4/3, is more accurate than any seen so far, so it is one that should be reported.  Finally, of course, 5/4 is exactly the ratio, and so it is the last number reported in the sequence.

The input will contain several pairs of positive integers. Each pair is on a line by itself, beginning in the first column and with a space between the two numbers.  The first number of a pair is the number of gaining stocks for the day, and the second number is the number of losing stocks for the day.   The total number of stocks never exceeds 5000.

The output for each input pair should contain a series of approximations to the ratio of gainers to losers.  The first approximation has '1' as its denominator, and the last is exactly the ratio of gainers to losers, expressed as a fraction with least possible denominator.  The approximations in between are increasingly accurate and have increasing denominators, as described above.

The approximations for a pair are printed one to a line, beginning in column one, with the numerator and denominator of an approximation separated by a slash (``/'').  A blank line separates one sequence of approximations from another.

Sample Input

5 4
1498 902

Sample Output

1/1
4/3
5/4

2/1
3/2
5/3
48/29
53/32
58/35
63/38
68/41
73/44
78/47
83/50
88/53
93/56
377/227
470/283
563/339
656/395
749/451

Problem: Overhanging Playing Cards

A single playing card can be placed on a table, carefully, so that the short edges of the card are parallel to the table's edge, and half the length of the card hangs over the edge of the table. If the card hung any further out, with its center of gravity off the table, it would fall off the table and flutter to the floor. The same reasoning applies if the card were placed on another card, rather than on a table.

Two playing cards can be arranged, carefully, with short edges parallel to table edges, to extend 3/4 of a card length beyond the edge of the table. The top card hangs half a card length past the edge of the bottom card. The bottom card hangs with only 1/4 of its length  past the table's edge. The center of gravity of the two cards combined lies just over the edge of the table.

Three playing cards can be arranged, with short edges parallel to table edges, and each card touching at most one other card, to  extend 11/12 of a card length beyond the edge of the table. The top two cards extend 3/4 of a card length beyond the edge of the bottom card, and the bottom card extends only 1/6 over the table's edge; the center of gravity of the three cards lines over the edges of the table.

If you keep stacking cards so that the edges are aligned and every card has at most one card above it and one below it, how far out can 4 cards extend over the table's edge? Or 52 cards? Or 1000 cards? Or 99999?

The input will contain several nonnegative integers, one to a line. No integer exceeds 99999. A blank line will indicate the end of the input

The generated output should contain, on successful completion of the program, a heading:

# Cards  Overhang

(that's two spaces between the words) and, following, a line for each input integer giving the length of the longest overhang achievable with the given number of cards, measured in cardlengths, and rounded to the nearest thousandth.  The length must be expressed with at least one digit before the decimal point and exactly three digits after it. The number of cards is right-justified in column 5, and the decimal points for the lengths lie in column 12.

Sample Input

1
2
3
4
30

Sample Output

# Cards  Overhang
   1      0.500
   2      0.750
   3      0.917
   4      1.042
  30      1.997

Problem: Stacks of Flapjacks

Given a stack of pancakes, you are to write a program that indicates how the stack can be sorted so that the largest pancake is on the bottom and the smallest pancake is on the top. The size of a pancake is given by the pancake's diameter. All pancakes in a stack have different diameters.

Sorting a stack is done by a sequence of pancake ``flips''. A flip consists of inserting a spatula between two pancakes in a stack and flipping (reversing) all the pancakes on the spatula (reversing the sub-stack). A flip is specified by giving the position of the pancake on the bottom of the sub-stack to be flipped (relative to the whole stack). The pancake on the bottom of the whole stack has position 1 and the pancake on the top of a stack of n pancakes has position n.

A stack is specified by giving the diameter of each pancake in the stack in the order in which the pancakes appear.

For example, consider the three stacks of pancakes below (in which pancake 8 is the top-most pancake of the left stack):

         8           7           2
         4           6           5
         6           4           8
         7           8           4
         5           5           6
         2           2           7
The stack on the left can be transformed to the stack in the middle via flip(3). The middle stack can be transformed into the right stack via the command flip(1).

The input consists of a sequence of stacks of pancakes. Each stack will consist of between 1 and 30 pancakes and each pancake will have an integer diameter between 1 and 100. The input is terminated by end-of-file. Each stack is given as a single line of input with the top pancake on a stack appearing first on a line, the bottom pancake appearing last, and all pancakes separated by a space.

For each stack of pancakes, the output should echo the original stack on one line, followed by some sequence of flips that results in the stack of pancakes being sorted so that the largest diameter pancake is on the bottom and the smallest on top. For each stack the sequence of flips should be terminated by a 0 (indicating no more flips necessary). Once a stack is sorted, no more flips should be made.

Sample Input

1 2 3 4 5
5 4 3 2 1
5 1 2 3 4

Sample Output

1 2 3 4 5
0
5 4 3 2 1
1 0
5 1 2 3 4
1 2 0


File translated from TEX by TTH, version 2.25.
On 21 Oct 2001, 13:44.