Usaco Open08 Bronze

Part of USACO Open08

``````**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Four problems numbered 11 through 14
**********************************************************************

Problem 11: Best Grass [Rob Kolstad, 2008]

Bessie is planning her day of munching tender spring grass and is gazing
out upon the pasture which Farmer John has so lovingly partitioned into a
grid with R (1 <= R <= 100) rows and C (1 <= C <= 100) columns. She wishes
to count the number of grass clumps in the pasture.

Each grass clump is shown on a map as either a single '#' symbol or perhaps
two '#' symbols side-by-side (but not on a diagonal). Given a map of the
pasture, tell Bessie how many grass clumps there are.

By way of example, consider this pasture map where R=5 and C=6:

.#....
..#...
..#..#
...##.
.#....

This pasture has a total of 5 clumps: one on the first row, one that spans
the second and third row in column 2, one by itself on the third row, one
that spans columns 4 and 5 in row 4, and one more in row 5.

PROBLEM NAME: bgrass

INPUT FORMAT:

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

* Lines 2..R+1: Line i+1 describes row i of the field with C
characters, each of which is a '#' or a '.'

SAMPLE INPUT (file bgrass.in):

5 6
.#....
..#...
..#..#
...##.
.#....

OUTPUT FORMAT:

* Line 1: A single integer that is the number of grass clumps Bessie
can munch

SAMPLE OUTPUT (file bgrass.out):

5

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

Problem 12: Going to the Movies [Rob Kolstad, 2008]

Farmer John is taking some of his cows to the movies! While his
truck has a limited capacity of C (100 <= C <= 5000) kilograms, he
wants to take the cows that, in aggregate, weigh as much as possible
without exceeding the limit C.

Given N (1 <= N <= 16) cows and their respective weights W_i, determine
the weight of the heaviest group of cows that FJ can take to the
movies.

PROBLEM NAME: cowflix

INPUT FORMAT:

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

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

SAMPLE INPUT (file cowflix.in):

259 5
81
58
42
33
61

OUTPUT FORMAT:

* Line 1: A single integer that is the weight of the heaviest group of
cows that can go to the movies

SAMPLE OUTPUT (file cowflix.out):

242

OUTPUT DETAILS:

81+58+42+61 = 242; this is the best possible sum

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

Problem 13: Clear Cold Water [Rob Kolstad, 2008]

The steamy, sweltering summers of Wisconsin's dairy district stimulate
the cows to slake their thirst. Farmer John pipes clear cold water
into a set of N (3 <= N <= 99999; N odd) branching pipes conveniently
numbered 1..N from a pump located at the barn. As the water flows
through the pipes, the summer heat warms it.  Bessie wants to find
the coldest water so she can enjoy the weather more than any other
cow.

She has mapped the entire set of branching pipes and noted that
they form a tree with its root at the farm and furthermore that
every branch point has exactly two pipes exiting from it. Surprisingly,
every pipe is exactly one unit in length; of course, all N pipes
connect up in one way or another to the pipe-tree.

Given the map of all the pipe connections, make a list of the
distance from the barn for every branching point and endpoint.
Bessie will use the list to find the very coldest water.

The endpoint of a pipe, which might enter a branching point or might
be a spigot, is named by the pipe's number. The map contains C (1
<= C <= N) connections, each of which specifies three integers: the
endpoint E_i (1 <= E_i <= N) of a pipe and two branching pipes B1_i
and B2_i (2 <= B1_i <= N; 2 <= B2_i <= N). Pipe number 1 connects
to the barn; the distance from its endpoint to the barn is 1.

PROBLEM NAME: coldwat

INPUT FORMAT:

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

* Lines 2..C+1: Line i+1 describes branching point i with three
space-separated integers: E_i, B1_i, and B2_i

SAMPLE INPUT (file coldwat.in):

5 2
3 5 4
1 2 3

INPUT DETAILS:

The input above describes this pipe map:

+------+
| Barn |
+------+
| 1
*
2 / \ 3
*
4 / \ 5

OUTPUT FORMAT:

* Lines 1..N: Line i of the output contains a single integer that is
the distance from the barn to the endpoint of pipe i

SAMPLE OUTPUT (file coldwat.out):

1
2
2
3
3

OUTPUT DETAILS:

Pipe 1 is always distance 1 from the barn. Pipes 2 and 3 connect directly
to pipe 1 and thus are distance 2 from the barn. Pipes 4 and 5, which
connect to pipe 3, are distance 3 from the barn.

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

Problem 14: Munching [Rob Kolstad, 2008]

Bessie loves her grass and loves to hurry to the barn for her evening
milking session. She has partitioned the pasture into a rectilinear
grid of R (1 <= R <= 100) rows and C (1 <= C <= 100) columns and
marked the squares as grass or rocky (she can't eat rocks and won't
even go into those squares). Bessie starts on her map at location
R_b,C_b and wishes to munch her way, square by square, to the barn
at location 1,1 by the shortest route possible. She moves from one
square to any one of the potentially four adjacent squares.

Below is the original map [with rocks ('*'), grass ('.'), the barn
('B'), and Bessie ('C' for cow) at row 5, col 6] and a route map
with the optimal route marked with munches ('m'):

Map               Optimal Munched Route
1 2 3 4 5 6  <-col      1 2 3 4 5 6  <-col
1 B . . . * .           1 B m m m * .
2 . . * . . .           2 . . * m m m
3 . * * . * .           3 . * * . * m
4 . . * * * .           4 . . * * * m
5 * . . * . C           5 * . . * . m

Bessie munched 9 squares.

Given a map, determine how many squares Bessie will eat on her
shortest route to the barn (there's no grass to eat on the barn's
square).

PROBLEM NAME: munch

INPUT FORMAT:

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

* Lines 2..R+1: Line i+1 describes row i with C characters (and no
spaces) as described above

SAMPLE INPUT (file munch.in):

5 6
B...*.
..*...
.**.*.
..***.
*..*.C

OUTPUT FORMAT:

* Line 1: A single integer that is the number of squares of grass that
Bessie munches on the shortest route back to the barn

SAMPLE OUTPUT (file munch.out):

9

**********************************************************************```
```
page revision: 1, last edited: 08 Jul 2011 02:28