Usaco Nov07 Bronze

Part of USACO Nov07

``````**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Three problems numbered 11 through 13
**********************************************************************

Problem 11: Exploration [Jeffrey Wang, 2007]

Bessie is traveling on a road teeming with interesting landmarks.
The road is labeled just like a number line, and Bessie starts at
the "origin" (x = 0). A total of N (1 <= N <= 50,000) landmarks are
located at points x_1, x_2, ..., x_N  (-100,000 <= x_i <= 100,000).
Bessie wants to visit as many landmarks as possible before sundown,
which occurs in T (1 <= T <= 1,000,000,000) minutes. She travels 1
distance unit in 1 minute.

Bessie will visit the landmarks in a particular order. Since the
landmarks closer to the origin are more important to Farmer John,
she always heads for the unvisited landmark closest to the origin.
No two landmarks will be the same distance away from the origin.

Help Bessie determine the maximum number of landmarks she can visit
before the day ends.

PROBLEM NAME: explore

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single integer that is the
location of the ith landmark: x_i

SAMPLE INPUT (file explore.in):

25 5
10
-3
8
-7
1

INPUT DETAILS:

Bessie has 25 minutes before sundown, and there are 5 landmarks
located at positions 10, -3, 8, -7, and 1.

OUTPUT FORMAT:

* Line 1: The maximum number of landmarks Bessie can visit.

SAMPLE OUTPUT (file explore.out):

4

OUTPUT DETAILS:

Bessie sequentially visits the landmarks at locations 1, -3, -7,
and 8, after which she has traveled a total of 24 minutes.  She
cannot visit the next intended landmark at position 10, since this
would extend her total travel time to 26 minutes.

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

Problem 12: Speed Reading [Jeffrey Wang, 2007]

All K (1 <= K <= 1,000) of the cows are participating in Farmer
a single book with N (1 <= N <= 100,000) pages as fast as possible
while understanding it.

Cow i has a reading speed S_i (1 <= S_i <= 100) pages per minute,
a maximum consecutive reading time T_i (1 <= T_i <= 100) minutes,
and a minimum rest time R_i (1 <= R_i <= 100) minutes.  The cow can
read at a rate of S_i pages per minute, but only for T_i minutes
at a time. After she stops reading to rest, she must rest for R_i

Determine the number of minutes (rounded up to the nearest full
minute) that it will take for each cow to read the book.

INPUT FORMAT:

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

* Lines 2..K+1: Line i+1 contains three space-separated integers: S_i,
T_i, and R_i

10 3
2 4 1
6 1 5
3 3 3

INPUT DETAILS:

The book has 10 pages; 3 cows are competing. The first cow reads
at a rate of 2 pages per minute, can read for at most 4 minutes at
a time, and must rest for 1 minute after reading. The second reads
at a rate of 6 pages per minute, can read for at most 1 minute at
a time, and must rest 5 minutes after reading. The last reads at a
rate of 3 pages per minute, can read for at most 3 minutes at a
time, and must rest for 3 minutes after reading.

OUTPUT FORMAT:

* Lines 1..K: Line i should indicate how many minutes (rounded up to
the nearest full minute) are required for cow i to read the
whole book.

6
7
7

OUTPUT DETAILS:

The first cow can read 8 pages in 4 minutes, rest for 1 minute, and
read the last 2 pages in a minute. The second reads 6 pages in a
minute, rests for 5 minutes, and finishes in the next minute. The
last reads 9 pages in 3 minutes, rests for 3 minutes, and finishes
in the next minute.

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

Problem 13: Avoid The Lakes [Jeffrey Wang, 2007]

Farmer John's farm was flooded in the most recent storm, a fact
only aggravated by the information that his cows are deathly afraid
of water. His insurance agency will only repay him, however, an
amount depending on the size of the largest "lake" on his farm.

The farm is represented as a rectangular grid with N (1 <= N <=
100) rows and M (1 <= M <= 100) columns. Each cell in the grid is
either dry or submerged, and exactly K (1 <= K <= N*M) of the cells
are submerged. As one would expect, a lake has a central cell to
which other cells connect by sharing a long edge (not a corner).
Any cell that shares a long edge with the central cell or shares a
long edge with any connected cell becomes a connected cell and is
part of the lake.

PROBLEM NAME: lake

INPUT FORMAT:

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

* Lines 2..K+1: Line i+1 describes one submerged location with two
space separated integers that are its row and column: R and C

SAMPLE INPUT (file lake.in):

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

INPUT DETAILS:

The farm is a grid with three rows and four columns; five of the cells
are submerged. They are located in the positions (row 3, column 2);
(row 2, column 2); (row 3, column 1); (row 2, column 3); (row 1,
column 1):
# . . .
. # # .
# # . .

OUTPUT FORMAT:

* Line 1: The number of cells that the largest lake contains.

SAMPLE OUTPUT (file lake.out):

4

OUTPUT DETAILS:

The largest lake consists of the input's first four cells.

**********************************************************************```
```
page revision: 5, last edited: 08 Jul 2011 07:17