Problem Set 2003 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" for C++ programs or "programN.class" for Java programs, where N is the problem number. Do NOT turn in source code. HINT: Unix allows you to redirect the contents of a file to the standard input stream. This may come in handy when testing your solutions to some of the problems, since there's a relatively large amount of text to type in. For example, to use a test case found in the file "example1.txt", type the following at the Unix prompt (for C++ programs): programN < example1.txt Or this command for Java programs: java programN.class < example1.txt Problem 1 -- Irish Names ------------------------ Recently, Active Children's Magazine (ACM) published an article about the St. Patrick's Day Parade in Salt Lake City. The parade is being organized by Mike O'Reily and Steve O'Malley. Unfortunately, the journalist thought their names were Mike Reily and Steve Malley, so there were errors in the article. The editor figured out a solution to the problem. He ordered you to write a computer program that inputs a line of text and outputs the same line with the characters O (upper case O) and ' (apostrophe) added before any upper case letter. Input to your program will be a single line of text. Your program output must also be a single line of text, as described above, ending in a newline ('\n') character. If your program produces any other output it will be judged incorrect. EXAMPLES -------- Example 1: --------- Input: Reily and Malley are organizing the parade. Output: O'Reily and O'Malley are organizing the parade. Example 2: --------- Input: You will complete the tasks for ACM. Output: O'You will complete the tasks for O'AO'CO'M. Problem 2 -- The Leprechaun's Treasure -------------------------------------- You catch a leprechaun named Andrew Conor McCabe (ACM for short), and demand that he give you his Treasure. Reluctantly he leads you to a big pot in the woods. Much to your dismay the pot is not full of gold, but just a bunch of Irish coins (punts and Irish cents). Before you can take the money Andrew must account for the loss in his financial records. The leprechauns record all their transactions using the old Irish monetary system. Andrew knows the exact amount of money in the pot, but must enter the equivalent amount in terms of the old Irish coins. In order to keep his accounting simple he wants to record the minimum number of each of the old coins (farthings, pennys, shillings, florins, crowns, and pounds) necessary to have the same value as the amount of money in the pot. You'd better help the Leprechaun, as his math is a bit rusty. Hurry and don't take your eyes off him, or he and his Treasure might disappear. In Ireland the standard unit of currency is the punt, which is similar to the dollar. Before the introduction of this decimal system in 1971, the Irish used a non-decimal currency where conversions were not straight forward. (It was kind of like using feet and inches rather than meters and centimeters) Your program will read two lines of input, each containing a single integer. The first number represents the number of punts in the pot, and the second number represents the number of Irish cents (1/100th of a punt) that are in the pot. The first number can range between 0 and 9999, and the second number between 0 and 99. An example of input to the program would be: 101 1 This represents 101 punts and 1 Irish cent. Note, either number may be zero, and a newline character will end each input line. You should read in this input, and convert it to a floating point number of punts. The pence is a unit in the Old Irish "non-decimal" system. Once you have the number of punts you can convert the quantity to pence using the following conversion. 1 punt = 240 pence. Pence can be converted into the other units in the old system using the following conversions. 1 farthing = .25 pence 1 penny = 1 pence 1 shilling = 12 pence 1 florin = 24 pence 1 crown = 60 pence 1 pound = 240 pence You should now compute the number of each of the coin types that will result in the smallest number of total coins, but still have the same value as the input amount. Your output must be a single line with the number of each type of coin, followed by the name of that type of coin, as follows: 101 pounds 0 crowns 0 florins 0 shillings 2 pennies 2 farthings where the numbers are replaced by the correct numbers for the given input. Each word and each number are separated by one space, and a new line character must end the line of output. Note, even if the amount of a type of coin is 0 or 1 the output must remain as above. HINT: Do not round any numbers until you calculate the number of farthings. At that point round up to the next highest farthing. Thus, 2.01 farthings would be output as "3 farthings". Even though 4 farthings is equal to one Penny, an answer of 4 farthings is acceptable where the number of farthings has been rounded up. (For example, 1 penny and 3.048 farthings should be output as 1 penny and 4 farthings, not 2 pennies). EXAMPLES ------- Example 1: --------- Input: 1 25 Output: 1 pounds 1 crowns 0 florins 0 shillings 0 pennies 0 farthings Example 2: --------- Input: 17 94 Output: 17 pounds 3 crowns 1 florins 1 shillings 9 pennies 3 farthings Example 3: --------- Input: 1 2 Output: 1 pounds 0 crowns 0 florins 0 shillings 4 pennies 4 farthings Problem 3 --- Picking out the Shamrocks --------------------------------------- The economy is down, and businesses are looking for ways to boost their revenues. American Circle Manufacturers (ACM) have decided that they will increase their income by producing drawings of shamrocks for St. Patrick's Day. The only problem is, the software that ACM uses doesn't allow them to see their designs before they get printed. To help ACM save money on printer ink, you've been asked to write a program that will determine whether or not a design constitutes a shamrock. A design consists of three circles, each defined by a center point and a radius. A design is considered to be a shamrock if both of the following conditions are met: 1. Each circle overlaps both of the other two circles. Circle A overlaps Circle B if there is at least one point in Circle A that is also in Circle B. This means that two circles that are tangent to one another are considered to overlap. ("Tangent" means that they have just one point in common.) 2. None of the circles are enclosed by another circle. Circle A is enclosed by Circle B if every point in Circle A is also within Circle B. This means that one circle can be tangent to another and still be enclosed in it. The input to your program will be nine lines of text, each group of lines describing one circle. A group of three lines will consist of three floating point numbers, one per line. The first two numbers represent the X and Y coordinates, respectively, of the center point. The third number represents the radius of the circle. Your program must compute whether or not the given circles form a shamrock and then print out either "yes" or "no" (without the quotes). Your program must print one of these two words exactly as shown, and then print out a newline character ('\n') and exit. If your program produces any other output, it will be judged incorrect. Reminder: The formula for determining the distance between the points (x1,y1) and (x2,y2) is as follows: d = sqrt( (x2-x1)^2 + (y2-y1)^2 ) EXAMPLES -------- Example 1 (no intersections): ---------------------------- Input: 10.0 20.0 10.0 30.0 40.0 5.0 50.0 50.0 5.0 Output: no Example 2 (all three intersect): ------------------------------- Input: 25.8 25.8 30.2 45.8 25.8 30.2 35.8 43.6 30.2 Output: yes Example 3 (one circle enclosed in another): ------------------------------------------ Input: 75.0 20.0 40.0 70.0 20.0 10.0 20.0 20.0 45.0 Output: no Example 4 (two circles are tangent): ----------------------------------- Input: 15.0 15.0 15.0 15.0 45.0 15.0 45.0 15.0 30.0 Output: yes Problem 4 - Find That Pot O' Gold! ---------------------------------- (lep-re-chaun, n; in Irish folklore, a small man with magical powers, often dressed in green, who works as a shoemaker and is believed to know where treasure is hidden) That little green man is at it again! But this time he's gone too far -- it's *your* pot o' gold that he's stolen and hidden somewhere in his kingdom. Your task is to design an Ancient Celtic Magnet (ACM) to assist you in your search for the leprechaun and the stolen money. To simplify your task, you decide your program should input the leprechaun's kingdom as a 2-dimensional array of characters. It will then calculate the start and end coordinates of the "magic word" that will show you where your gold is hidden. Be assured that no kingdom will be larger than 20 characters wide by 20 characters high. Input Format: number_of_rows (N) length_of_each_row row 0 row 1 ... row N-1 magic_word_to_find NOTE: The coordinate of the upper-left corner of the array is [0,0]. Words can be found in any direction, i.e. forward, backward, up, down, or diagonal. Your program should output one line only, namely the start and end coordinates of the word in the following format: [x1,y1] -> [x2,y2] Just in case the leprechaun plays a practical joke on you, you should output the following if the word isn't found: Not found Remember not to output any extra information, and good luck in your search for that pot o' gold! EXAMPLES -------- Example 1: --------- Input: 3 10 aaaaaaaaaa apotogolda aaaaaaaaaa potogold Output: [1,1] -> [8,1] Example 2: --------- Input: 7 7 aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa aaaaaaa leprechaun Output: Not found Example 3: --------- Input: 15 15 dtughrikbalboai cedirgamaripmel aorieznrcordoba ymtiggnirenorkf ichayenolleukeg unrcytdollarolh gadzakdobrindoa urekkrbximahksn ofadiidatesecei layirgnillihcsn inaraugnqboayce sonnrioleusltug ariohlhgtreaodn lkkwodnuopptloa asucrepikwanzal schilling Output: [13,9] -> [5,1] Problem 5 -- Let the River Flow Green! -------------------------------------- The citizens of Dublin need your help! For St. Patrick's Day, they want to dye the River Liffey green. What they need from you is the software to run their Aquatic Coloring Machine (ACM). You'll get a map of the river banks, and the location of one point that's in the river. You need to color every square that is connected to that point, without coloring any land (including islands). You must also go under bridges, but you will not color them. A point is defined as being "connected" to another point if it is adjacent either horizontally, vertically, or diagonally. The maps are rectangular arrays. Each point in the array contains one of the following characters: . Uncolored land or water x River banks - don't color B Bridge - don't color, but remember that water goes underneath G Green - starting point and places you've colored Input to your program will be one line with the number of rows in the map, one line with the length of each row in the map, and then the map itself. Your program will output the number of squares to be colored, including the start square, on one line, followed by the final map with all the connected water colored green. Each map will have no more than 100 rows and no more than 80 characters per row. EXAMPLES -------- Example 1 (simple): ------------------ Input: 8 10 ...x...... ..xx...... xxx.....xx ....G..xx. .....xxx.. ..xxxx.... xxx....... .......... Output: 31 ...xGGGGGG ..xxGGGGGG xxxGGGGGxx GGGGGGGxx. GGGGGxxx.. GGxxxx.... xxx....... .......... Example 2 (showing a diagonal connection): ----------------------------------------- Input: 10 15 ...x.........G. ..xx........... xx......xxxx... .......xx..xx.. .....xxx....xxx ..xxxx.......xx xxx...........x ............... ..........xxxx. ......xxxxx..xx Output: 52 GGGxGGGGGGGGGGG GGxxGGGGGGGGGGG xxGGGGGGxxxxGGG GGGGGGGxx..xxGG GGGGGxxx....xxx GGxxxx.......xx xxx...........x ............... ..........xxxx. ......xxxxx..xx Example 3 (showing a bridge): ---------------------------- Input: 10 15 ...x.........G. ..xx........... xxxBBBBBxxxx... .......xx..xx.. .....xxx....xxx ..xxxx.......xx xxx...........x ............... ..........xxxx. ......xxxxx..xx Output: 41 ...xGGGGGGGGGGG ..xxGGGGGGGGGGG xxxBBBBBxxxxGGG GGGGGGGxx..xxGG GGGGGxxx....xxx GGxxxx.......xx xxx...........x ............... ..........xxxx. ......xxxxx..xx Example 4 (showing a bridge with a diagonal connection underneath): ------------------------------------------------------------------ Input: 7 20 x....xx.......xx.xxx ......xxx......x..xx .......xxx.....x...x ......xxxxx..BBBxx.. .........xxxBB...xxG ..xxxx..xx........xx xxx..xxxx......xxxxx Output: 46 x....xxGGGGGGGxxGxxx ......xxxGGGGGGxGGxx .......xxxGGGGGxGGGx ......xxxxxGGBBBxxGG .........xxxBBGGGxxG ..xxxx..xxGGGGGGGGxx xxx..xxxxGGGGGGxxxxx