************ Winter Championship Rules Changes and Problems *********
Here are the changes and clarifications to the rules. If you do not have a
copy of the complete rules (mailed to you yesterday), write to kolstad@bsdi.com
immediately.
First, it's the WINTER Championship:
USACO Winter Championship
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.
======================================================================
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
======================================================================
====================================================================
/\ Rob Kolstad Berkeley Software Design, Inc.
/\/ \ kolstad@bsdi.com 5575 Tech Center Dr. #110
/ \ \ 719-593-9445 Colorado Springs, CO 80919
====================================================================