Usaco Oct08 Gold

Part of USACO Oct08

**********************************************************************
                           GOLD PROBLEMS
**********************************************************************
                  Six problems numbered 1 through 6
**********************************************************************

Problem 1: Bovine Bones [Rob Kolstad, 2008]

Bessie loves board games and role-playing games so she persuaded
Farmer John to drive her to the hobby shop where she purchased three
dice for rolling. These fair dice have S1, S2, and S3 sides
respectively (2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40).

Bessie rolls and rolls and rolls trying to figure out which three-dice
sum appears most often.

Given the number of sides on each of the three dice, determine which
three-dice sum appears most frequently. If more than one sum can
appear most frequently, report the smallest such sum.

POINTS: 70

PROBLEM NAME: bones

INPUT FORMAT:

* Line 1: Three space-separated integers: S1, S2, and S3

SAMPLE INPUT (file bones.in):

3 2 3

OUTPUT FORMAT:

* Line 1: The smallest integer sum that appears most frequently when
        the dice are rolled in every possible combination.

SAMPLE OUTPUT (file bones.out):

5

OUTPUT DETAILS:

Here are all the possible outcomes.
1 1 1 -> 3  1 2 1 -> 4  2 1 1 -> 4  2 2 1 -> 5  3 1 1 -> 5  3 2 1 -> 6
1 1 2 -> 4  1 2 2 -> 5  2 1 2 -> 5  2 2 2 -> 6  3 1 2 -> 6  3 2 2 -> 7
1 1 3 -> 5  1 2 3 -> 6  2 1 3 -> 6  2 2 3 -> 7  3 1 3 -> 7  3 2 3 -> 8

Both 5 and 6 appear most frequently (five times each), so 5 is the answer.

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

Problem 2: Building A Fence [Jeffrey Wang, 2007]

Industrious Farmer John wants a build a four-sided fence to enclose
the cows. He has one plank of wood of integer length N (4 <= N <=
2,500) that he wants to cut at three points to make four integer-length
pieces.

The four pieces can be of any positive integer length as long as
Farmer John can form a quadrilateral fence with them. How many
different ways can he cut the plank of wood so that he can make a
complete fence?

NOTES:

  * Two ways of cutting are different if one has a cut at a
    spot that the other doesn't. Don't worry about eliminating
    symmetries or other complexities like that.

  * Do make sure, though, that the fence has greater than 0 area.

  * Rejoice that the answer will always fit into a signed 32-bit
    integer.

POINTS: 250

PROBLEM NAME: quad

INPUT FORMAT:

* Line 1: A single integer: N

SAMPLE INPUT (file quad.in):

6

INPUT DETAILS:

The plank of wood has length 6.

OUTPUT FORMAT:

* Line 1: A single integer that is the number of ways that Farmer John
        can cut the plank of wood into four pieces such that they form
        a valid quadrilateral.

SAMPLE OUTPUT (file quad.out):

6

OUTPUT DETAILS:

Farmer John can cut the plank 10 ways into four pieces: (1, 1, 1,
3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3,
1, 1); (2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1); or (3, 1, 1, 1).
Four of these -- (1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), and (3,
1, 1, 1) -- cannot be used to form a quadrilateral, though.

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

Problem 3: Watering Hole [Paul Christiano, 2007]

Farmer John has decided to bring water to his N (1 <= N <= 300)
pastures which are conveniently numbered 1..N. He may bring water
to a pasture either by building a well in that pasture or connecting
the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000).
Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <=
100,000; P_ij = P_ji; P_ii=0).

Determine the minimum amount Farmer John will have to pay to water
all of his pastures.

POINTS: 400

PROBLEM NAME: water

INPUT FORMAT:

* Line 1: A single integer: N

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

* Lines N+2..2N+1: Line N+1+i contains N space-separated integers; the
        j-th integer is P_ij

SAMPLE INPUT (file water.in):

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

INPUT DETAILS:

There are four pastures. It costs 5 to build a well in pasture 1,
4 in pastures 2 and 3, 3 in pasture 4. Pipes cost 2, 3, and 4
depending on which pastures they connect.

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the minimum cost
        of providing all the pastures with water.

SAMPLE OUTPUT (file water.out):

9

OUTPUT DETAILS:

Farmer John may build a well in the fourth pasture and connect each pasture 
to the first, which costs 3 + 2 + 2 + 2 = 9.

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

Problem 4: Pasture Walking [Neal Wu, 2007]

The N cows (2 <= N <= 1,000) conveniently numbered 1..N are grazing
among the N pastures also conveniently numbered 1..N. Most conveniently
of all, cow i is grazing in pasture i.

Some pairs of pastures are connected by one of N-1 bidirectional
walkways that the cows can traverse. Walkway i connects pastures
A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N) and has a length of L_i
(1 <= L_i <= 10,000).

The walkways are set up in such a way that between any two distinct
pastures, there is exactly one path of walkways that travels between
them. Thus, the walkways form a tree.

