Problem Set 2001 ACM High School Programming Contest DO NOT LOOK AT THE PROBLEMS UNTIL YOU ARE TOLD TO DO SO BY THE CHIEF JUDGE!! REMEMBER: All input comes from the keyboard, and all output goes to the screen. In all problems, you should output ONLY what is specified. Do not output debugging information, and do not prompt for input. You should turn in an executable file called "programN", where N is the problem number. Do NOT turn in source code. Problem 1 - What Was That Number Again? --------------------------------------- You've just been hired on as a junior programmer for A-1 Computer Modems, Inc. (ACM). Your first job is to write a program that deals with phone numbers. Generally, today's modems expect that a phone number will be typed in as a sequence of digits (zero through nine), as shown in these examples: 8824295 2668228 3569377 But these days, it's pretty common for people to see phone numbers written with letters in place of some or all of the digits. For instance, the phone numbers above might be written like this: UTAHBY5 CONTACT FLOWERS Each letter represents a digit in the actual phone number. For example, the letters `A', `B', and `C' all represent the digit 2. The letters `D', `E', and `F' represent 3, and so on, as indicated on all modern telephone keypads. Your company wants its modems to understand phone numbers that contain both letters and digits. Unfortunately, the hardware inside the modems can only deal with digits. Therefore, your job at ACM is to write a phone number translation program. Write a program that reads SEVEN characters of input: each of these characters will be a digit (`0'--`9') or an upper-case letter (`A'--`Z'). These seven characters represent a phone number. Your program must translate this input into a phone number that contains ONLY DIGITS, according to the following rules. For each input character: + If the character is a DIGIT, output that digit. + If the character is an UPPER-CASE LETTER, output the digit that is represented by that letter, as indicated by the following table: ABC == 2 JKL == 5 TUV == 8 DEF == 3 MNO == 6 WXYZ == 9 GHI == 4 PQRS == 7 After printing the translated phone number, your program must print a newline character (`\n') and exit. Thus, your program will output a sequence of exactly seven digits, followed by a newline, and NOTHING ELSE. You may assume that the input to your program will be exactly seven alphanumeric characters, followed by a newline character. In the examples below, be sure to notice the difference between zero `0' and oh `O'. Example 1 Example 2 Example 3 -------------------- -------------------- ----------------------- Input: 5818224 Input: 4PIZZAS Input: COLLECT Output: 5818224 Output: 4749927 Output: 2655328 Example 4 Example 5 Example 6 -------------------- -------------------- ----------------------- Input: UTAHBY5 Input: PN65000 Input: 2GO4FUN Output: 8824295 Output: 7665000 Output: 2464386 Problem 2 - DNA Matcher ----------------------- Extracting genetic information from a cell is a demanding process. Each strand of DNA must be extracted, replicated, and analyzed one molecule at a time. The four molecules that make up DNA are: Cytosine Thymine Adenine Guanine These molecules are represented by their first letters: C, T, A, and G. When a portion of a DNA strand is sequenced, the result is a string of these letters. The string represents some sequence of molecules in the DNA strand. Here is an example DNA sequence representation: GTCAACTACTACCTAGCTAGACATAGCACTCTACCGACTACGCATACG The process of reading an entire DNA strand is the process of reading many partial sequences from the DNA and then merging these smaller sequences together to form one long sequence. One difficulty is discovering how the small sequences should be merged to form the entire DNA strand. Fortunately, the small DNA sequences overlap each other, thus giving us a clue as to how they fit together. You have been hired to write a program called Assessment of Complex Molecules (ACM) that takes two DNA sequences as input and determines if the two sequences overlap. For this problem, two strands overlap if at least five molecules at the START of one strand match the same number of molecules at the END of the other strand. For example, these two strands overlap: GTACTACCGG GACCAAGTACTA The first six characters of the first strand are the same as the last six characters of the second strand. If the second strand were placed before the first, they could be merged into a single strand like this: GACCAAGTACTACCGG These two strands do not overlap: GAGACTICAT GAGACTTICA ACM INPUT: Two strings representing DNA molecule sequences. The strings will contain the upper case letters G, A, T, and C, in any order. Each string will be followed by a newline. The strings will be at least six letters long and at most 50 characters long. ACM OUTPUT: If the two strings do not overlap by at least five letters, output the string "no overlap" followed by a newline character ('\n'). If the two strings do overlap by at least five letters, merge the strings and output the SHORTEST possible merged string, followed by a newline character. Be careful -- strings may overlap in different ways and by different amounts. In all our test cases, the answer will be unique. EXAMPLES ON NEXT PAGE... EXAMPLE 1: Input: CAGGATATATATA TATATATGG Output: CAGGATATATATATGG EXAMPLE 2: Input: GATTACA ATTACAGATTA Output: GATTACAGATTA EXAMPLE 3: Input: TAGAGGGACA CCGGACATAGA Output: no overlap Problem 3 - B.I.N.G.O. ---------------------- The Artificial Cybernetic Machine Co. (ACM) has just developed their newest game playing machine designed to entertain astronauts during their long voyages in outer space. The first game to be implemented is BINGO, and you have been asked to write the software. The standard BINGO card is a 5 by 5 grid containing integers between 1 and 75, with a FREE spot at the center that contains 0. The first column in the grid contains only integers between 1 and 15, the second column numbers are all between 16 and 30, the third are 31 to 45, the fourth 46-60, and the fifth 61-75. There are no duplicate numbers on a BINGO card. Before the game starts, each player is given a BINGO card. The game also has a "caller", who issues a list of all the integers between 1 and 75 in random order. As each number is called, players mark the appropriate squares on their cards. The middle square, the FREE square, is always marked. The winner of the game is the first person whose BINGO card has one of the following winning conditions: A. All five spots in a column are marked B. All five spots in a row are marked C. All the spots in either of the two diagonals are marked D. The four corner squares are all marked Your program will be given a BINGO card configuration and a stream of numbers between 1 and 75. It must output the number that generates the earliest possible winning condition. Good luck! INPUT Your input will consist of two parts. The first five lines will represent the BINGO card. Each line will be a row of five integers separated by spaces. The third number in the third line, the free square, will always contain the number 0. Next will come another seventy five integers, each on a separate line. These will always be the values between 1 and 75 in random order. OUTPUT Your output will be a single integer, followed by a newline character. This should be the input that gave you the earliest winning condition. In other words, the last number called before you would declare BINGO. EXAMPLE ON NEXT PAGE... EXAMPLE: Input: 10 22 41 53 71 2 20 40 50 66 14 26 0 52 69 15 29 37 51 65 6 17 35 55 64 9 14 17 52 72 69 35 26 63 1 12 [et cetera, until are numbers have been listed] Output: 26 Problem 4 - Egyptian Fractions ------------------------------ Although the ancient Egyptians were master engineers and builders, their mathematical expertise had some obvious flaws. One such was the inability of their system of numbers to handle what we view as simple rational fractions. All fractions in their system had a numerator of 1, as in: 1/2, 1/3, 1/4, 1/5, ... More complicated fractional numbers were represented as a sum of simple fractions. In the sum, each fraction had a UNIQUE denominator. For example: 3/5 = 1/2 + 1/10 (NOT 1/5 + 1/5 + 1/5) 5/7 = 1/2 + 1/5 + 1/70 Unfortunately for them, there was no computing device that would help them do mathematical calculations. Since you are the proud owner of an Advanced Calculating Machine (ACM), you would be able to help them out by writing a program that reads in a rational fraction and writes it out in Egyptian style as a sum of simple fractions. Your assignment for this problem is to do just that. You may assume that in the rational fractions provided, the numerator will be less than the denominator, each of those values will be less than 25, and the number of simple components in your output will be no more than 10. Input will be 2 integers on a single line, separated by blanks, with the numerator preceding the denominator. Your output should be presented in the form shown above, where the rational fraction is printed, followed by the representative Egyptian fractions separated by `+' signs (with a single space separating each of those components), followed by a single newline character. Examples: --------- Input: Input: 3 5 19 20 Output: Output: 3/5 = 1/2 + 1/10 19/20 = 1/2 + 1/3 + 1/9 + 1/180 Input: Input: 5 7 7 23 Output: Output: 5/7 = 1/2 + 1/5 + 1/70 7/23 = 1/4 + 1/19 + 1/583 + 1/1019084 Note that the answer may not be unique. Any valid output is correct. Problem 5 - Word Ladders ------------------------ _Amazing_Computing_Monthly_, a major computer industry magazine, has hired you write a monthly "word ladder" problem. You've decided to write a program to help you with this task. A "word ladder" is a game that begins with two words: a "start word" and an "end word" as shown in the examples below. Example 1 Example 2 ----------------------- ----------------------- lead <--- start word give <--- start word .... .... gold <--- end word take <--- end word ----------------------- ----------------------- The game is played by changing ONE letter at a time, each time making a new word. (Each change MUST result in an actual word.) The goal is to change the start word into the end word in the fewest number of steps. Put another way, you're making the shortest possible "ladder" from the start word to the end. In Example 1 above, the first step would be to replace one letter in "lead" to make another word. So, the second word in the ladder might be any of these: bead dead head leaf leap lend load read If you chose "bead", the next word in the ladder could be any of these: beak bean bend brad dead head lead read Obviously, some of these word choices are bad because they result in long ladders or run around in circles. There's no point in going from "lead" to "bead" to "dead", for instance, because you could go from "lead" to "dead" in just one step. Similarly, there's no point in going from "lead" to "bead" and then back to "lead". The goal of the game is to find a word ladder that is AS SHORT AS POSSIBLE. So, for the examples above, you might find the following ladders: Example 1 Example 2 ------------------------ ------------------------------------------- lead (In this case, give give give give load there is only gave live dive gave goad one shortest cave OR like OR dike OR save OR ... gold word ladder.) cake lake tike sake ------------------------ take take take take ------------------------------------------- As shown for Example 2, there might be more than one "shortest" word ladder. If so, then any of these "shortest" ladders is OK. You just need to find one! This is where your program comes in. Your program will solve word ladder problems like these, by finding the shortest possible word ladder solutions. NEXT PAGE... Write a program that reads the following input: + The "start word" for a word ladder. + The "end word" for a word ladder. + A number, indicating the number of words in the "dictionary." + The words in the dictionary. These are the words that your program can use to make word ladders. Each word and number will appear on a separate input line. Each word will contain exactly FOUR LOWER-CASE LETTERS. (No upper-case letters, and no apostrophes.) The number of words in the dictionary will never be more than thirty (30). You may assume that the start and end words will always appear in the dictionary. You may also assume that the start and end words will always be different from each other. Your program must output ONE of the SHORTEST word ladders from the start word to the end word. Every word in the ladder must be a word that appears in the dictionary. Remember that there may be more than one "shortest" ladder between the start word and the end word. Your program may output any one of these ladders. Each word in the ladder must be printed on a line by itself. The words must be printed in order (of course!). The first output word must be the start word and the last output word must be the end word. Your program may not print extra spaces or anything else around the words --- just print the words in order, each followed by a newline. Your program must exit after printing the ladder. If there is NO WAY to make a ladder from the start word to the end word, your program must output the words "no solution" (all lower case, no quotes), output a newline, and then exit. In any case, your program must either print a word ladder or "no solution" in NO MORE THAN FIVE SECONDS. Example 1 Example 2 Example 3 ------------ ------------ ------------ Input: Input: Input: life hero card raft zero hand 4 6 5 life aero band lift herb bard raft herd card rift hero hand Output: hire hard life zero Output: lift Output: card rift hero hard raft zero hand ------------ ------------ ------------ MORE EXAMPLES ON THE NEXT PAGE... Example 4 Example 5 Example 6 ------------ ------------ ------------------- Input: Input: Input: head more bank foot less loan 14 20 17 bead lass band bear lens bank beat less bean boar list bend boat lore bent boot lose land coat loss lean coot lost load foot mare loan head mess meal hear miss mean near mist sand neat more sank soar most send Output: nose sent head part tank bead pore toad beat port Output: boat pose no solution boot post ------------------- foot Output: If you add "bead" to ------------ more the dictionary, then lore there is exactly one lose shortest ladder: loss bank -> band -> bend less -> bead -> bean -> ------------ lean -> loan MORE EXAMPLES ON THE NEXT PAGE... Example 7 Example 8 Example 9 ------------ ------------ ---------------------------- Input: Input: Input: dish push hand wash pull wave 6 10 10 cash bulk band dash bull bane dish bush hand fish busk land wash mule lane wish mull sand Output: muse sane dish mush save dash pull wane wash push wave OR: Output: Output: OR: dish push hand hand wish bush band land wash busk bane lane ------------ bulk wane wane bull wave wave pull OR: OR: OR: hand hand push sand sand mush sane sane muse save wane mule wave wave mull ---------------------------- pull If you add "wand" to the ------------ dictionary, then there is exactly one shortest ladder: hand -> wand -> wane -> wave