Problem Set 2006 ACM High School Programming Contest DO NOT LOOK AT THE PROBLEMS UNTIL YOU ARE TOLD TO DO SO BY THE CHIEF JUDGE!! REMEMBERS: 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. Problem 1 - Where's the Rainbow? -------------------------------- It's well known that leprechauns hide their pots o' gold at the ends of rainbows. What's not commonly understood is that the gold is hidden at the point on the ground where the rainbow is green (like a shamrock, you know), which turns out to be the exact center of the spectrum of colors in the bow. That means you need to be able to figure out where each color touches the ground in order to find the treasure. Consider the rainbow shown in the following diagram: vbgyyooyygbv vibgyorrrrrroygbiv vibgyorr rroygbiv vibgyor roygbiv vibgyor roygbiv vibgyor roygbiv vibgyor roygbiv vibgyor roygbiv vibgyor roygbiv vibgyor roygbiv vibgyor roygbiv vibgyor roygbiv +----+----+----+----+----+----+----+----+----+----+----+--- 0 ^ ^ 4 51 This rainbow is said to have one endpoint at location 4 and one endpoint at location 51, measured in "rainbow color units". Each color is one unit wide at the point where the rainbow touches the ground. The color at each of the endpoints is violet, as indicated by the letter 'v'. If one wanted to know which color was at location 6, the answer would be 'blue', indicated by the 'b' at that location. You decide to increase your chances of finding the pot o' gold by designing an Automatic Color Measurer (ACM) program to calculate which color will be found at which location. Input to your ACM program will be three integers, all on one line. The first two numbers will correspond to the locations of the endpoints of a rainbow. The third number will be a location. The first two numbers will always differ by at least 14, so they will always define a valid rainbow. The program will compute the color that shines on the given location. Output from your program will be a single word. If the rainbow hits the location, the output will be the name of the color at that spot. If the rainbow is not shining on the location, your program will output "none". Colors that correspond to the letters in the diagram above are: violet indigo blue green yellow orange red If your program produces any other output, it will be judged incorrect. Example 1: --------- Input: 4 51 45 Output: red Example 2: --------- Input: 10 -10 0 Output: none Example 3: --------- Input: -1 -28 -3 Output: blue Example 4: --------- Input: 8 248 9 Output: indigo Example 5: --------- Input: 21 95 6 Output: none Problem 2 - Treasure Hunt ------------------------- Whilst romping through the foothills one foggy March morning, you stumble across a treasure map hidden under a rock. The map is an Additive Coordinate Map (ACM), which provides information about where to find the treasure and how to get there. You've been fooled by incorrect maps in the past, so before you go running all over everywhere trying to find a pot o' gold, you decide to write a program to help you test its validity. The ACM provides a location relative to where you found the map. This location is the number of paces upward or downward on the map (north/south) and the number of paces to the right or left (east/west). It also includes a list of directional segments, each of which contains a distance (in paces) and a direction to walk (north, south, east, or west). Your program will take as input the location of the treasure, the total number of directional segments, and a list of those segments. Input will be on multiple lines. The first line will be an ordered pair, separated by a space, which represents the destination that is trying to be reached. The first number in the pair is the number of paces east (if positive) or west (if negative). The second number in the pair is the number of paces north (if positive) or south (if negative). The second input line will be a simple integer, telling you how many segments will follow. After that, there will be as many lines as was indicated on the second line, each of which will be a number, a space, and then a direction. The direction will be one character - N,S,E,W. If it is "3 W", for example, you know that you should go 3 paces to the left on the cartesian coordinate system. You may assume that the map will never tell you go either negative or zero in a specified direction. You may also assume that all numbers will be integers. Your program will output whether or not the directional segments end up at the place where the map tells you the treasure is. If the various segments lead you to the final destination, your program must output "Treasure Found". If the segments don't lead to the treasure, it should output "Bad Map". If your program produces any other output, it will be judged incorrect. Example 1: ---------- Input: 5 5 3 5 E 2 N 3 N Output: Treasure Found Example 2: ---------- Input: -2 5 5 8 N 31 S 3 W 8 N 1 E Output: Bad Map Example 3: ---------- Input: 4 7 10 5 E 2 N 4 E 6 W 4 N 3 S 4 W 6 E 4 N 1 W Output: Treasure Found Problem 3 - Magic Squares ------------------------- Being interested in all things magic, the Leprechaun Society has commissioned a study of semi-magic and magic squares. Specifically, they would like an Automated Checker of Magic (ACM) program to determine the magical level of a square. This task has fallen onto you. Should you complete it successfully, the Leprechauns have promised to tell you the secret of how to locate the pot o' gold at the end of the rainbow. A square is a grid of integers where the number of rows is equal to the number of columns. In a semi-magic square the sums of the numbers in each row and each column are equal. A magic square is a semi-magic square where the sums of the numbers in the two diagonals is equal to those of the rows and columns. For example, the following square is a magic square. If one or both of the diagonals did not have a sum of 15, it would only be a semi-magic square. +---+---+---+ | 2 | 7 | 6 | -> 15 +---+---+---+ | 9 | 5 | 1 | -> 15 +---+---+---+ | 4 | 3 | 8 | -> 15 +---+---+---+ / | | | \ 15 V V V 15 15 15 15 Your task is to write a program that will read a square from standard input. It will then output whether the square is magic, semi-magic, or neither. The first line of input will contain a single integer, n, indicating the number of rows and columns in the square. Note that n is guaranteed to be less than 50. There will then be n lines of input, corresponding to the rows of a square. Each line contains n integers. Your program output must be a single line of text, exactly matching the examples below. If your program produces any other output, it will be judged incorrect. Example 1: --------- Input: 4 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 Output: This square is magic. Example 2: --------- Input: 3 1 2 3 2 3 1 3 1 2 Output: This square is semi-magic. Example 3: --------- Input: 5 17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 20 21 3 11 18 25 2 9 Output: This square is not magic. Problem 4 - Limerick Police --------------------------- On St. Patrick's Day, everyone tries to be Irish: wearing green, eating Irish food, and trying to write limericks. The problem is, anyone who's not Irish and tries to write a limerick invariably gets it wrong. The Association for Checking Makers of Limericks (ACM for short) has hired you to write a program to distinguish the true Irishmen and Irishwomen from the fakers by analyzing their poetry. A limerick is a five-line poem with the rhyme scheme "aabba". That is, the first, second, and fifth lines must rhyme with each other, and the third and fourth must rhyme. Two words rhyme if their final syllables have similar sounds. Because is it very hard to teach a computer how words actually sound, the ACM has specified that two words rhyme if their 'rhyming suffixes' are exactly the same. I.e., you will consider only the spelling, not the sound, of the suffix. The rhyming suffix of a word is defined to be the final non-terminal vowel, and all letters after it. A terminal vowel is one that appears as the last letter of a word. If the only vowel in a word is a terminal vowel, the entire word is considered to be the rhyming suffix. For this problem, 'y' is always considered a vowel, so the set of vowels is a,e,i,o,u, and y Here are some examples of rhyming suffixes: limerick: ick nantucket: et eire: ire wee: ee she: she Your program will take as input a supposed limerick. The input will be five lines. Each line will be no longer than 255 characters, and will contain at least two words, separated by spaces. Each word will contain at least one vowel. There will be no punctuation in or after the final word on each line. If the input has the correct rhyming scheme, your program must output the word "Aye". If not, it must output the word "Blarney". If your program produces any other output, it will be judged incorrect. Example 1: --------- Input: There was an old man who supposed That the street door was partially closed But some very large rats Ate his coats and his hats While that futile old gentleman dozed Output: Aye Example 2: --------- Input: There once was a man from Nantucket Who kept all his cash in a bucket But his daughter named Nan Ran away with a man And as for the bucket, Nantucket Output: Aye Example 3: --------- Input: There once was a coder so clever Whose code didn't work, however She got it all right Through the first hundred bytes But had a bug on the very last line Output: Blarney Problem 5 - Irish Football -------------------------- Based upon the way many people celebrate St. Patrick's Day, you might be thinking that there's not much to Ireland besides magic, rainbows, and pots of gold. But football (called soccer here in the States) is something the Irish take very seriously. To handle the upcoming Cup Championship the Football Association of Ireland sets up the Athletic Competition Management (ACM) system. The ACM assigns each football club a seed in the initial round of play. For example, in this ordering, Drogheda United would play the Bray Wanderers and Shelbourne would play St. Patrick's Athletic in round 1. For either Drogheda or Bray to play Shelbourne, it would have to be in round 2. ROUND 1 ROUND 2 ROUND 3 Drogheda United -----------------------| Bray Wanderers |-------------| -----------------------| | |------------- Shelbourne | -----------------------| | St. Patrick's Athletic |-------------| -----------------------| Some fans would like to know when their favorite team might play a particular rival, so the ACM has asked you to write a program to figure that out. Given any ordering of teams, the ACM needs your help in determining which round any two teams could play in. Input to your program will be the number of clubs (always a power of 2), a list of football clubs in the order they would appear in a tournament bracket like the one shown above, followed by the names of two clubs that could play each other. These will all be on separate lines. Output from your program will be a single integer - the number of the round that the two football clubs will play each other, assuming they both win all games necessary to reach that round. If your program produces any other output, it will be judged incorrect. Example 1: --------- Input: 2 Derry City Cork City Derry City Cork City Output: 1 Example 2: --------- Input: 4 Drogheda United Bray Wanderers Shelbourne St. Patrick's Athletic Drogheda United Shelbourne Output: 2 Example 3: --------- Input: 8 Waterford United Longford Town Sligo Rovers Bohemians Dublin City U.C.D. Shelbourne Bray Wanderers Longford Town U.C.D. Output: 3