The cows are very social and wish to visit each other often. Ever
in a hurry, they want you to help them schedule their visits by
computing the lengths of the paths between Q (1 <= Q <= 1,000) pairs
of pastures (each pair given as a query p1,p2 (1 <= p1 <= N; 1 <=
p2 <= N).

POINTS: 200

PROBLEM NAME: pwalk

INPUT FORMAT:

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

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

* Lines N+1..N+Q: Each line contains two space-separated integers
        representing two distinct pastures between which the cows wish
        to travel: p1 and p2

SAMPLE INPUT (file pwalk.in):

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

OUTPUT FORMAT:

* Lines 1..Q: Line i contains the length of the path between the two
        pastures in query i.

SAMPLE OUTPUT (file pwalk.out):

2
7

OUTPUT DETAILS:

Query 1: The walkway between pastures 1 and 2 has length 2.
Query 2: Travel through the walkway between pastures 3 and 4, then the one
between 4 and 1, and finally the one between 1 and 2, for a total length of 7.

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

Problem 5: Wheel Rotation [Fatih Gelgi, 2008]

Farmer John has an old-time thresher (wheat harvester) that requires
belts to be installed on various gears to turn the parts. The engine
drives pulley 1 in a clockwise direction which attaches via a belt
to pulley 2. Pulley 2 attaches via a belt to pulley 3 and so on
through a total of N (2 <= N <= 1,000) pulleys (and N-1 belts).

The diagram above depicts the two ways a belt can be installed
between two gears. In this illustration, pulley 1's belt directly
drives pulley 2 (a 'straight' connection) and thus they will rotate
in the same direction. Pulley 3 drives pulley 4 via a 'crossed belt'
that reverses the direction of the rotation.

Given a list of the belt types that connect the pulleys along with
the fact that pulley 1 is driven in a clockwise direction by the
engine, determine the drive direction of pulley N. Each belt is
described by three integers:
  * S_i -- the driving (source) pulley
  * D_i -- the driven (destination) pulley
  * C_i -- the connection type (0=straight, 1=crossed)

Unfortunately, FJ lists the belts in random order.

By way of example, consider the illustration below. N = 4, and
pulley 1 is driven clockwise by the thresher engine. Straight
belts drive pulley 2 and then pulley 3, so they rotate clockwise. The
crosswise belt reverses the rotation direction so pulley 4 (pulley N)
rotates counterclockwise.

POINTS: 70

PROBLEM NAME: rotation

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N: Each line describes a belt with three integers: S_i,
        D_i, and C_i

SAMPLE INPUT (file rotation.in):

4
2 3 0
3 4 1
1 2 0

INPUT DETAILS:

As in the example illustration.

OUTPUT FORMAT:

* Line 1: A single integer that is the rotation direction for pulley N
        (0=clockwise, 1=counterclockwise)

SAMPLE OUTPUT (file rotation.out):

1

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

Problem 6: Power Failure [Rob Kolstad, 2008]

A vicious thunderstorm has destroyed some of the wires of the farm's
electrical power grid! Farmer John has a map of all N (2 <= N <=
1,000) of the powerpoles, which are conveniently numbered 1..N and
located on integer plane coordinates x_i,y_i (-100,000 <= x_i <=
100000; -100,000 <= y_i <= 100,000).

Some W (1 <= W <= 10,000) power wires connect pairs of power poles
Pi and Pj (1 <= Pi <= N; 1 <= Pj <= N).

He needs to get power from pole 1 to pole N (which means that some
series of wires can traverse from pole 1 to pole N, probably through
some intermediate set of poles).

Given the locations of the N poles and the list of remaining power
wires, determine the minimum length of power wire required to restore
the electrical connection so that electricity can flow from pole 1
to pole N.  No wire can be longer than some real number M (0.0 < M
<= 200,000.0).

As an example, below on the left is a map of the 9 poles and 3 wires
after the storm. For this task, M = 2.0. The best set of wires to
add would connect poles 4 and 6 and also poles 6 and 9.

      After the storm              Optimally reconnected

3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

The total length is then 1.414213562 + 1.414213562 = 2.828427124 .

POINTS: 350

PROBLEM NAME: pwrfail

INPUT FORMAT:

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

* Line 2: A single real number: M

* Lines 3..N+2: Each line contains two space-separated integers: x_i
        and y_i

* Lines N+3..N+2+W: Two space-separated integers: Pi and Pj

SAMPLE INPUT (file pwrfail.in):

9 3
2.0
0 0
0 1
1 1
2 1
2 2
3 2
3 3
4 1
4 3
1 2
2 3
3 4

INPUT DETAILS:

Just as in the diagram above.

OUTPUT FORMAT:

* Line 1: A single integer on a single line.  If restoring connection
        is impossible, output -1. Otherwise, output a single integer
        that is 1000 times the total minimum cost to restore
        electricity. Do not perform any rounding; truncate the
        resulting product.

SAMPLE OUTPUT (file pwrfail.out):

2828

OUTPUT DETAILS:

As above.

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