Problem Set 2004 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. Problem 1 -- The ides of March is 'r' ------------------------------------- SOOTHSAYER. Caesar! CAESAR. Ha! Who calls? CASCA. Bid every noise be still. Peace yet again! CAESAR. Who is it in the press that calls on me? I hear a tongue, shriller than all the music, Cry "Caesar." Speak, Caesar is turn'd to hear. SOOTHSAYER. Beware the ides of March. CAESAR. What man is that? BRUTUS. A soothsayer you beware the ides of March. CAESAR. Set him before me let me see his face. CASSIUS. Fellow, come from the throng; look upon Caesar. CAESAR. What say'st thou to me now? Speak once again. SOOTHSAYER. Beware the ides of March. CAESAR. He is a dreamer; let us leave him. Pass. - "Julius Caesar", Shakespeare Julius had the misconception that "ides" means "middle", so he thought he might be able to find the soothsayer's real message by decoding the middle letters of all the messages he received during the month of March. He decided to commission the construction of an Automatic Centerpoint Machine (ACM) that he can run on all of his incoming email. The job falls to you. Time is of the utmost importance so that Julius can figure out what he needs to beware of. You are to write a program that takes a line of input, finds the middle character, and compares it to the character on the second line of input. If they are the same, your program will print "Beware!". If they are not the same, your program will print "All is clear.". Note that in a string with an even number of characters, we define the middle character to be the first of the two characters in the middle. For example '2' is the middle character in the string "1234". Input to your program will be two lines. The first line will contain a string no more than 100 characters in length, and the second line will contain a single non-blank character. Your program output must 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: March r Output: Beware! Example 2: --------- Input: March a Output: All is clear. Example 3: --------- Input: Shakespeare, William r Output: Beware! Problem 2 -- Roman Numerals --------------------------- Archaeologists have recently unearthed a cache of scrolls that were created during the time of Julius Caesar. They contain tables of numbers that are thought to be tax records maintained by the Archivus Centaurius Mathematicus (ACM), which was the Roman equivalent of the Internal Revenue Service (IRS). Of course, all the records are in Roman numbers, so translating them to our number system would be a very tedious task. The archaeologists have decided to scan them into the computer and hire you to write a program that converts Roman numbers to ours. There are seven different digits in the Roman number system. They are listed here, along with their corresponding value: M - 1000 D - 500 C - 100 L - 50 X - 10 V - 5 I - 1 To compose a Roman number, one simply appends as many of these digits as necessary to add up to the desired number. The digits are normally listed in order of decreasing value. Unfortunately, this resulted in some very long numbers, so the Romans added a special rule that the value of a digit would be subtracted, rather than added, to the total if the immediately following digit is larger. Thus: 1. An I preceding a V or an X becomes -1. 2. An X preceding an L or a C becomes -10. 3. A C preceding a D or an M becomes -100. Thus, IX represents 9 (-1 + 10), and CM represents 900 (-100 + 1000). By following these rules, no digit occurs more than three times in a row in any number between 1 and 3999. Input to your program will be a Roman number with no more than 15 digits. It will be a combination of the seven Roman digits that follows the rules described above. Your program is to calculate the value of that number and output its value, followed by a newline character ('\n'). If your program produces any other output it will be judged incorrect. EXAMPLES ------- Example 1: --------- Input: MDCLXVI Output: 1666 Example 2: --------- Input: IX Output: 9 Example 3: --------- Input: MMIV Output: 2004 Example 4: --------- Input: CDXXXVI Output: 436 Example 5 (number with largest possible value): ---------------------------------------------- Input: MMMCMXCIX Output: 3999 Example 6 (number with the most possible digits): ------------------------------------------------ Input: MMMDCCCLXXXVIII Output: 3888 Problem 3 --- The Answer is in the Stars ---------------------------------------- Before Julius Caesar was assassinated in 44 BC, a soothsayer named Spurinna warned him to "Beware the ides of March". HOW DID SPURINNA KNOW ABOUT THE IMPENDING ASSASSINATION? People have tried to answer this question for more than two thousand years, but with little success. The Astrological Code Meisters (ACM) think they have the answer. They say that Spurinna was able to foretell Caesar's future by studying patterns made by the stars that were visible in Rome at the time of his death. ACM scientists theorize that the secret information is encoded in the shapes formed by groups of four stars. They claim that these shapes have a special meaning for the future. It turns out that there are only six possibilities for the shape made by the lines connecting any four points: 1. Square - all four sides are the same length, all angles are right 2. Rectangle - opposite sides are the same length, all angles are right 3. Rhombus - all four sides are the same length, no right angles 4. Parallelogram - opposite sides are parallel, no right angles 5. Trapezoid - two sides are parallel, two sides are not 6. Tetragon - any general four-sided figure To completely understand the stars that were in the sky in March of 44 BC, they have to generate a huge number of shapes. There are just too many stars to do it by hand, so they ask you to help them by writing a shape recognizing program that calculates the shape made by any four points. Input to your program will be four lines of text. Each line will contain two integers: the X and Y coordinates of a point. You may assume that the input points are listed in order; i.e., if your program inputs A then B then C then D, then lines AB, BC, CD, and DA are the four sides of the tetragon. No three points will be on the same line. Your program must output a single word that describes the shape formed by the lines connecting the four points - Square, Rectangle, Rhombus, Parallelogram, Trapezoid, or Tetragon - followed by a newline character ('\n'). The program must output the most restrictive shape category; for example, a shape that is a Square is also a Rectangle, but the correct answer would be a Square because it is more restrictive. (Note that the above list is in order of decreasing restrictiveness.) EXAMPLES -------- Example 1: Exampmle 2: --------- ---------- Input: Input: 0 0 0 0 1 0 1 0 1 1 1 2 0 1 0 2 Output: Output: Square Rectangle Example 3: --------- Input: 0 0 2 -1 4 0 2 1 Output: Rhombus Example 4: --------- Input: 0 0 1 0 2 1 1 1 Output: Parallelogram Example 5: --------- Input: 4 0 2 3 0 3 0 0 Output: Trapezoid Example 6: --------- Input: 1 2 3 3 4 0 0 0 Output: Tetragon Example 7: --------- Input: 0 1 1 2 2 1 1 0 Output: Square Problem 4 - Roman Poetry ------------------------ When in Rome, do as the Romans. In order to impress Caesar and secure your place in the empire, you'll need to know how the Romans do poetry. The famous sonnet served Shakespeare well in England, but it won't get you too far with the newest styles in Rome. Everyone seems to have fallen in love with simple "word square" poems, i.e. the ones that read the same horizontally as they do vertically. Your task is to design an Acrostic Composition Maker (ACM) to assist you in making these bizarre poems. Because of the lack of literacy throughout the Empire, you decide to keep your poetry simple by only using 5-letter words. Your program will take five 5-letter words as input, one per line. All letters will be lower case, since the Romans didn't know about upper case in 44 BC. It will then determine if these words can be arranged into a Roman poem that reads the same horizontally and vertically. If so, your program should output the given words, one per line, in the correct order. Otherwise, it should output the following single line: Not possible Be careful not to output any extra information, and good luck in your quest for an enhanced imagination! EXAMPLES -------- Example 1: --------- Input: minor roman avoid nerdy olive Output: roman olive minor avoid nerdy Example 2: --------- Input: abcde abcde abcde abcde abcde Output: Not possible Example 3: --------- Input: homer march achoo rheum coupe Output: march achoo rheum coupe homer Problem 5 -- All Roads Lead Out Of Rome --------------------------------------- Defying history, Julius Caesar has heeded the soothsayer's advice to "Beware the ides of March" and is making himself scarce in Rome. He's going to wait for the heat from Brutus and his gang to pass by going to stay with a buddy in Byzantium (not Istanbul OR Constantinople). As Caesar's travel agent, it's your job to take him away from this terrible calamity (Abducto Calamitas Maximus (ACM)), and you'd better get him there as fast as you can, or you'll be going head-to-head with a lion in the Coliseum. You're to write a program that finds the fastest route from Rome to Byzantium. Input to your program be a list of the roads that connect pairs of cities in the Roman Empire. Output will be the route that Caesar should take to get to Byzantium as quickly as possible. The first line of input to your program will contain a single integer - the number of roads in the Empire. This will be followed by a list of roads, one per line. Each road specification consists of a space-separated list of a starting city, an ending city, and an integer indicating how many days it takes to travel the road. Note that you can, of course, travel a road in either direction; thus, if a road is listed as going from Rome to Venice, you could also take it from Venice to Rome. Your program should find the shortest route (measured in days) from Rome to Byzantium. It should then output a line containing the number of days the trip will take, followed by a list of the cities Caesar will pass through. The cities along the route should be listed one per line, in order, starting with Rome and ending with Byzantium. City names will be no longer than 20 characters, there will never be more than 100 roads, and there will never be more than 100 cities. There will always be a path between the starting and ending cities, and there will be only one shortest path (i.e., if the shortest trip possible is 10 days, then there will be only one path that takes 10 days). All roads will have a travel time of at least one day. EXAMPLES -------- Example 1 (simple path): ----------------------- Input: 4 Rome Venice 10 Venice Athens 20 Athens Thrace 2 Athens Byzantium 25 Output: 55 Rome Venice Athens Byzantium Example 2 (shortest trip in days may not have the fewest number of cities): -------------------------------------------------------------------------- Input: 5 Rome Istropolis 30 Istropolis Byzantium 40 Rome Verona 10 Verona Philippi 15 Philippi Byzantium 10 Output: 35 Rome Verona Philippi Byzantium Example 3 (more complex): ------------------------ Input: 12 Rome Gallia 4 Verona Senia 6 Mursa Senia 10 Rome Verona 6 Epidaurus Macedonia 10 Epidaurus Verona 4 Philippi Byzantium 15 Byzantium Macedonia 5 Senia Salona 2 Epidaurus Gallia 10 Mursa Macedonia 15 Philippi Senia 20 Output: 25 Rome Verona Epidaurus Macedonia Byzantium