USACO Winter Championship Wed-Mon, January 15-20, 1997 Results Report Introduction WHAT: The USA Computer Olympiad Winter Championship is a computer programming contest open to all pre-college students on the hs-computing@delos.com mailing list. Four or five problems are presented for solution. WHO: All pre-college students who are members of the hs-computing mailing list are eligible. This is an individual contest, not a team contest. WHEN: Problems will be posted to the mailing list between 0750 and 0800 a.m. US Mountain Standard Time (1450-1500 GMT) on Wednesday, January 15, 1997. All results are due by 0800 am US Mountain Standard Time (1500 GMT) Monday, January 20, 1997. Late solutions will not be accepted. The extended solution interval is required this time since several schools are conducting final examinations this week. WHERE: Students can work on problem solutions anywhere they wish, including school and home. HOW: Problems and rules will be posted to the hs-computing mailing list. Solutions must be written in Borland C/C++ or Turbo Pascal and must be returned via e-mail by the contest completion deadline along with answers to test data supplied with the problems. Choosing a different compiler than the Borland compilers will probably cause a solution to compile incorrectly on the Borland compilers on the judges' machines (which will result in no points scored for that problem). PRIZES: Winners will receive a handsome plaque, have their names immortalized on the USACO Web Pages, and be the subject of a press release. FEES: No entry fees are charged. RULES: * No consultation with people is allowed. * Submit questions to kolstad@bsdi.com who will try to fathom an appropriate answer for you (and post it to the hs-computing list, if appropriate). * Any amount of consultation with written materials (such as programming books) is allowed (but this doesn't mean you can ask someone to write an article on how to solve a problem, of course). * Spend no more than six hours solving problems. * Spend no more than three sessions solving problems (i.e., don't work one hour in a session, take a one hour break, work another hour, take another break, ...). * Submit source code for the problems and answers to the test data to the contest coordinators via e-mail to win97@delos.com (see below). * Solutions will be judged for correctness by running them against several (usually 10) different sets of data. Points are accrued for correct solutions. Some datasets for a problem will be worth more points than others. Solutions to some problems will be worth more points. Judging will be performed expeditiously but could easily take more than one week to complete. * Unless otherwise stated, no one solution can run longer than 10 seconds on the judge's computer (a medium speed Pentium). * Judges will not test all datasets against a program that crashes the computer for initial datasets. * Judges will not test all datasets against a program whose author submits erroneous solutions for the supplied test data. * Make sure your program has any special compiler options listed near its first line so the graders can get them right. * Decision of the judges is final. * Do not cheat; it's no fun for anyone. * Do not use inline assembler statements. * Don't submit programs that use data files that aren't supplied by the contest coordinators * Keep in mind that this is neither a `tricky input' nor a `tricky output' contest, in general. * All problems are intended to be straightforward; no problems are intended to have `tricks' in them. * If you find a problem with wording or an ambiguity, document your assumptions carefully and move on. Send e-mail; we'll reply if we can. NOTES: * We will mostly be using automated grading procedures. * The registration information at the front of the solution should be in precisely the same format as requested below. * Submitters of programs that attempt to thwart grading procedures will be forever disqualified from USACO contests. * Rob Kolstad is this contest's director. * During the contest, feel free to send questions (one per e-mail please!) to kolstad@bsdi.com. He will reply by e-mail when he is available. Questions judged to be germane to the entire hs-computing list will be summarized and posted there, also. Be sure to check your e-mail occasionally for contest updates, should there be any. For fairness, sometimes your question will be answered with a null answer (`sorry, I can't elaborate on that'). * Rob Kolstad judges Russ Cox's programs (at kolstad's site) before any other program is judged. * All programs read their input from file INPUT.DAT. * All programs write their output to the console. * DO NOT USE conio.h or its Pascal equivalent -- just write your answer straight to the console as if it were a teletype-style printer (using no screen manipulation or cursor positioning commands). ACKNOWLEDGMENTS: * Thanks to Hal Burch for problem and solution creation and testing. * Thanks to Don Piele for problem selection and creation. * Thanks in advance to Russ Cox for creating grading procedures and performing them for the contest entrants. ---------------------------------------------------------------------- No special registration form is required. Each problem solution has, within it, an entry form to be completed (see below). ---------------------------------------------------------------------- Submit your answers to problems via e-mail to win97@delos.com. Please send precisely one problem's solution (and test results) per e-mail (i.e., send three separate e-mails for three problems, etc.). Submit only one solution per problem. If you submit more than one solution, only the last one received will be graded. Every e-mail is acknowledged almost instantly by an automated mail reader. If you do not receive an acknowledgment, double-check the address. Note that some networks connect to the Internet only occasionally. Each solution e-mail submission should have the following format for the e-mail message. PLEASE SEND ASCII MESSAGES. DO NOT USE ATTACHMENTS, MIME ENCODING, fancy mail options, or anything else. The programs that read the mail are looking for just plain old ASCII. The submissions have special comments separating sections of the mail. These begin with three `#'s and are followed by an informational comment. Those comment lines are surrounded by a single blank line. Here is the format for submitting solutions so the grading programs can read them: ### Program ... [text of program in C or pascal; see below for header format] ... ### Test Data 1 ... [output of program for first run of test data] ... ### Test Data 2 ... [output of program for second run of test data] ... ### Test Data 3 ... [output of program for third run of test data] ... ### Test Data 4 ... [output of program for fourth run of test data] ... ### Test Data 5 ... [output of program for fifth run of test data] ... ### End NOTES: * Put comments precisely like these at top of each solution. * These are read by a program, do not change the format. * Be sure your email address and name are always spelled precisely the same way. We use the combination of email address and name as a unique identifier for you. * Data after `### End' is ignored (e.g., signatures) Here is the C/C++ header filled out for Rob Kolstad (my comments on far right). You should fill yours out for each problem with your own data (why not save it in a file on your computer for easy inclusion on later submissions): /* Compiler options: (any special options needed) Problem: 1 (single digit problem number) Name: Rob Kolstad (first name then last name) Email: kolstad@bsdi.com (email address) School: Norman High School Grade: 12 (grade in school, numerical: 7, 8, 9, ..., 13) Age: 18 Country: USA (three letters: CAN, COL, DEU, ROM, USA, etc.) */ Pascal users substitute { for /* and } for */. Here's a clarification for screen I/O. Don't even clear the screen. * DO NOT USE conio.h (in C) or `uses dos;' in Pascal -- just write your answer straight to the console as if it were a teletype-style printer (using no screen manipulation or cursor positioning commands). Here's a hint about testing your program: * Note that test data run by the judges will almost surely be more challenging than the test data supplied with each problem. Here's even broader clarification about how your program should get its input: * All programs read their input from file INPUT.DAT; do not specify a path name in your `open' statement. Watch your mailbox for a quick (automatically-generated) reply. If you don't see one fairly soon, send another e-mail to kolstad@bsdi.com explaining the situation (which problem you submitted, when you sent it). Good luck! Problems PROBLEM 1: Milk Containers [Piele, 1997] Farmer Paul has many milk containers of each of the following sizes: Can 10 gallons Pail 2 gallons Gallon Quart 1/4 gallon Pint 1/8 gallon Cup 1/16 gallon Write a program that will compute the number of ways farmer Paul can store X gallons of milk using any combination of these containers. For instance, farmer Paul can store one Quart four ways: 1: 1 quart 2: 2 pints 3: 1 pint + 2 cups 4: 4 cups One gallon can be stored 26 different ways. In all data, X is a positive integer number and 1 <= X gallons <= 50. Your program must compute the number of combinations for each separate input value in less than ten seconds (which means that your program might run as long as 10*n seconds for n input values). Your program should read values from the file INPUT.DAT one per line (and compute and print the number of combinations) until encountering a value of 0. ---------------------------------------------------------------------- SAMPLE INPUT (file INPUT.DAT): 5 10 0 SAMPLE OUTPUT: 5 1308 10 12477 TEST DATA SET #1: 1 5 10 15 39 0 PROBLEM 2: Super Roman Numerals [Kolstad, 1997] You've heard the story of Romans like Midas who had the `Golden Touch'. Midas was no fool and sold his gold for lots of money. The traditional Roman numerals proved inconvenient for expressing the value of his fortune, which ranged into the millions. He invented Super Roman Numerals. Super Roman Numerals follow the traditional rules for Roman numerals but have many more single-character values. Consider the traditional Roman numeral values, shown here with the single letter and the decimal number it represents: I 1 L 50 M 1000 V 5 C 100 X 10 D 500 As many as three of the same marks that represent 10^n may be placed consecutively: III is 3 CCC is 300 Marks that are 5 * 10^n are never used consecutively. Generally (with the exception of the next rule), marks are connected together and written in descending order: CCLXVIII = 100+100+50+10+1+1+1 = 263 Sometimes, a mark that represents 10^n is placed before a mark of one of the two next higher values (I before V or X; X before L or C; etc.). In this case, the value of the smaller mark is SUBTRACTED from the mark it precedes: IV = 4 IX = 9 XL= 40 But compound marks like XD, IC, and XM are not legal, since the smaller mark is too much smaller than the larger one. For XD (wrong for 490), one would use CDXC; for IC (wrong for 99), one would use XCIX; for XM (wrong for 990), one would use CMXC. Regrettably, in standard Roman numerals, numbers like 10,000 are represented as MMMMMMMMMM. In Super Roman Numerals, the table of marks is extended: I 1 L 50 M 1,000 R 50,000 U 1,000,000 N 50,000,000 V 5 C 100 P 5,000 S 100,000 B 5,000,000 Y 100,000,000 X 10 D 500 Q 10,000 T 500,000 W 10,000,000 Z 500,000,000 Numbers greater than 100 million are now easily expressible. Write a program that reads non-negative decimal numbers (one per line) from the file INPUT.DAT and prints the Super Roman Numeral equivalent. It is promised that the input data will require an answer that is representable using the given rules. Stop your program when the input number is a 0. ---------------------------------------------------------------------- SAMPLE INPUT (file INPUT.DAT): 18 1997 12345678 0 SAMPLE OUTPUT: 18 XVIII 1997 MCMXCVII 12345678 WUUSSSQRPDCLXXVIII TEST DATA SET #1: 18 1998 87654321 99999999 11111 0 PROBLEM 3: Babylonian Fractions [Traditional] In ancient Babylon, fractions were poorly understood. The strange way they represented fractions was as a sum of the minimal number of descending size terms of unique fractions with numerators of 1. Consider 2/3: 2/3 = 1/2 + 1/6 Write a program that reads pairs of numbers, one per line, from the file INPUT.DAT (stopping when either of the numbers is 0). It should print the Babylonian equivalent of the quotient of that pair of numbers formatted similarly to the examples below. Your program must compute the number of combinations for each separate input value in less than ten seconds (which means that your program might run as long as 10*n seconds for n input values). No solution will require a fraction whose denominator (bottom number) is greater than 10,000. ---------------------------------------------------------------------- SAMPLE INPUT (file INPUT.DAT): 2 3 3 4 1 2 0 0 SAMPLE OUTPUT (note the format): 2/3 = 1/2 + 1/6 3/4 = 1/2 + 1/4 1/2 = 1/2 TEST DATA SET #1: 2 3 3 4 1 2 79 1200 26 27 0 0 PROBLEM 4: Electrical Engineering Lab [Kolstad, 1997] A poorly funded high school in Elbonia wishes to construct a laboratory for Electrical Engineering students. They are so poor that they wish to build a software laboratory. They are concerned only with resistors. Resistors are electrical devices with two `terminals' (wires going into the resistor). Between these two terminals there is some amount of `resistance' measured in `ohms'. A single resistor is diagrammed (in the USA) somewhat like this: ----/\/\/\/---- 10 ohms There isn't a notion of an input or output terminal (wire) -- that all depends on which way electricity flows through the device. Furthermore, the device is perfectly symmetrical and bidirectional. Hooking two resistors `in series' is diagrammed like this: ----/\/\/\/------/\/\/\/---- 10 ohms 20 ohms These two resistors in series behave precisely a single resistor whose value is the sum of the two resistors (10+20 in this example): ----/\/\/\/---- 30 ohms Another way (not the only other way) to connect resistors is known as connecting them `in parallel' and is diagrammed like this: +----/\/\/\/----+ ----+ 10 ohms +------- +----/\/\/\/----+ 20 ohms The resistors' left terminals is connected together as are the right terminals. These two resistors in series behave precisely a single resistor whose value is calculated thusly (given two resistors whose values are R1 and R2 ohms): R1*R2 R = ------- tot R1+R2 ----/\/\/\/---- R ohms tot For the example above (10 and 20 ohms), the equivalent value for a pair resistors of 10 and 20 ohms connected in parallel is: R1*R2 10*20 200 R = ------- = ------ = ----- = 6.667 ohms tot R1+R2 10+20 30 Other configurations of resistors require more complex analysis and formulae. The Elbonians wish their software circuit simulator to be able to find equivalent resistances for sets of resistors connected in parallel and series (and combinations thereof, of course). For instance, they wish to calculate the equivalent resistance for a slightly more complex circuit that looks like this: +----/\/\/\/----+ ----+ 10 ohms +-------/\/\/\/---- +----/\/\/\/----+ 25 ohms 20 ohms This circuit's equivalent resistance is found by finding the parallel resistance and substituting an equivalent transistor ----/\/\/\/\/-------/\/\/\/---- 6.667 ohms 25 ohms then using the series formula to combine these two resistors: ----/\/\/\/\/---- 31.667 ohms More complex examples are easily designed: +----/\/\/\/----+ + 25 ohms + +----/\/\/\/----+ +----/\/\/\/----+ ----+ 10 ohms +-------/\/\/\/-----+ 22 ohms +----- +----/\/\/\/----+ 25 ohms +----/\/\/\/----+ + 20 ohms + 44 ohms +----/\/\/\/----+ 41 ohms This circuit is reduced pair-by-pair: maybe starting with the 25 and 10 ohm resistors in parallel, then the 41 and 20 in parallel, then those two equivalents in parallel, then the series combination of that equivalent with the 25 ohm resistor, and so on. Write a program that accepts a set of resistor connections described by the resistors' values and endpoints: 25 A B 100 B C with a zero ohm resistor designating the endpoints (and designating the end of the input): 0 A C Consider the previous example, now augmented with arbitrarily chosen SINGLE LETTER connection names: +----/\/\/\/----+ B A ----+ 10 ohms +-------/\/\/\/---- C +----/\/\/\/----+ 25 ohms 20 ohms whose input description is: 10 A B 20 A B 25 B C 0 A C Connect names can be upper or lower case -- and node upper-case `A' is different from node lower-case `a'. There will be no more than 500 resistors. Calculate your answers in floating point printing four decimal places of results. No formulae other than those presented here will be required (though this notation enables potential test data that is not solvable with these equations -- such test data will not be presented to your program). Read your input data from the file INPUT.DAT that has a single set of test data with the 0 ohm connection data as its last entry. Print your answer with four decimal places: 31.6667 ---------------------------------------------------------------------- SAMPLE INPUT (file INPUT.DAT): 10 A B 20 A B 25 B C 0 A C SAMPLE OUTPUT: 31.6667 TEST DATASET #1: 10 A B 20 A B 25 B C 0 A C TEST DATASET #2: 10 A B 10 B C 10 C D 10 D E 10 E F 10 F G 10 G H 10 H I 10 I J 10 J K 10 K L 0 A L TEST DATASET #3: 10 A B 10 B C 10 C D 10 D E 10 E F 10 F G 10 G H 10 H I 10 I J 10 J K 10 K L 10 A L 0 A L TEST DATASET #4: 10 A B 10 A B 10 A B 10 A B 0 A B TEST DATASET #5: 10 A B 10 B A 10 C D 10 D C 10 B C 10 A D 0 D A PROBLEM 5: Planetary Timekeeping [Kolstad, 1997 after Heinlein] Consider the Angusonian planetary system. It has N (1 <= N <= 9) planets circling the Angus sun in perfect circles. The system is so perfect that the planets trace circular, clockwise orbits that are all in the same plane. Let's call the planets P1, P2, ..., PN and the respective radius of their orbits R1, R2, ..., RN. Any planet with orbit of radius 100 mooters requires exactly one year to orbit the sun. Planets closer to the sun require less time to complete an orbit; planets farther from the sun require more time. In fact, the length of a planet's year is precisely: _ _ 2 | R_i | Yearlen =| ------- | years i |_ 100 _| So a planet whose orbit has radius 200 mooters would require (200/100)^2 = 2^2 = 4 years to complete an orbit. A planet whose orbit has radius 50 mooters would require (1/2)^2 = 0.25 years to complete an orbit. You will be given a set of planets. For each planet, you will be given the size of its radius (in mooters) and its initial position for this observation. Its initial position will be expressed in clock time. The clock time represents the location of the planet in its orbit. At the specified time, the `little hand' of an analog clock will point to the position of the planet in its orbit. By way of example, a planet located at 12:15 is 180 degrees around the sun from a planet positioned at 6:15. Given the positions and orbital radii of a set of planets, you are to determine the date (in years) when the planets will all line up at 3:00 (i.e., all planets will be positioned in their orbits at the 3:00 angle). Consider a single planet of orbital radius 100 mooters and located at 12:00. In 0.25 years, it will be at 3:00. Consider a pair of planets. Planet 1 has radius 100 mooters and is currently located at 9:00. Planet 2 has radius 200 mooters and is located at 1:30. After 0.5 years, they will both be aligned at 3:00. Your input file is named INPUT.DAT and includes a set of lines each with a radius and starting time. The last input line is all zeroes and is to be ignored. The input file looks like this for the previous example: 100 9 00 200 1 30 0 0 0 You are to calculate the number of years until the planets align at 3:00 and print the answer to four decimal places: 0.5000 It is guaranteed that the planets will eventually line up. The least common multiple of the planets' radii will be less than 2,000,000,000. NOTE: `Starting times' (initial angles) might have a floating point number for the minutes. A planet of radius 100 mooters might have an input line like this: 100 9 42.5 ---------------------------------------------------------------------- SAMPLE INPUT (file INPUT.DAT): 100 9 00 200 1 30 0 0 0 SAMPLE OUTPUT: 0.5000 TEST DATA SET #1: 100 9 00 200 1 30 0 0 0 TEST DATA SET #2: 100 9 00 200 7 30 0 0 0 TEST DATA SET #3: 100 9 00 200 1 30 300 10 20 0 0 0 TEST DATA SET #4: 100 12 00 200 8 15 300 9 20 75 8 20 0 0 0 TEST DATA SET #5: 5000 3 0 100 3 0 200 3 0 0 0 0