USACO Fall Championship December 3-5, 1996 Results Report Introduction WHAT: The USA Computer Olympiad Fall Championship is a computer programming contest open to all pre-college students on the hs-computing@delos.com mailing list. Four 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 between 0750 and 0800 a.m. US Mountain Standard Time (1450-1500 GMT) on Tuesday, December 3, 1996. All results are due by 0800 am US Mountain Standard Time (1500 GMT) Thursday, December 5, 1996. WHERE: Students can work on problem solutions anywhere they wish, including school and home. HOW: Problems will be posted to the hs-computing mailing list. Solutions must be written in Borland C, C++, or Pascal and must be returned via e-mail by the contest completion deadline along with answers to test data supplied with the problems. 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. * Any amount of consultation with written materials is allowed (but this doesn't mean you can ask someone to write an article on how to solve a problem, of course). * Problems are intended to be solved in five hours * Spend no more than eight hours solving problems * Spend no more than two 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 to the contest coordinators via e-mail to fall96@delos.com (see below). * Submit answers to supplied test data to the contest coordinators via e-mail to fall96@delos.com (see below). * Solutions will be judged for correctness by running them against several (5-10) different datasets. Points are accrued for correct solutions. Some datasets might be worth more points than other solutions. Some problem solutions might be worth more points than other solutions. Judging could easily take a week. * Unless otherwise stated, no one solution can run longer than 15 seconds on the judge's computer (a medium speed Pentium). * Judges will not test all datasets against a program that crashes for easy 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 our 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. * Do not use data files not supplied by the contest coordinators. * Keep in mind that this is not a `tricky input' contest, in general. * All problems are intended to be straightforward; no problems are intended to have `tricks' in them. * If you find a problem or ambiguity, document your assumptions carefully and move on. Send e-mail; we'll reply if we can. Rob Kolstad is this contest's director. During the contest, feel free to send questions (one per e-mail please!) to him at 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. Thanks to Hal Burch for problem checking. ---------------------------------------------------------------------- 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 fall96@delos.com. Please send precisely one problem's solution per e-mail (i.e., send four separate e-mails if you solve all four problems). Submit only one solution per problem. If you submit more than one solution, only the last one received will be graded. Each solution should have the following in comments at the top of the program (example for C shown here; PASCAL users use PASCAL-style comments): /* * PROBLEM NUMBER n * * compiler options * * Name: * Email address: * School: * Grade in school: * Age: * Country: */ Then include the source program. After the source program, include the answers you get when running the program on the supplied test data sets. Please label each of the answer sets very clearly! If possible, just include all these pieces as text, no special MIME encoding or other mail formats; it will save the graders a lot of time. 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: The Errant Physicist [New Zealand Contest, 1989] The well-known physicist Alfred E Neuman is working on problems that involve multiplying polynomials of x and y. For example, he may need to calculate 8 3 5 3 (-x y + 9x - 1 + y) * (x y + 1 + x ) yielding the answer 13 2 11 8 6 5 5 2 3 3 -x y - x y + 8x y + 9x - x y + x y + 8x + x y - 1 + y Unfortunately, such problems are so trivial that the great man's mind keeps drifting off the job, and he gets the wrong answers. As a consequence, several nuclear warheads that he has designed have detonated prematurely, wiping out five major cities and a couple of rain forests. Write a program to perform such multiplications and save the world. The file of input data will contain pairs of lines, none longer than 80 characters. Stop your program when no more input is available. Each input line contains a polynomial written without spaces and without any explicit exponentiation operator. Exponents are positive non-zero unsigned integers. Coefficients are also integers, but may be negative. Both exponents and coefficients are less than or equal to 100 in magnitude. Each term contains at most one factor in x and one in y (i.e., at most one term of x to a power and likewise for y). For example, an input file for the above problem might be: -x8y+9x3-1+y x5y+1+x3 # Your program must multiply each pair of polynomials in the input and print each product on a pair of lines, the first line containing all the exponents, suitably positioned with respect to the rest of the information, which is in the line below. See the representation above. The following rules control the output format: * Terms in the output line must be sorted in decreasing order of powers of x and, for a given power of x, in increasing order of powers of y. * Factors of similar terms must be combined into a single term. For example, 2 3 2 3 2 3 42x y - 40x y should be shown as 2x y . * Terms with a zero coefficient must not be displayed. * Coefficients equal to 1 are not to printed, except for the case of a constant term equal to 1. * When the exponent is 1 (e.g., x to the first power), do not print the exponent * Binary pluses and minuses (that is the pluses and minuses connecting terms in the output) have a single blank column both before and after. * If the coefficient of the first output term is negative, it is preceded by a unary minus in the first column, with no intervening blank column. Otherwise, the coefficient itself begins in the first output column. * The output can be assumed to fit into a single line of at most 80 characters in length. * There are no blank lines printed between each pair of output lines. * There are no blank space on the end of input lines * There should be no blank spaces on the end of output lines. The above example conforms to all those requirements. Input file: INPUT.DAT Example input file: -x8y+9x3-1+y x5y+1+x3 Output to screen: the product of the polynomials, as described above Example output: 13 2 11 8 6 5 5 2 3 3 -x y - x y + 8x y + 9x - x y + x y + 8x + x y - 1 + y Self Test Data #1: -x8y+9x3-1+y x5y+1+x3 x+y x+y 45x4y3+-3x6 7y1++3y8-x+7x2 x+3x4--65x5 7y4-78y6+x3y3 x67y34+y67 x34+37y87x3+7 PROBLEM 2: Hamming Codes [Traditional, Kolstad] Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8), such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each of the other codewords. The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4): 0x554 = 0101 0101 0100 0x234 = 0010 0011 0100 Bit differences: xxx xx Since five bits were different, the Hamming distance is 5. Input file: INPUT.DAT Format: N, B, D on a single line Example input file: 16 7 3 Output to screen: N codewords, sorted, in decimal, ten per line. Example (but not only possible example): 0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127 Self Test Data #1: 16 7 3 Self Test Data #2: 8 6 3 Self Test Data #3: 8 5 2 Self Test Data #4: 16 8 3 PROBLEM 3: Palindromic Squares [Kolstad] Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome. Given a number base B (2 <= B <= 20 base 10) that has been read from the file INPUT.DAT, print all the integers N (1 <= N <= 100 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters 'A', 'B', and so on to represent the digits 10, 11, and so on. Print both the number and its square in base B. Input file: INPUT.DAT Example input file: 10 Output to screen: the table of integers and their palindromic squares Example output: 1 1 2 4 3 9 11 121 22 484 26 676 Self Test Data #1: 10 Self Test Data #2: 7 Self Test Data #3: 2 Self Test Data #4: 17 Self Test Data #5: 11 PROBLEM 4: Window Area [IV Balkan Olympiad] You've just be assigned the project of implemented a windowing interface. This windowing interface is fairly simple, and fortunately, you don't have to display the actual windows. There are 5 basic operations: 1) Create a window 2) Bring a window to the top 3) Put a window to the bottom 4) Destroy a window 5) Output what percentage of a window is visible (i.e., isn't covered by windows above it). In the input, the operations appear in the following format: Create window: w(I,x,y,X,Y) Bring window to top: t(I) Put window on bottom: b(I) Destroy window: d(I) Output percentage visible: s(I) The I is a unique identifier for each window, which is one character. The character can be any of 'a'..'z', 'A'..'Z', and '0'..'9'. No extra spaces will appear in the input. (x,y) and (X,Y) are opposite corners of the window. When a window is created, it is put `on top'. You can't create a window with an identifier that is already in use, but you can destroy a window and then create a new one with the identifier of the destroyed window. Coordinates will be positive integers, and all windows will be of non-zero area (x != X and y != Y). Partial credit will be given for solving the following problems: 1) 0 < x,y < 250 2) Able to solve up to 20 windows However, to receive full credit, the program must work for any number of windows (limited by the identifiers, of course), and x and y coordinates between 1 and 32767 inclusive. Input file: INPUT.DAT The input file will consist of a sequence of commands to your interpreter. They will be listed one per line. Terminate the program when no more input is available Input sample: w(a,10,132,20,12) w(b,8,76,124,15) s(a) Output to screen: Output lines only for the s() commands. Of course, there might be several s() commands so the output should be a sequence of percentages, one per line, stating the percentage of the windows that are visible. The percentages should be rounded to 3 decimal place. Sample Output: 49.167% Self Test Data #1: Input: w(a,10,132,20,12) w(b,8,76,124,15) s(a) Self Test Data #2: Input: w(a,1,1,21,21) w(b,2,2,12,12) w(c,5,5,8,8) s(a) s(c) s(b) Self Test Data #3: Input: w(a,164,16,78,102) w(9,110,96,41,225) w(d,60,89,141,158) s(a) b(d) s(a) t(a) s(9) s(d) Self Test Data #4: Input: w(a,10,132,20,12) w(c,12,120,22,16) w(b,8,16,124,15) t(a) w(d,18,93,102,20) b(b) b(a) s(a) s(b) s(c) s(d) d(d) d(c) s(a) s(b) Self Test Data #5: Input: w(a,4,452,182,338) w(b,435,340,56,467) w(c,474,4,343,486) w(d,243,204,188,118) w(e,493,173,301,68) w(f,96,306,57,433) w(g,362,344,313,105) w(h,432,277,319,94) s(a) s(b) s(c) s(d)