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