15-295 Reading 3 (Wednesday, February 2, 2005)
Assigned Readings
-
First edition: Sections 17.1-17.3
-
Second edition: Sections 16.1-16.3
Problem A: Piggy Banking
A standard automated teller machine dispenses cash in multiples of ten
dollars; for example, it can dispense $10 or $20, but not $15. The management
of the National Piggy Bank has decided to gain competitive edge by installing
Accuracy Cash Machines (ACM), which can dispense any
amount of dollars and cents. These machines use the minimal number of coins
and bills to dispense the required amount. For example, if a customer needs
five cents, she gets a nickel rather than five pennies; as another example,
if she needs $5.14, she gets a five-dollar bill, a dime, and four pennies.
The denominations of the available coins and bills are $0.01, $0.05, $0.10,
$0.25, $1, $5, $10, $20, $50, and $100. Your task is to write a program
that determines the minimal number of coins and bills for a given amount
of cash.
Input
The input is a list of cash amounts, one amount per line; each amount is
between 0.01 and 1000.00. We represent an amount by a real value with exactly
two digits after the decimal point. Note that we include these two digits
even if they are zeros; for instance, we represent five dollars as $5.00
rather than $5. The total number of lines in the input file is at most
1000; the last line is "0.00", which does not represent a cash amount.
Output
The output shows the minimal number of coins and bills for each amount;
each number is on a separate line.
Sample input
0.05
5.14
1000.00
0.00
Sample output
1
6
10
Problem B: Pony Tale
The Alpine Country of Mountaintops (ACM) consists
of n mountaintops connected by bridges; each bridge has a
weight limit, and safety regulations prohibit travelers to overload bridges.
Every bridge allows travel in both direction, and the inhabitants of ACM
never build two different bridges between the same two mountaintops, which
means that their country is a well-defined undirected graph. The people
of ACM had traditionally traveled by foot, but eventually
several entrepreneurs decided to introduce the United Pony Service (UPS)
for the delivery of heavy loads. Unfortunately, their initial experiments
showed that ponies are afraid of heights, and refuse to cross bridges.
Further investigation revealed that ponies cross green bridges, possibly
because the green reminds them of the grass, but would not go onto bridges
of other colors. The country did not have any green bridges, and the entrepreneurs
asked the king's permission to paint the bridges. The king liked the idea
of UPS, but wanted to preserve the old color of most
bridges, and he allowed painting of only n - 1 bridges. Furthermore,
he asked the entrepreneurs to select these bridges in such a way that a
two-pony carriage can travel between any two locations without overloading
any bridges. After analyzing the map of ACM, the entrepreneurs
determined that they can satisfy the king's condition only if the weight
of the carriage is within a specific value, denoted
W. That is,
if the weight is W or less, they can select n -1 bridges
in such a way that the carriage can travel between any two locations; if
it is greater than W, the king's problem in unsolvable. Your task
is to write a program that reproduces their manual computations and finds
W.
Input
The first line contains a positive integer n between 2 and 100,000,
which is the number of mountaintops. The other lines describe bridges between
mountaintops, one bridge per line. The description of a bridge includes
three positive integers, separated by single spaces, where the first two
integers are the respective mountaintops, and the third is the weight limit;
for example, the line "2 4 100" describes a bridge between mountaintops
2 and 4, with weight limit 100. The mountaintop numbers are between 1 and
n,
and the weight limits are between 1 and 108. The last line is
"0 0 0", which does not represent a bridge.
Output
If the graph is not connected, the output is the string "Disconnected
graph". If the graph is connected, he output is a single integer W,
which is the maximal carriage weight that allows the entrepreneurs to satisfy
the king's condition.
Sample input
4
1 2 10
2 3 20
3 4 30
4 1 60
0 0 0
Sample output
20
Problem C: Rooms for a contest
The Association for Computing Machinery (ACM) has
decided to hold a regional programming contest at Carnegie Mellon. The
contest includes several events, where each event is specified by its start
time and end time, in the same way as in the activity-selection problem.
If two events overlap, they require separate rooms; for instance, the events
with time intervals [1..4] and [4..8] can be in the same room, whereas
[1..4] and [3..7] require separate rooms. Since the room reservation involves
painful negotiations with the university administration, the contest organizers
plan to use as few rooms as possible. Your task is to write a program that
determines the minimal number of rooms required for scheduling all given
events.
Input
The input is a list of events, one per line; the description of an event
includes two positive integers, separated by a single space. The first
integer is a start time, and the second is a finish time, which is strictly
greater than the start time. The time values are between 1 and 108,
and the total number of activities is between 1 and 100,000; the last line
is "0 0", which does not represent an event.
Output
The output is a single integer number, which represents the minimal required
number of rooms.
Example input
1 4
4 5
3 6
5 7
5 8
7 9
0 0
Example output
3