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.
PROBLEM NAME: buyhay
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
SAMPLE INPUT (file buyhay.in):
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.
SAMPLE OUTPUT (file buyhay.out):
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