Usaco Dec07 Silver

Part of USACO Dec07

**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Charm Bracelet [Kolstad/Cox, 2006]

Bessie has gone to the mall's jewelry store and spies a charm
bracelet. Of course, she'd like to fill it with the best charms
possible from the N (1 <= N <= 3,402) available charms. Each charm
i in the supplied list has a weight W_i (1 <= W_i <= 400), a
'desirability' factor D_i (1 <= D_i <= 100), and can be used at
most once.  Bessie can only support a charm bracelet whose weight
is no more than M (1 <= M <= 12,880).

Given that weight limit as a constraint and a list of the charms
with their weights and desirability rating, deduce the maximum
possible sum of ratings.

PROBLEM NAME: charm

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 describes charm i with two space-separated
        integers: W_i and D_i

SAMPLE INPUT (file charm.in):

4 6
1 4
2 6
3 12
2 7

INPUT DETAILS:

Four potential charms; maximum weight 6

OUTPUT FORMAT:

* Line 1: A single integer that is the greatest sum of charm
        desirabilities that can be achieved given the weight
        constraints

SAMPLE OUTPUT (file charm.out):

23

OUTPUT DETAILS:

Without the second possible charm, the 4+12+7=23 is the highest
value for weight 1+2+3 <= 6

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

Problem 7: Building Roads  [Richard Ho, 2007]

Farmer John had just acquired several new farms! He wants to connect
the farms with roads so that he can travel from any farm to any
other farm via a sequence of roads; roads already connect some of
the farms.

Each of the N (1 <= N <= 1,000) farms (conveniently numbered 1..N)
is represented by a position (X_i, Y_i) on the plane (0 <= X_i <=
1,000,000; 0 <= Y_i <= 1,000,000).  Given the preexisting M roads
(1 <= M <= 1,000) as pairs of connected farms, help Farmer John
determine the smallest length of additional roads he must build to
connect all his farms.

PROBLEM NAME: roads

INPUT FORMAT:

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

* Lines 2..N+1: Two space-separated integers: X_i and Y_i

* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating
        that there is already a road connecting the farm i and farm j.

SAMPLE INPUT (file roads.in):

4 1
1 1
3 1
2 3
4 3
1 4

INPUT DETAILS:

Four farms at locations (1,1), (3,1), (2,3), and (4,3). Farms 1 and 4 are
connected by a road.

OUTPUT FORMAT:

* Line 1: Smallest length of additional roads required to connect all
        farms, printed without rounding to two decimal places. Be sure
        to calculate distances as 64-bit floating point numbers.

SAMPLE OUTPUT (file roads.out):

4.00

OUTPUT DETAILS:

Connect farms 1 and 2 with a road that is 2.00 units long, then connect
farms 3 and 4 with a road that is 2.00 units long. This is the best we can
do, and gives us a total of 4.00 unit lengths.

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

Problem 8: Mud Puddles [Jeffrey Wang, 2007]

Farmer John is leaving his house promptly at 6 AM for his daily
milking of Bessie. However, the previous evening saw a heavy rain,
and the fields are quite muddy. FJ starts at the point (0, 0) in
the coordinate plane and heads toward Bessie who is located at (X,
Y) (-500 <= X <= 500; -500 <= Y <= 500). He can see all N (1 <= N
<= 10,000) puddles of mud, located at points (A_i, B_i) (-500 <= A_i
<= 500; -500 <= B_i <= 500) on the field. Each puddle occupies only
the point it is on.

Having just bought new boots, Farmer John absolutely does not want
to dirty them by stepping in a puddle, but he also wants to get to
Bessie as quickly as possible. He's already late because he had to
count all the puddles. If Farmer John can only travel parallel to
the axes and turn at points with integer coordinates, what is the
shortest distance he must travel to reach Bessie and keep his boots
clean? There will always be a path without mud that Farmer John can
take to reach Bessie.

PROBLEM NAME: mud

INPUT FORMAT:

* Line 1: Three space-separate integers: X, Y, and N.

* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i
        and B_i

SAMPLE INPUT (file mud.in):

1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2

INPUT DETAILS:

Bessie is at (1, 2). Farmer John sees 7 mud puddles, located at (0,
2); (-1, 3); (3, 1); (1, 1); (4, 2); (-1, 1) and (2, 2). Pictorially:

   4 . . . . . . . . 
   3 . M . . . . . . 
Y  2 . . M B M . M . 
   1 . M . M . M . . 
   0 . . * . . . . . 
  -1 . . . . . . . . 
    -2-1 0 1 2 3 4 5 
           X

OUTPUT FORMAT:

* Line 1: The minimum distance that Farmer John has to travel to reach
        Bessie without stepping in mud.

SAMPLE OUTPUT (file mud.out):

11

OUTPUT DETAILS:

The best path for Farmer John is (0, 0); (-1, 0); (-2, 0); (-2, 1);
(-2, 2); (-2, 3); (-2, 4); (-1, 4); (0, 4); (0, 3); (1, 3); and (1,
2), finally reaching Bessie.

   4 ******* . . . . 
   3 * M . * . . . . 
Y  2 * . M B M . M . 
   1 * M . M . M . . 
   0 ***** . . . . . 
  -1 . . . . . . . . 
    -2-1 0 1 2 3 4 5 

           X

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