Official Problem Set
Slippery Rock University
Computer Science Department
High School Computer Programming Competition
February 11, 2003
For all problems, you may make the following assumptions:
No data line has more than 80 characters before the end-of-line marker.
Data is valid. E.g., if there are supposed to be 4 numbers on a line, there will be 4 numbers on the line; if they are supposed to be positive, they will be positive.
Example data does not necessarily include every special case of valid data. Your program is responsible for handling every valid special case.
Numeric data is space-separated on a line for C, C++, Java, and Pascal. It is comma-separated for BASIC and Python. (All examples below are shown with space-separated data, however.)
Text data is space separated regardless of your programming language.
The order in which the problems are given is not necessarily ascending order of difficulty.
1. Quadratic
Consider the standard equation form, y = Ax2+Bx+C. Given the values of A, B, C, and x, find and print the coordinates of the point on the curve of the equation at x.
Your output must be printed in standard ordered pair notation, i.e.,
(x, y). Print at least one decimal place, unless it is zero; e.g., for 43.2543 you could print 43.3, 43.25, or 43.254, etc.; for 18.0 you could print 18, 18., 18.0, or 18.00, etc. Do not print in scientific notation. There will be one set of data, i.e., values for A, B, C and x, per line. Repeat reading and processing until there is no more data.
Example: for the data:
3.6 5.2 -7.1 4.9
0.0 -2.1 34.9 0.0
The output might be:
(4.9, 104.8)
(0.0, 34.9)
2. Vicksburg Cipher
Perhaps the most common cipher used by the Confederacy during the Civil War was known as the Vicksburg Cipher (Stern, Secret Missions of the Civil War). This was actually based on an older cipher, the Vigenére Tableau. It was easily remembered and simply set up (alas, it was also fairly easy to break).
Begin with a table as follows:
ABCDE FGHIJ KLMNO PQRST UVWXYZ A ABCDE FGHIJ KLMNO PQRST UVWXYZ B BCDEF GHIJK LMNOP QRSTU VWXYZA C CDEFG HIJKL MNOPQ RSTUV WXYZAB D DEFGH IJKLM NOPQR STUVW XYZABC E EFGHI JKLMN OPQRS TUVWX YZABCD F FGHIJ KLMNO PQRST UVWXY ZABCDE G GHIJK LMNOP QRSTU VWXYZ ABCDEF H HIJKL MNOPQ RSTUV WXYZA BCDEFG I IJKLM NOPQR STUVW XYZAB CDEFGH J JKLMN OPQRS TUVWX YZABC DEFGHI K KLMNO PQRST UVWXY ZABCD EFGHIJ L LMNOP QRSTU VWXYZ ABCDE FGHIJK M MNOPQ RSTUV WXYZA BCDEF GHIJKL N NOPQR STUVW XYZAB CDEFG HIJKLM O OPQRS TUVWX YZABC DEFGH IJKLMN P PQRST UVWXY ZABCD EFGHI JKLMNO Q QRSTU VWXYZ ABCDE FGHIJ KLMNOP R RSTUV WXYZA BCDEF GHIJK LMNOPQ S STUVW XYZAB CDEFG HIJKL MNOPQR T TUVWX YZABC DEFGH IJKLM NOPQRS U UVWXY ZABCD EFGHI JKLMN OPQRST V VWXYZ ABCDE FGHIJ KLMNO PQRSTU W WXYZA BCDEF GHIJK LMNOP QRSTUV X XYZAB CDEFG HIJKL MNOPQ RSTUVW Y YZABC DEFGH IJKLM NOPQR STUVWX Z ZABCD EFGHI JKLMN OPQRS TUVWXY
Then you and your agent must agree upon a key phrase or key word. Names of Southern generals proved to be popular choices (and hence easily guessed by the damn Yankees).
Now write out your plaintext message, and below it repeat your key phrase as often as needed to cover your message; ignore any blanks or punctuation in the key phrase. At each sentence, start with the beginning of your key phrase again. So if the message was “THE ARMY MOVES AT MIDNIGHT. BE READY.” and the key phrase was STONEWALL JACKSON, you would write:
THE ARMY MOVES AT MIDNIGHT. BE READY.
STO NEWA LLJAC KS ONSTONEW. ST ONEWA.
Then to encipher the message, find each letter down the leftmost column, and then locate the corresponding letter of the key phrase across the top row. Your substitution letter is found at the intersection of that row/column pair. So for the first letter, ‘T’, of our cipher, we find the row beginning with T, and the column below ‘S’ and find the intersection is letter ‘L’. The second letter ‘S’ intersects with the key letter ‘T’ at ‘A’, and so on. For our sample message, the ciphertext would be:
LAS NVIY XZEEU KL AVVGWTLP. TX FREZY.
To decipher the message, again repeat the key phrase as many times as needed to ‘cover’ the ciphertext (beginning afresh at the start of each new sentence). Now, taking each letter of the key phrase, find it across the top row of your table (identifying the column); then look down that column until you find the letter of the cipher, and then replace it with the leftmost letter of that row.
Write a program that will read in and process an unspecified number of ciphers. The first line of data in a set will have the number 1 (encipher) or 2 (decipher) to indicate which way you need to work the table. The second line in the set will be the key phrase, such as “Stonewall Jackson”. The third and final line of data in each set will be the plaintext or ciphertext message. All sentences will end with either a period or a question mark. Repeat processing until you run out of data sets. A negative number will indicate the end of the data. Ciphertext input will be fully capitalized; the key phrase and plaintext input may or may not be capitalized.
Example: for the data:
2
Stonewall Jackson
LAS NVIY XZEEU KL AVVGWTLP. TX FREZY.
1
BOBBY LEE
We move on Lynchburg. Supplies ready?
1
Damnyankees
Bring all horses you have to Gettysburg. Hurry.
-99
The output should be:
THE ARMY MOVES AT MIDNIGHT. BE READY.
XS NPTP SR MMODFMYVH. TIQQJTIW SSBEW?
ERUAE AYV LJJVEE LMU UKZI LR GQGRYFLYVY. KUDEW.
3. Letter Count
Given a set of three words on a line, determine which word has a particular letter occuring most often. Print the word, the letter, and the number of occurrences. In case of any kind of tie, e.g., two words with the same maximum number, or one word with the maximum number of occurrences on different letters (“mississippi”, below has 4 i's and 4 s's, and no other letter appears as often as 4 times), just print “tie” and go on. Repeat until there is no more data.
Example: for the data:
alfalfa engineering interconnection
mesopotamia mississippi conflagration
The output should be:
interconnection 4 n
tie
4. Aibohphobia
A palindrome is a word or phrase that is spelled the same, forward and backward, ignoring every character but letters.
Given a series of lines of text, determine which lines contain a palindrome (and only a palindrome).There is one potential palindrome per line. Repeat reading lines until there are no more lines to process.
Example: for the data:
Madam, I'm Adam.
Able was I 'ere I saw Elba.
A man, a plan, a canal, Suez!
Your output should be:
palindrome
palindrome
not a palindrome
5. Pyramids
In the ancient civilization of Egyptia, priests offer sacrifices to their gods on truncated pyramids.
Each pyramid has a square base, and is composed of two types of blocks: single blocks which are 1-cubit cubes, and double blocks which are the size of two single blocks. (If you must know, 1 cubit = 18 inches, but that won't help you with the problem.) To construct a pyramid, you must construct a solid square of blocks, and then build a smaller layer of blocks on top of the first layer, and continue building progressively smaller layers of blocks until you reach the desired number of layers. Each layer of the pyramid is one cubit per side smaller than the layer below it. Each layer is composed of double blocks and at most one single block.
You are to write a computer program which will indicate how many single blocks and how many double blocks are required for various pyramids. Each set of data will give the desired area for the top of the pyramid, and the height of the pyramid in cubits. Print a heading as indicated in the example problem, and one line of output for each set of data. Each line of output must give the area of the top layer, the height of the pyramid, the number of double blocks needed, and the number of single blocks needed. Continue reading and processing data until there are no more data to read.
Example: for the data:
1 1
9 4
16 3
Your output should be:
| Area | Height | No. of Double Blocks | No. of Single Blocks |
| 1 | 1 | 0 | 1 |
| 9 | 4 | 42 | 2 |
| 16 | 3 | 38 | 1 |