The ACM Scholastic Programming Contest
sponsored by AT&T Computer Systems
1990
Mountain Region
Programming Contest
Problem Set
General Instructions:
What is to be submitted for judging must be a program file of the
PROGn.EXE or PROGn.COM form; where 'n' is the assigned number for the
program. The judges will attempt to execute your program by typing PROGn.
They will not look in the directory to see what you chose to call your
program. It must run automatically without the need for the judges to
compile the code. In other words, you are to compile your program to
executable form on disk, and it must have the proper name indicated above.
For every program that requires an input file, please use the file name
PROGn.DAT where 'n' is the assigned number for the program. Do not precede
the input file name with any directory or disk drive designation.
The judges have been instructed not to make any effort to remedy
incorrect program names or data file names. Programs that do not run
properly according to the foregoing ground rules will be designated incorrect
and returned to the submitters with an appropriate error indicated.
1. COMBINATIONS
Computing the exact number of ways that N things can be taken M at a
time can be a great challenge when N and/or M become very large. Challenges
are the stuff of contests. Therefore, you are to make just such a
computation given the following:
GIVEN: 5 <= N <= 100, and
5 <= M <= 100, and M <= N
Compute the EXACT value of:
N!
C = -------------
(N-M)! * M!
You may assume that the final value of C will fit in a 32-bit Pascal LongInt
or a C long.
For the record, the exact value of 100! is:
93,326,215,443,944,152,681,699,238,856,266,700,490,715,
968,264,381,621,468,592,963,895,217,599,993,229,915,
608,941,463,976,156,518,286,253,697,920,827,223,758,
251,185,210,916,864,000,000,000,000,000,000,000,000
The input to this program will be one or more lines each containing zero
or more leading spaces, a value for N, one or more spaces, and a value for M.
Typical examples of an input set might be:
100 6
20 5
18 6
12 3
4 2
0 0
The last line of the input file will contain a dummy N, M pair with both
values equal to zero. Your program should terminate when this line is read.
The output from this program should be in the form:
N things taken M at a time is C exactly.
The corresponding output lines for the input set provided above is:
100 things taken 6 at a time is 1192052400 exactly.
20 things taken 5 at a time is 15504 exactly.
18 things taken 6 at a time is 18564 exactly.
12 things taken 3 at a time is 220 exactly.
4 things taken 2 at a time is 6 exactly.
2. BINGO
The game of BINGO is another of the great American pastimes. Our
version of BINGO is to be played on a square card containing a 5x5 matrix.
The first five lines of the input file will each contain five integer values
separated by spaces in the range 0 <= V <= 99; these values are to be placed
in the corresponding row of the matrix from left to right. Immediately
following the the values for the card will be a series of lines each
containing one "called" number such that 1 <= C <= 99; the last line will
contain an invalid "called" number of zero (0).
For this problem, you are to write a program that accepts the integers
that are to be placed in the cells of a "BINGO" card. Then you are to read
in the "called" values, which may or may not be the same as the numbers on
your BINGO card, one at a time until you either find a BINGO, or you run out
of called numbers. Each called number is to be echoed to the screen on a
line by itself as it is read. If you run out of called numbers before you
find a BINGO, you are to print out the following message immediately
following the last valid "called" number:
No BINGO on this card.
If you find a BINGO at some point in the input, you are to stop reading the
input values, and print out a notification of the BINGO followed by a list of
comma separated triples in ROW MAJOR Order that represent the Row, Column,
and Value of all of the elements making up the BINGO. The output should have
the following format:
BINGO
R, C, V
R, C, V
...
Where:
R = row subscript from 1 to 5, and
C = column subscript from 1 to 5, and
V = called number value that matched the cell contents, or the
word FREE.
A BINGO occurs when one of the following rules has been fulfilled:
1. Each of the five elements in a row have either been matched by a
called number, or are FREE, or
2. Each of the five elements in a column have either been matched by
a called number, or are FREE, or
3. Each of the four corner elements have either been matched by a
called number, or are FREE.
4. Each of the five elements in either prime diagonal have been
matched by a called number or are FREE.
Any element in the matrix containing a zero (0) after the original load is
FREE, and is considered to have been matched.
3. ACKERMANN FUNCTIONS
An Ackermann function has the characteristic that the length of the
sequence of numbers generated by the function cannot be computed directly
from the input value. One particular integer Ackermann function is the
following:
IF Xn is even Xn / 2
Xn+1 := and
IF Xn is odd 3 * Xn + 1
This Ackermann has the characteristic that it eventually converges on 1. A
few examples follow in which the starting value is shown in square brackets
followed by the sequence of values that are generated, followed by the length
of the sequence in curly braces:
[10] 5 16 8 4 2 1 {6}
[13] 40 20 10 5 16 8 4 2 1 {9}
[14] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 {17}
[19] 58 29 88 44 22 ... 2 1 {20}
[32] 16 8 4 2 1 {5}
[1] 4 2 1 {3}
Your program is to read in a series of pairs of values that represent the
first and last numbers in a closed sequence. For each closed sequence pair
determine which value generates the longest series of values before it
converges to 1. The largest value in the sequence will not be larger than
can be accomodated in a 32-bit Pascal LongInt or C long. The last pair of
values will be 0, 0. The output from your program should be as follows:
Between L and H, V generates the longest sequence of S values.
WHERE:
L =the lower boundary value in the sequence
H = the upper boundary value in the sequence
V = the {first} value that generates the longest sequence,
(if two or more values generate the longest sequence
then only show the lower value)
S = the length of the generated sequence.
In the event that two numbers in the interval should both produce equally
long sequences, report the first.
SAMPLE INPUT
1 20
35 55
0 0
CORRESPONDING OUTPUT
Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 35 and 55, 54 generates the longest sequence of 112 values.
4. WhatFix Notation
There are three traversal methods commonly used in compilers and calculators:
prefix
infix
postfix
For example, a single expression can be written in each form
infix: a + b * c
prefix: + a * b c
postfix: a b c * +
Note that prefix and postfix ARE NOT mirror images of each other! The
advantage of prefix and postfix notations is that parentheses are unnecessary
to prevent ambiguity.
In our traversal the following symbols are operators with precedence rules
going from highest to lowest:
$ exponentiation
* / multiply and divide
+ - add and subtract
& | AND and OR
! NOT
The Problem:
You are given two strings. The first string is the infix version of the
expression. The second string is the prefix version of the expression.
Determine the postfix version of the expression and print it out on a single
line.
All input will be single characters separated by a space. Output must be the
same, single characters separated by a space. There are no special sentinels
identifying the end of the data.
Example input data
a + b - c
+ a - b c
Your output should be
INFIX => a + b - c
PREFIX => + a - b c
POSTFIX => a b c - +
5. ROMULAN SPELLING
The Romulans use a language that can be approximated with the English
alphabet and normal punctuation marks. Their spelling rules are even stranger
than English, however. In particular, they have a rule that states:
G before P except after E or when pronounced X as in npguk-
bor or wpguk.
Operationally, you can detect the X pronounciation by the string PGUK
appearing in the word. Also, the Romulan rules for capitalization are
different from ours, so capital letters can appear anywhere in a word.
Given a file containing lines of Romulan text, you are to output the text
with spelling corrected according to the G before P except after E rule given
above. No input line will contain more than 70 characters including spaces.
For example, the input file corresponding to the romulan translation of the
quote:
"I received the wierd piece of pie from my neighbor sam who in turn recieved
the weird peice of pei from his nieghbor harry,"
might well be ...
"I rpEpgvpd tKp wgprd tgpEp of tgp from my npguKbor sam wKo gn turn rpEgpvpd
tKp wpgrd tpgEp of tpg from Kgs ngpuKbor Karry,"
should produce the output file:
"I rpEpgvpd tKp wgprd tgpEp of tgp from my npguKbor sam wKo gn turn rpEpgvpd
tKp wgprd tgpEp of tgp from Kgs npguKbor Karry,"
6. BIG MOD
Calculate
R := BP mod M
for large values of B, P, and M using an efficient algorithm.
That's right, this problem has a time dependency.
Input:
Three integer values (in the order B, P, M) will be read one number per
line. B and P are integers in the range 0 to 2147483647 inclusive. M is an
integer in the range 1 to 46340 inclusive.
Output:
The result of the computation. A single integer.
Sample input Corresponding output
3
18132
17 13
17
1765
3 3
2374859
3029382
36123 13195
7. Inscribed Circles and Isosceles Triangles
Given two real numbers
B the width of the base of an isoceles triangle in inches
H the altitude of the same isoceles triangle in inches
Compute to six significant decimal places
C the sum of the circumfrences of a series of inscribed circles
stacked one on top of another from the base to the peak; such that
the lowest inscribed circle is tangent to the base and the two
sides and the next higher inscribed circle is tangent to the lowest
inscribed circle and the two sides, etc. In order to keep the time
required to compute the result within reasonable bounds, you may
limit the radius of the smallest inscribed circle in the stack to
a single precision floating point value of 0.000001.
For those whose geometry and trigonometry are a bit rusty, the center of an
inscribed circle is at the point of intersection of the three angular
bisectors.
The input will be a single line of text containing two positive single
precision real numbers (B H) separated by spaces.
The output should be a single real number with twelve significant digits, six
of which follow the decimal point.
8. More Triangles ... THE AMBIGUOUS CASE
The ambiguous case in trigonometry calls for the solution of triangles when
given two sides and the angle opposite one of them. You are to write a
program that accepts such data and reports all solutions.
The input data for each case will consist of a single input line containing
three real numbers separated by an arbitrary number of spaces. The first two
real numbers on each input line represent the lengths of two sides of a
triangle. The third real number on each input line is an angle (measured in
degrees) which is opposite the second of the two given sides. The stream of
input cases is terminated when all three pieces of data are zero.
Your program is to read the data and analyze the data for each case, and
produce a report of the results according to the format shown below. Each
case report consists of the number of solutions for the case, and the
corresponding solutions (to two decimal places) when the number of solutions
is nonzero. Please assign a case number to each set of data starting with
1.
SAMPLE INPUT
2.00 2.00 30.00
2.00 3.00 130.00
1.00 1.00 90.00
CORRESPONDING OUTPUT
Case A B THETA # of Side Side
# side side (deg) Triags 1 2
1 2.00 2.00 30.00 1 3.46
2 2.00 3.00 130.00 1 1.29
3 1.00 1.00 90.00 0
END OF REPORT for 3 cases