Usaco Mar08 Gold

Part of USACO Mar08

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

Problem 1: Land Acquisition [Paul Christiano, 2007]

Farmer John is considering buying more land for the farm and has
his eye on N (1 <= N <= 50,000) additional rectangular plots, each
with integer dimensions (1 <= width_i <= 1,000,000; 1 <= length_i
<= 1,000,000).

If FJ wants to buy a single piece of land, the cost is $1/square
unit, but savings are available for large purchases. He can buy
any number of plots of land for a price in dollars that is the width
of the widest plot times the length of the longest plot. Of course,
land plots cannot be rotated, i.e., if Farmer John buys a 3x5 plot
and a 5x3 plot in a group, he will pay 5x5=25.

FJ wants to grow his farm as much as possible and desires all the
plots of land. Being both clever and frugal, it dawns on him that
he can purchase the land in successive groups, cleverly minimizing
the total cost by grouping various plots that have advantageous
width or length values.

Given the number of plots for sale and the dimensions of each,
determine the minimum amount for which Farmer John can purchase all

PROBLEM NAME: acquire

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 describes plot i with two space-separated
        integers: width_i and length_i

SAMPLE INPUT (file acquire.in):

4
100 1
15 15
20 5
1 100

INPUT DETAILS:

There are four plots for sale with dimensions as shown.

OUTPUT FORMAT:

* Line 1: The minimum amount necessary to buy all the plots.

SAMPLE OUTPUT (file acquire.out):

500

OUTPUT DETAILS:

The first group contains a 100x1 plot and costs 100. The next group
contains a 1x100 plot and costs 100. The last group contains both the 20x5
plot and the 15x15 plot and costs 300. The total cost is 500, which is
minimal.

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

Problem 2: Cow Jogging [Alex Schwendner & Eric Price, 2006]

Bessie has taken heed of the evils of sloth and has decided to get
fit by jogging from the barn to the pond several times a week. She
doesn't want to work too hard, of course, so she only plans to jog
downhill to the pond and then amble back to the barn at her leisure.

Bessie also doesn't want to jog any too far either, so she generally
takes the shortest sequence of cow paths to get to the pond. Each
of the M (1 <= M <= 10,000) cow paths connects two pastures
conveniently numbered 1..N (1 <= N <= 1000). Even more conveniently,
the pastures are numbered such that if X>Y then the cow path from
pasture X to pasture Y runs downhill. Pasture N is the barn (at the
top of the hill) and pasture 1 is the pond (at the bottom).

Just a week into her regimen, Bessie has begun to tire of always
taking the same route to get to the pond. She would like to vary
her route by taking different cow paths on different days. Specifically,
Bessie would like to take exactly K (1 <= K <= 100) different routes
for variety. To avoid too much exertion, she wants these to be the
K shortest routes from the barn to the pond. Two routes are considered
different if they comprise different sequences of cow paths.

Help Bessie determine how strenuous her workout will be by determining
the lengths of each of the K shortest routes on the network of
pastures. You will be supplied a list of downhill cow paths from
X_i to Y_i along with the cow path's length: (X_i, Y_i, D_i) where
(1 <= Y_i < X_i; Y_i < X_i <= N). Cowpath i has length D_i (1 <=
D_i <= 1,000,000).

PROBLEM NAME: cowjog

INPUT FORMAT:

* Line 1: Three space-separated integers: N, M, and K

* Lines 2..M+1: Line i+1 describes a downhill cow path using three
        space-separated integers: X_i, Y_i, and D_i

SAMPLE INPUT (file cowjog.in):

5 8 7
5 4 1
5 3 1
5 2 1
5 1 1
4 3 4
3 1 1
3 2 1
2 1 1

OUTPUT FORMAT:

* Lines 1..K: Line i contains the length of the i-th shortest route or
        -1 if no such route exists. If a shortest route length occurs
        multiple times, be sure to list it multiple times in the
        output.

SAMPLE OUTPUT (file cowjog.out):

1
2
2
3
6
7
-1

OUTPUT DETAILS:

The routes are (5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),
(5-4-3-2-1).

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

Problem 3: Pearl Pairing [Catalin Tiseanu, 2007]

At Bessie's recent birthday party, she received N (2 <= N <= 100,000;
N%2 == 0) pearls, each painted one of C different colors (1 <= C
<= N).

Upon observing that the number of pearls N is always even, her
creative juices flowed and she decided to pair the pearls so that
each pair of pearls has two different colors.

Knowing that such a set of pairings is always possible for the
supplied testcases, help Bessie perform such a pairing. If there
are multiple ways of creating a pairing, any solution suffices.

PROBLEM NAME: ppairing

INPUT FORMAT:

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

* Lines 2..C + 1: Line i+1 tells the count of pearls with color i: C_i

SAMPLE INPUT (file ppairing.in):

8 3
2
2
4

INPUT DETAILS:

There are 8 pearls and 3 different colors. Two pearls have color I; two
have color II; four have color III.

OUTPUT FORMAT:

* Lines 1..N/2: Line i contains two integers a_i and b_i indicating
        that Bessie can pair two pearls with respective colors a_i and
        b_i.

SAMPLE OUTPUT (file ppairing.out):

1 3
1 3
2 3
3 2

OUTPUT DETAILS:

Bessie pairs each pearl of color III with one of color I and II.

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