Usaco Nov07 Gold

Part of USACO Nov07

**********************************************************************
                           GOLD PROBLEMS
**********************************************************************
                  Three problems numbered 1 through 3
**********************************************************************

Problem 1: Telephone Wire [Jeffrey Wang, 2007]

Farmer John's cows are getting restless about their poor telephone
service; they want FJ to replace the old telephone wire with new,
more efficient wire. The new wiring will utilize N (2 <= N <=
100,000) already-installed telephone poles, each with some height_i
meters (1 <= height_i <= 100). The new wire will connect the tops
of each pair of adjacent poles and will incur a penalty cost C *
the two poles' height difference for each section of wire where the
poles are of different heights (1 <= C <= 100). The poles, of course,
are in a certain sequence and can not be moved.

Farmer John figures that if he makes some poles taller he can reduce
his penalties, though with some other additional cost. He can add
an integer X number of meters to a pole at a cost of X^2.

Help Farmer John determine the cheapest combination of growing pole
heights and connecting wire so that the cows can get their new and
improved service.

PROBLEM NAME: telewire

INPUT FORMAT:

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 contains a single integer: height_i

SAMPLE INPUT (file telewire.in):

5 2
2
3
5
1
4

INPUT DETAILS:

There are 5 telephone poles, and the vertical distance penalty is
$2/meter. The poles initially have heights of 2, 3, 5, 1, and 4,
respectively.

OUTPUT FORMAT:

* Line 1: The minimum total amount of money that it will cost Farmer
        John to attach the new telephone wire.

SAMPLE OUTPUT (file telewire.out):

15

OUTPUT DETAILS:

The best way is for Farmer John to raise the first pole by 1 unit and the
fourth pole by 2 units, making the heights (in order) 3, 3, 5, 3, and 4.
This costs $5. The remaining wiring will cost $2*(0+2+2+1) = $10, for a
total of $15.

**********************************************************************

Problem 2: Cow Relays [Erik Bernhardsson, 2003]

For their physical fitness program, N (2 <= N <= 1,000,000) cows
have decided to run a relay race using the T (2 <= T <= 100) cow
trails throughout the pasture.

Each trail connects two different intersections (1 <= I1_i <= 1,000;
1 <= I2_i <= 1,000), each of which is the termination for at least
two trails. The cows know the length_i of each trail (1 <= length_i
<= 1,000), the two intersections the trail connects, and they know
that no two intersections are directly connected by two different
trails. The trails form a structure known mathematically as a graph.

To run the relay, the N cows position themselves at various
intersections (some intersections might have more than one cow).
They must position themselves properly so that they can hand off
the baton cow-by-cow and end up at the proper finishing place.

Write a program to help position the cows. Find the shortest path
that connects the starting intersection (S) and the ending intersection
(E) and traverses exactly N cow trails.

PROBLEM NAME: relays

INPUT FORMAT:

* Line 1: Four space-separated integers: N, T, S, and E

* Lines 2..T+1: Line i+1 describes trail i with three space-separated
        integers: length_i, I1_i, and I2_i

SAMPLE INPUT (file relays.in):

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

OUTPUT FORMAT:

* Line 1: A single integer that is the shortest distance from
        intersection S to intersection E that traverses exactly N cow
        trails.

SAMPLE OUTPUT (file relays.out):

10

**********************************************************************

Problem 3: Sunscreen [Russ Cox, 2001]

To avoid unsightly burns while tanning, each of the C (1 <= C <=
2500) cows must cover her hide with sunscreen when they're at the
beach. Cow i has a minimum and maximum SPF rating (1 <= minSPF_i
<= 1,000; minSPF_i <= maxSPF_i <= 1,000) that will work. If the SPF
rating is too low, the cow suffers sunburn; if the SPF rating is
too high, the cow doesn't tan at all.

The cows have a picnic basket with L (1 <= L <= 2500) bottles of
sunscreen lotion, each bottle i with an SPF rating SPF_i (1 <= SPF_i
<= 1,000). Lotion bottle i can cover cover_i cows with lotion. A
cow may lotion from only one bottle.

What is the maximum number of cows that can protect themselves
while tanning given the available lotions?

PROBLEM NAME: tanning

INPUT FORMAT:

* Line 1: Two space-separated integers: C and L

* Lines 2..C+1: Line i describes cow i's lotion requires with two
        integers: minSPF_i and maxSPF_i

* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i
        with space-separated integers: SPF_i and cover_i

SAMPLE INPUT (file tanning.in):

3 2
3 10
2 5
1 5
6 2
4 1

INPUT DETAILS:

3 cows; 2 lotions.  Cows want SPF ratings of 3..10, 2..5, and 1..5. Lotions
available: 6 (for two cows), 4 (for 1 cow).  Cow 1 can use the SPF 6 lotion.
Either cow 2 or cow 3 can use the SPF 4 lotion.  Only 2 cows can be covered.

OUTPUT FORMAT:

A single line with an integer that is the maximum number of cows that
can be protected while tanning

SAMPLE OUTPUT (file tanning.out):

2

************************************************************************

Related Pages

NOV07 Bronze Problems
NOV07 Silver Problems

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License