Usaco Feb12 Gold

Part of USACO Feb12

**********************************************************************
                           GOLD PROBLEMS
**********************************************************************
                  Three problems numbered 1 through 3
**********************************************************************

Problem 1: Cow Coupons [Neal Wu and Mark Gordon, 2012]

Farmer John needs new cows! There are N cows for sale (1 <= N <= 50,000),
and FJ has to spend no more than his budget of M units of money (1 <= M <=
10^14).  Cow i costs P_i money (1 <= P_i <= 10^9), but FJ has K coupons (1
<= K <= N), and when he uses a coupon on cow i, the cow costs C_i instead
(1 <= C_i <= P_i). FJ can only use one coupon per cow, of course.

What is the maximum number of cows FJ can afford?

PROBLEM NAME: coupons

INPUT FORMAT:

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

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

SAMPLE INPUT (file coupons.in):

4 1 7
3 2
2 2
8 1
4 3

INPUT DETAILS:

FJ has 4 cows, 1 coupon, and a budget of 7.

OUTPUT FORMAT:

* Line 1: A single integer, the maximum number of cows FJ can afford.

SAMPLE OUTPUT (file coupons.out):

3

OUTPUT DETAILS:

FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of
3 + 2 + 1 = 6.

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

Problem 2: Symmetry [Brian Dean, 2012]

After taking a modern art class, Farmer John has become interested in
finding geometric patterns in everything around his farm.  He carefully
plots the locations of his N cows (2 <= N <= 1000), each one occupying a
distinct point in the 2D plane, and he wonders how many different lines of
symmetry exist for this set of points.  A line of symmetry, of course, is a
line across which the points on both sides are mirror images of each-other.  

Please help FJ answer this most pressing geometric question.

PROBLEM NAME: symmetry

INPUT FORMAT:

* Line 1: The single integer N.

* Lines 2..1+N: Line i+1 contains two space-separated integers
        representing the x and y coordinates of the ith cow (-10,000
        <= x,y <= 10,000).

SAMPLE INPUT (file symmetry.in):

4
0 0
0 1
1 0
1 1

INPUT DETAILS:

The 4 cows form the corners of a square.

OUTPUT FORMAT:

* Line 1: The number of different lines of symmetry of the point set.

SAMPLE OUTPUT (file symmetry.out):

4

OUTPUT DETAILS:

There are 4 lines of symmetry -- one vertical, one horizontal, and two
diagonal.

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

Problem 3: Nearby Cows [Neal Wu and Eric Price, 2011]

Farmer John has noticed that his cows often move between nearby fields. 
Taking this into account, he wants to plant enough grass in each of his
fields not only for the cows situated initially in that field, but also for
cows visiting from nearby fields.

Specifically, FJ's farm consists of N fields (1 <= N <= 100,000), where
some pairs of fields are connected with bi-directional trails (N-1 of them
in total).  FJ has designed the farm so that between any two fields i and
j, there is a unique path made up of trails connecting between i and j. 
Field i is home to C(i) cows, although cows sometimes move to a different
field by crossing up to K trails (1 <= K <= 20).  

FJ wants to plant enough grass in each field i to feed the maximum number
of cows, M(i), that could possibly end up in that field -- that is, the
number of cows that can potentially reach field i by following at most K
trails.  Given the structure of FJ's farm and the value of C(i) for each
field i, please help FJ compute M(i) for every field i.

PROBLEM NAME: nearcows

INPUT FORMAT:

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

* Lines 2..N: Each line contains two space-separated integers, i and j
        (1 <= i,j <= N) indicating that fields i and j are directly
        connected by a trail.

* Lines N+1..2N: Line N+i contains the integer C(i). (0 <= C(i) <=
        1000)

SAMPLE INPUT (file nearcows.in):

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

INPUT DETAILS:

There are 6 fields, with trails connecting (5,1), (3,6), (2,4), (2,1), and
(3,2).  Field i has C(i) = i cows.  

OUTPUT FORMAT:

* Lines 1..N: Line i should contain the value of M(i).

SAMPLE OUTPUT (file nearcows.out):

15
21
16
10
8
11

OUTPUT DETAILS:

Field 1 has M(1) = 15 cows within a distance of 2 trails, etc.

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