Problem Set 2005 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 - How Good is an Idea? -------------------------------- Albert Einstein was born on March 14, 1876, which means he would be 126 years old today. This wouldn't be a particularly interesting birthday year, except that 1905 has become known as the "miraculous year", when Einstein published three important papers describing ideas that have since influenced all physics research. Thus, 2005 really marks the 100th anniversary of modern physics. Not coincidentally, March 14th is Pi Day (3.14 - get it?). It turns out that these two facts are related. (But then again, everything is "relative" according to Dr. Einstein.) Is it totally coincidental that Einstein tended to enjoy a slice of pie while he was working? Absolutely not! Many know Einstein for his famous equation: E = mc^2. What not many people know, however, is that Einstein also discovered a corollary to that law which can be used to calculate the amount of creative energy produced by someone who has eaten a piece of pie. This is known as Albert's Creativity Measure (ACM). It works as follows: Whenever Einstein had a new idea, a "light bulb" lit up in his head. He measured the brilliance of that new idea in terms of how bright the light bulb was. He also measured the durability of an idea by how long the light bulb stayed on. He was able to estimate the brightness of the light, since he could see the light in his head, but he had to use his famous equation to predict how durable the idea would be. According to Einstein, the creative energy produced by a piece of pie was proportional to the mass of the pie he had eaten when the idea came to him times the square of the constant 'c'. For this corollary, however, 'c' is not the speed of light, but 31416. He defined the unit of durability to be the number of complete years the light in his head stayed on. This unit has become known as an "Einstein". For this problem, you are to write a program that inputs the mass of pie that had been eaten (in grams) and the brightness of the light (in watts). It then outputs the number of Einsteins for that idea. Input to your program will be two integers (mass, then brightness) on a single line, separated by a space. Your output must be a single integer followed by a newline ('\n') character. If your program produces any other output, it will be judged incorrect. To help you with your work, here is some information you will need to know: Energy is measured in joules; mc^2 produces joules of energy if m is the number of grams. Power is measured in watts, which is joules per second. Each year contains exactly 365 days (no leap years). Each day contains exactly 24 hours (no leap hours). Each hour contains exactly 60 minutes (no leap minutes). Each minute contains exactly 60 seconds (no leap seconds). HINT: To avoid overflow you should do your calculations using variables of type double. (Remember that your program is to output the number of whole years, hoever; any fractional part of a year should not be output.) (over) - 2 - Example 1: --------- Input: 200 60 Output: 104 Example 2: --------- Input: 1000 100 Output: 312 Example 3: --------- Input: 20 100 Output: 6 Example 4: --------- Input: 3000 200 Output: 469 Problem 2 - High Speed String Theory ------------------------------------ One of Einstein's great theories states that speed affects time and space. He theorized that the faster something moves, the shorter it becomes. Using this logic, the American Council of Measurement (ACM) has asked you to write a program that simulates what happens when you send text documents at high speeds - for if the Theory is true, it must apply to the papers Einstein wrote about Relativity, and it's up to you to prove it. For this problem, we will assume that traveling at high speeds does not affect consonants, numbers, or spaces, but that it causes vowels and punctuation marks to be removed. (You can assume that 'y' is always a vowel.) Hence, you are to write a program that takes a single line of input and outputs the same line with all vowels and punctuation removed. Input into your program will be one line of text no more than 255 characters in length. That means it will include letters, numbers, spaces, punctuation (like commas, periods, parentheses, et cetera), and possibly a reference at the end. Your program must output 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. Example 1: --------- Input: Albert Einstein Output: lbrt nstn Example 2: --------- Input (all on one line): The length to be discovered by the operation (b) we will call "the length of the (moving) rod in the stationary system." This we shall determine on the basis of our two principles, and we shall find that it differs from l. (1) Output (all on one line): Th lngth t b dscvrd b th prtn b w wll cll th lngth f th mvng rd n th sttnr sstm Ths w shll dtrmn n th bss f r tw prncpls nd w shll fnd tht t dffrs frm l 1 (over) - 2 - Example 3: --------- Input (all on one line): The results of the previous investigation lead to a very interesting conclusion, which is here to be deduced. (2) Output: Th rslts f th prvs nvstgtn ld t vr ntrstng cnclsn whch s hr t b ddcd 2 Footnotes: Two of the examples were taken from the following papers: (1) Einstein A. Zur Elektrodynamik bewegter Körper/On the Electrodynamics of Moving Bodies. Annalen der Physik. Leipzig 17 (1905) 891; (translation into English) H. Lorentz, A. Einshtein, H. Minkowsky, and H. Weyl The Principle of Relativity, Methuen, London, (1923) 35. (2) Einstein, A. Ist die Trägheit eines Körpers von seinem Energieinhalt abhängig?/Does the Inertia of a Body Depend upon its Energy Content? Annalen der Physik. Leipzig 18 (1905) 639; (translation into English) H. Lorentz, A. Einshtein, H. Minkowsky, and H. Weyl The Principle of Relativity, Methuen, London (1923) 67. Problem 3 - Birthday Pie ------------------------ For Einstein's birthday, he invited his two best friends to a party. Because his birthday is on Pi Day, instead of having a birthday cake, he decided to have a birthday pie. Einstein let each of his friends take a piece of the pie first, then he took a piece for himself. Being a mathematician, he was curious about the amount of pie that was left after his friends had taken their pieces. (Actually, he wanted to know exactly how much pie was left for him!) For this problem you are to write an Alternative (to) Cake Module (ACM) to help Dr. Einstein with his calculation. Your program will input two fractions representing how much pie the friends took. It will then output the fraction of the pie that is left, reduced as much as possible. Input to the program will be on two lines, one for each fraction. The input data will be in the form of two integers on each line, one representing the numerator and the other representing the denominator of the fraction. Your program output must be in the form "N/D", where N is the numerator of the remaining fraction of pie, and D is the denominator. Remember that the fraction must be reduced to its lowest form and be followed by a newline ('\n') character. No other output is allowed. If there is no pie left, just output 0. You may assume that each of the friends' pieces will always be greater than or equal to 0, and the sum of their two pieces will always be less than or equal to 1, so the solution will never be negative. Example 1: --------- Input: 1 4 1 4 Output: 1/2 Example 2: --------- Input: 1 4 2 3 Output: 1/12 (over) - 2 - Example 3: --------- Input: 33 99 66 99 Output: 0 Example 4: --------- Input: 2 17 5 23 Output: 260/391 Problem 4 - Going in Circles ---------------------------- Einstein observed that the circumference of one of his beloved pies is a circle. A circle has no start, and it has no end. He observed that even events can be circular. Events come full circle when you find yourself back where you started, which often happened when he was trying to come up with a new idea. Typically this circular thinking involves a chain of causes and effects. For example: Cause Effect ----- ------ You finish a pie. --> You decide you'd better buy more pie. You decide you'd better buy pie. --> You go to the store and get some. You get some pie. --> You put it in the cupboard. You have pie in the cupboard. --> You eat a piece every day. You eat a piece of pie every day. --> After six days it's all gone. You've now come full circle. In the example above, the effect of one event is the cause of the next event. In this problem, you are asked to write a program that can be used as an Automatic Cycle-checking Machine (ACM) which determines if a list of unordered cause-and-effect pairs are circular; i.e., if they can be organized into one complete circle. Your program will input a list of cause-and-effect pairs. It will output "Full circle" if these pairs can all be organized into a single circular chain of events. It will output "Nope" if the causes and effects cannot all be combined into a single circle. For this program each cause and each effect will be described by a single word. The first line of input to your program will be an integer that tells you how many pairs are to follow. The remaining input will be a list of pairs on separate lines. Each line will contain two words separated by a single space, with no leading or trailing spaces and no punctuation. The first word will be the cause, and the second will be the effect. Your output must exactly match the output in these examples (no extra formatting, text, or spaces allowed) with a newline ('\n') at the end. Example 1: --------- Input: 5 Wealth Spending Poverty Frugality Saving Wealth Frugality Saving Spending Poverty Output: Full circle (over) - 2 - Example 2: --------- Input: 6 Saving Spending Wealth Spending Poverty Frugality Saving Wealth Frugality Saving Spending Poverty Output: Nope Example 3: --------- Input: 6 Wealth Spending Poverty Frugality Poverty Misery Saving Wealth Frugality Saving Spending Poverty Output: Nope Example 4: --------- Input: 3 Wealth Spending Saving Wealth Spending Poverty Output: Nope Example 5: --------- Input: 1 Happiness Happiness Output: Full circle Problem 5 - Simplifying Einstein's Math --------------------------------------- Everyone knows that Einstein came up with the formula "E = mc^2", but not very many people know how strenuous the algebra was to get it to that simple form. For example, he may have started with something like: E = (mc - 5)(5 + c) + 5c(1 - m) + 25 Unfortunately, Einstein didn't have the advantage of a computer to help him with his calculations. He had to do everything by hand, which was quite a laborious task. You've decided to help today's physicists by designing an Algebraic Complexity Minimizer (ACM) that will handle part of their work. Your program will input two polynomials, calculate the product of the two, and then output the resulting polynomial in its simplest form. The input format for each polynomial will be an integer indicating the order of the polynomial (its highest exponent) on one line, followed by a line containing a list of all the coefficients of that polynomial. The list will start with the coefficient of the highest order term, and include an integer for each term all the way down to the constant. If a term is missing (i.e., its coefficient is zero), the list will contain a zero at that point. Hence, if the order is N, there will always be N+1 values in the list. The output format will be in the form that you are used to seeing when polynomials are written on a single line of text (like Einstein's famous equation above). Each term will be of the form Cx^E, where C is the coefficient and E is the exponent. Terms will be separated by either " + " or " - "; i.e., the plus or minus sign should have spaces before and after. Although this sounds straightforward, be careful to consider the special cases, for example: 7x^2 + -1x + 0 should be output as 7x^2 - x and -3x^3 + 2x^2 + 0x + 15 should be output as -3x^3 + 2x^2 + 15 Your output should be on a single line ending with a newline ('\n'). Remember not to output any extra information. (over) - 2 - Example 1: --------- Input: 1 1 2 1 1 -2 Output: x^2 - 4 Example 2: --------- Input: 2 1 -2 3 1 1 -5 Output: x^3 - 7x^2 + 13x - 15 Example 3: --------- Input: 5 -4 0 1 0 0 0 1 1 0 Output: -4x^6 + x^4