The contest runs for 3 hours.

Read these problems very carefully.

• Only one solution may be submitted for each problem.
• Once submitted, a program cannot be altered.

Question 2:  Hot Stuff!.  You have some hot sauce, but you wish to determine just how hot .  So you take a small amount, dilute it with water, and test whether your (rather gullible) friend can detect the hot sauce in the diluted mixture.  If so, you take a small amount of the diluted mixture, further dilute that with water, and test again.  You continue in this manner until your friend can no longer detect the hot sauce.  First, we define the concentration of the hot sauce mixture as the ratio of the volume of hot sauce to the total volume of hot sauce and water (be sure to use the same units).  Next, we define the strength of a hot sauce as the natural logarithm of the inverse of the concentration of the most diluted hot sauce mixture in which the hot sauce is still detectable.  Your task:  read in a sequence of dilutions, where the final dilution results in your friend not being able to detect the hot sauce.  Print out the strength of the hot sauce.  Note that each dilution is represented by four whitespace-separated values:  volume_original  units_original  volume_water  units_water .  The two volumes are doubles, the two units are strings with possible values:  "cc", "ml", "liter", "tsp", "gallon".  Note that 1 cc is equal to 1 ml which is equal to 1/1000 liters.  Further, a teaspoon is about 0.005 liter, there are 48 teaspoons in a cup, and 16 cups in a gallon.  Finally, the input is terminated by EOF.

Sample Input:
    1.5 ml 1.37 gallon
    3.4 cc 345 liter
    6 tsp 18.1 liter

Note:  This means that you originally diluted 1.5 ml of hot sauce with 1.37 gallons of water in container A.  Your friend tasted hot sauce.  So you further diluted 3.4 cc of that solution in container A with 345 liters of water in container B.  Your friend again tasted hot sauce.  So you further diluted 6 teaspoons of that diluted solution in container B with 18.1 liters of water in container C.  Your friend finally could not taste hot sauce in that final mixture in container C.

Question 3:  A Nearly-40-Minute Drive.    Pierre is a senior, he has driving privileges, and he has a free period when he can legally go off campus.  So Pierre wants to hit the road!  He wants to drive for as much time as he can while always driving the speed limit and without driving the same road twice and while making it back within 40 minutes for his next class.  Your task:  read in a series of driving times between locations, then print out the duration for Pierre's optimal trip subject to the terms above.  Each entry is given, whitespace-delimited, by a start location, a dash, an end location, a colon, and a time (in minutes).  Location names are case-insensitive strings of alphabetics.  The input is terminated by either a blank line or by EOF, whichever comes first.  Note that Pierre starts and ends at "SA", and that all legs can be traversed in either direction.

Sample Input:
    SA-QV:5  Sewickley-QV:8 Sewickley-Osborne:4
    Osborne-QV:11 QV-BellAcres:12 Pittsburgh-Sewickley: 23
    Sewickley-SA: 4 SA-Pittsburgh:26
Sample Output:
    24
[ The trip, in either direction:  SA-QV-Osborne-Sewickley-SA. ]

Question 4:  "Analyticizing" Triangles.    Here we learn an important trick:  how to place a triangle given in side-side-side terms onto the Cartesian plane -- that is, given doubles s₁, s₂, and s₃, (where all s_i > 0 and the s_i are guaranteed to be sides of a valid triangle), we come up with three points that form a triangle with the given sides.  First, we simply place the first point at (0,0).  Simple!  Next, we orient the triangle so that one side lies on the x-axis, and we arbitrarily choose that side to be of distance s₁, so that the second point must be (s₁ ,0).  So now our problem is reduced to finding the point (x,y), where y is positive by convention, where the distance from (x,y) to (0,0) is s₂ and the distance from (x,y) to (s₁,0) is s₃.  The rest is up to you.  Your task:  read in three doubles s₁, s₂, and s₃, and print out the three points of the triangle described above which has sides with lengths s₁, s₂, and s₃ .  Each point must be printed out in the format "(x,y)" -- that is, left-paren, x value, comma, y value, right-paren, no extra spaces.  Print the points on a single line with two hyphens between each point, and order the points according to their x value, highest first, and in the event of a tie, then according to their y value, lowest first.

Question 5:  Lemur Letters.   Linda, a world-famous scholar on the philosophical beliefs of lemurs, is about to publish her life's work on the subject when something dreadful happens.  One of her more rambunctious subjects, Lenny Lemur, gets loose and hops madly all over her computer (while, peculiarly, humming the tune to George Michael's "Faith").  In the process, Lenny manages to randomly edit Linda's thesis, and save the changes!  At first, Linda is unfazed, as she has a backup copy on another computer.  Sadly, though, Lenny's friend Lisa Lemur is inspired by her beau's antics, and dances all over that computer, managing to randomly edit Linda's backup copy of her thesis.  Gadzooks!  Linda, in desperation, calls you, and says:  "Do something!"  Then she adds: "or you'll never graduate".  She is also your Lemurs 101 teacher, and she means business.  Your task:  attempt to recover Linda's work by reading in two blocks of text (Lenny's copy and Lisa's copy), each no more than 237 characters long, and each terminated by a blank line.  Then, print out the longest-common-substring of the two copies.  Your match must be case sensitive (so 'A' does not match 'a'), and must accept all legal ASCII characters, including newlines.  One catch:  at the end of each exactly-matching substring in either string, include the phrase "[CHECK]" in your output, so Linda knows where to look for changes.

Sample Input:
    Lemurs are JAJD and the astute observer will SLUMPF,
    and so I dzzz the Nobel Prize.

    Lemurs are philosphical BLDS and the astute ARKLE will agree,
    and so I deserve the JKDF Prize.

Sample Output:
    Lemurs are [CHECK] and the astute [CHECK] will [CHECK],
    and so I d[CHECK] the [CHECK] Prize.

Question 6:  Units Converter.   Here you write a units converter.  Your input is a series of lines, each containing a single unit conversion of the form:  value1 units1 = value2 units2.  The values are positive doubles, and the units are case-insensitive alphabetics, possibly followed by a caret (^) and an integer exponent.  Note that the units will have at most one unit (possibly with exponent) in the numerator, and at most one unit (again possibly with exponent) in the denominator.  These lines are followed by a single line of the same format, except one of the two values will be replaced with a question mark (?).  Your task is to output the missing value, or to output "UNKNOWN" if it cannot be computed from the given data.

Sample Input:
    1.5 ackles = 2 splarks
    4 ingors^3 = 7 kintchos^3
    5 splarks/ingors^2 = ? ackles/kintchos^2

Sample Output:
    2.582295

[ note that 2.582295 = 5 * (1.5 / 2) * (4^2/3 / 7^2/3) ]

Question 7:  Rational e.  As you likely know, the base of the natural logarithm, e (2.71828...), is transcendental, meaning (among other things) that it is irrational, and so cannot be expressed as the ratio of two integers.  Then again, it can be approximated by such a ratio.  Your task is to read in two whole numbers, lo and hi, where 0 < lo < hi, and to determine the ratio of integers, m/n, such that both m and n are in (lo,hi], and that this ratio most closely approximates e among all such ratios.  If there are two such pairs, resolve ties with the ratio with the lowest sum of m+n, and then if there is still a tie, use the smaller numerator.  Your output:  the numbers m and n formatted in a ratio, followed by an equals sign, then the ratio's exact value, followed by approximately-equals (~=) followed by "e + <difference>" or "e - <difference>" as appropriate.  For example, to show how to format your output (so the numbers 56 and 20 might not be legal output, but if there were, you would format them as such):  56/20 = 2.8 ~= e + 0.0817182