Usaco Mar08 Silver

Part of USACO Mar08

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

Problem 6: The Loathesome Hay Baler [Rob Kolstad, 2008]

Farmer John has purchased the world's most loathesome hay baler.
Instead of having a drive-roller that drives maybe an idler roller
that drives the power take-off for the baler, it has N rollers (2
<= N <= 1050) which drive and are driven by various rollers.

FJ has meticulously cataloged data for each roller i: X_i,Y_i are
the center of the roller (-5000 <= X_i <= 5000; -5000 <= Y_i <=
5000); R_i is the roller's radius (3 <= R_i <= 800). The drive-roller
is located at 0,0; the baler power take-off is located at X_t,Y_t
(numbers supplied in the input).

The drive-roller turns clockwise at 10,000 revolutions per hour.
Your job is to determine the speeds of all the rollers that are in
the power-train: from the drive-roller through the power take-off
roller. Rollers that do not transfer power to the take-off roller
are to be ignored. A roller of radius Rd that is turning at S rph
and driving another roller of radius Rx will cause the second roller
to turn at the speed -S*Rd/Rx (where the sign denotes whether the
roller is turning clockwise or counterclockwise (anticlockwise for
our British friends)).

Determine the power-train path and report the sum of the absolute
values of all those rollers' speeds. All the rollers in the input
set except the driver-roller are driven by some other roller; power
is never transferred to a roller from more than one other roller.

Report your answer as an integer that is the truncated value after
summing all the speeds.

PROBLEM NAME: baler

INPUT FORMAT:

* Line 1: Three space-separated integers: N, X_t, and Y_t

* Lines 2..N+1: Line i+1 describes roller i's properties: X_i, Y_i,
        and R_i

SAMPLE INPUT (file baler.in):

4 32 54
0 0 10
0 30 20
32 54 20
-40 30 20

INPUT DETAILS:

Four rollers: the drive-roller at 0,0 with radius 10. It drives the
roller above it at 0,30 with radius 20. That roller drives both the
power take-off roller at 32,54 (r=20) and a random roller (not in
the power train) at -40,30 (r=20).

OUTPUT FORMAT:

* Line 1: A single integer that is the truncated version of the sum of
        the absolute value of the speeds of the rollers in the
        power-train including the drive-roller, all the driven
        rollers, and the power take-off roller.

SAMPLE OUTPUT (file baler.out):

20000

OUTPUT DETAILS:

 Roller   Radius   Speed
1 (0,0)     10     10,000
2 (0,30)    20     -5,000
3 (32,54)   20      5,000
                   ------
Sum of abs values: 20,000

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

Problem 7: Cow Travelling [Aram Shatakhtsyan, 2007]

Searching for the very best grass, the cows are travelling about
the pasture which is represented as a grid with N rows and M columns
(2 <= N <= 100; 2 <= M <= 100). Keen observer Farmer John has
recorded Bessie's position as (R1, C1) at a certain time and then
as (R2, C2) exactly T (0 < T <= 15) seconds later. He's not sure
if she passed through (R2, C2) before T seconds, but he knows she
is there at time T.

FJ wants a program that uses this information to calculate an integer
S that is the number of ways a cow can go from (R1, C1) to (R2, C2)
exactly in T seconds. Every second, a cow can travel from any
position to a vertically or horizontally neighboring position in
the pasture each second (no resting for the cows). Of course, the
pasture has trees through which no cow can travel.

Given a map with '.'s for open pasture space and '*' for trees,
calculate the number of possible ways to travel from (R1, C1) to
(R2, C2) in T seconds.

PROBLEM NAME: ctravel

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 describes row i of the pasture with exactly M
        characters that are each '.' or '*'

* Line N+2: Four space-separated integers: R1, C1, R2, and C2.

SAMPLE INPUT (file ctravel.in):

4 5 6
...*.
...*.
.....
.....
1 3 1 5

INPUT DETAILS:

The pasture is 4 rows by 5 colum. The cow travels from row 1, column
3 to row 1, column 5, which takes exactly 6 seconds.

OUTPUT FORMAT:

* Line 1: A single line with the integer S described above.

SAMPLE OUTPUT (file ctravel.out):

1

OUTPUT DETAILS:

There is only one way from (1,3) to (1,5) in exactly 6 seconds (and
it is the obvious one that travels around the two trees).

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

Problem 8: River Crossing [Jeffrey Wang, 2007]

Farmer John is herding his N cows (1 <= N <= 2,500) across the
expanses of his farm when he finds himself blocked by a river.
A single raft is available for transportation.

FJ knows that he must ride on the raft for all crossings and that
that adding cows to the raft makes it traverse the river more slowly.

When FJ is on the raft alone, it can cross the river in M minutes
(1 <= M <= 1000).  When the i cows are added, it takes M_i minutes
(1 <= M_i <= 1000) longer to cross the river than with i-1 cows
(i.e., total M+M_1 minutes with one cow, M+M_1+M_2 with two, etc.).
Determine the minimum time it takes for Farmer John to get all of
the cows across the river (including time returning to get more
cows).

PROBLEM NAME: river

INPUT FORMAT:

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

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

SAMPLE INPUT (file river.in):

5 10
3
4
6
100
1

INPUT DETAILS:

There are five cows. Farmer John takes 10 minutes to cross the river
alone, 13 with one cow, 17 with two cows, 23 with three, 123 with
four, and 124 with all five.

OUTPUT FORMAT:

* Line 1: The minimum time it takes for Farmer John to get all of the
        cows across the river.

SAMPLE OUTPUT (file river.out):

50

OUTPUT DETAILS:

Farmer John can first cross with three cows (23 minutes), then
return (10 minutes), and then cross with the last two (17 minutes).
23+10+17 = 50 minutes total.

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