Usaco Nov08 Silver

Part of USACO Nov08

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

Problem 6: Buying Hay [Neal Wu, 2007]

Farmer John is running out of supplies and needs to purchase H (1
<= H <= 50,000) pounds of hay for his cows.

He knows N (1 <= N <= 100) hay suppliers conveniently numbered 1..N.
Supplier i sells packages that contain P_i (1 <= P_i <= 5,000)
pounds of hay at a cost of C_i (1 <= C_i <= 5,000) dollars. Each
supplier has an unlimited number of packages available, and the
packages must be bought whole.

Help FJ by finding the minimum cost necessary to purchase at least
H pounds of hay.

INPUT FORMAT:

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

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

2 15
3 2
5 3

OUTPUT FORMAT:

* Line 1: A single integer representing the minimum cost FJ needs to
pay to obtain at least H pounds of hay.

9

OUTPUT DETAILS:

FJ can buy three packages from the second supplier for a total cost of 9.

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

Problem 7: Guarding the Farm [Fatih Gelgi, 2008]

The farm has many hills upon which Farmer John would like to place
guards to ensure the safety of his valuable milk-cows.

He wonders how many guards he will need if he wishes to put one on
top of each hill. He has a map supplied as a matrix of integers;
the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns.
Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000).
Help him determine the number of hilltops on the map.

A hilltop is one or more adjacent matrix elements of the same value
surrounded exclusively by either the edge of the map or elements
with a lower (smaller) altitude. Two different elements are adjacent
if the magnitude of difference in their X coordinates is no greater
than 1 and the magnitude of differences in their Y coordinates is
also no greater than 1.

PROBLEM NAME: guardian

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 describes row i of the matrix with M
space-separated integers: H_ij

SAMPLE INPUT (file guardian.in):

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

OUTPUT FORMAT:

* Line 1: A single integer that specifies the number of hilltops

SAMPLE OUTPUT (file guardian.out):

3

OUTPUT DETAILS:

There are three peaks: The one with height 4 on the left top, one of
the points with height 2 at the bottom part, and one of the points with
height 1 on the right top corner.

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

Problem 8: Time Management [SLPC, 2008]

Ever the maturing businessman, Farmer John realizes that he must
manage his time effectively. He has N jobs conveniently numbered
1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning
the barn, mending the fences, and so on).

To manage his time effectively, he has created a list of the jobs
that must be finished. Job i requires a certain amount of time T_i
(1 <= T_i <= 1,000) to complete and furthermore must be finished
by time S_i (1 <= S_i <= 1,000,000). Farmer John starts his day at
time t=0 and can only work on one job at a time until it is finished.

Even a maturing businessman likes to sleep late; help Farmer John
determine the latest he can start working and still finish all the
jobs on time.

PROBLEM NAME: mtime

INPUT FORMAT:

* Line 1: A single integer: N

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

SAMPLE INPUT (file mtime.in):

4
3 5
8 14
5 20
1 16

INPUT DETAILS:

Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of
time, respectively, and must be completed by time 5, 14, 20, and
16, respectively.

OUTPUT FORMAT:

* Line 1: The latest time Farmer John can start working or -1 if
Farmer John cannot finish all the jobs on time.

SAMPLE OUTPUT (file mtime.out):

2

OUTPUT DETAILS:

Farmer John must start the first job at time 2. Then he can do
the second, fourth, and third jobs in that order to finish on time.

**********************************************************************```
```
page revision: 2, last edited: 06 Jun 2009 21:40