Sewickley Academy Programming Team
Programming Contest:  28-Jan-2002
David Kosbie (Faculty Advisor)
Sewickley Academy

Link to Programming Contests home page.

Team Questions (of varying difficulty)

Question 1:  Read in six floating point numbers -- m1, b1, m2, b2, m3, b3 -- representing the slopes and y-intercepts of three lines.  Output the area enclosed by the lines to the nearest integer (with rounding).  If there is no enclosed area (such as, say, when two of the lines are parallel), output 0.

Question 2:  The function arctan(x) = x - x3/3 + x5/5 - ... when |x| < 1. Use this function to repeatedly read in a floating point number x in the range (-1,1) and output arctan(x) to within 0.0001.  Note that your code may not use math.h or any other means of computing arctan(x) besides directly computing the given function.  Exit when x is not in the range (-1,1)..

Question 3:  Read in series of lines each containing 3 integers -- x, y, r -- representing a circle centered at (x,y) with radius r. These will be terminated by a blank line.  Output the radius of the smallest possible circle centered at (3,5) which circumscribes all the circles.

Question 4:  The sum of the first n integers raised to the kth power, which we will call Sk, can be written 1k + 2k + ... + nk and is always a polynomial of degree k+1, as in ak+1nk+1 + aknk + ... + a0n0.  Repeatedly read in two numbers -- k and j -- and output aj from the polynomial for Sk, halting when k is 0.

Question 5:  As you know, ASCII is a fixed-length 8-bit encoding of alphanumeric symbols where 'A' is 65, 'B' is 66, etc.  By contrast, a Huffman Code is a variable-length encoding, so that some characters might have only 1 or 2 bits to encode them, whereas others might require more.  The goal of a Huffman Code is to reduce the overall number of bits required to represent strings by using fewer bits to represent the most common characters.  To construct a Huffman Code, you begin with a count of the number of occurrences of each letter in a sample corpus.  You construct a tree by first imagining that each letter is the root of its own tree with no leaves, and then by continually merging the two trees with the smallest counts and placing their sum at the new root until there is only one tree remaining (place the smaller child to the left, and resolve ties randomly).  Finally, label left children with a 0 and right children with a 1.

The following tree results from the input:  a:45, b:13, c:12, d:16, e:9, f:5:

           (100)
           0/  \1
       (a:45)  (55)
              0/   \1
           (25)     (30)
          0/  \1    0/ \1
      (c:12)(b:13)(14) (d:16)
                  0/ \1
               (f:5) (e:9)
This produces the following Huffman Code:
Letter Huffman Code
a 0
b 101
c 100
d 111
e 1101
f 1100

Your task:  Read in a frequency table all on one line in the form letter:occurrences, as in:
    a:45 b:13 c:12 d:16 e:9 f:5

Next, repeatedly read in a line.  If that line is just 1's and 0's, it represents an encoded message, and you should print out the sequence of letters which maps to that encoding.  Conversely, if the line contains more than 1's and 0's, it represents a message to encode, and you should output its Huffman Encoding.  If the line contains the word "quit", you should quit.