Usaco Mar12 Silver

Part of USACO Mar12

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

Problem 1: Tractor [Brian Dean, 2012]

After a long day of work, Farmer John completely forgot that he left his
tractor in the middle of the field.  His cows, always up to no good, decide
to play a prank of Farmer John: they deposit N bales of hay (1 <= N <=
50,000) at various locations in the field, so that Farmer John cannot
easily remove the tractor without first removing some of the bales of hay.  

The location of the tractor, as well as the locations of the N hay bales,
are all points in the 2D plane with integer coordinates in the range
1..1000.  There is no hay bale located at the initial position of the
tractor.  When Farmer John drives his tractor, he can only move it in
directions that are parallel to the coordinate axes (north, south, east,
and west), and it must move in a sequence of integer amounts.  For example,
he might move north by 2 units, then east by 3 units.  The tractor cannot
move onto a point occupied by a hay bale.

Please help Farmer John determine the minimum number of hay bales he needs
to remove so that he can free his tractor (that is, so he can drive his
tractor to the origin of the 2D plane).

PROBLEM NAME: tractor

INPUT FORMAT:

* Line 1: Three space-separated integers: N, and the (x,y) starting
        location of the tractor.

* Lines 2..1+N: Each line contains the (x,y) coordinates of a bale of
        hay.

SAMPLE INPUT (file tractor.in):

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

INPUT DETAILS:

The tractor starts at (6,3).  There are 7 bales of hay, at positions (6,2),
(5,2), (4,3), (2,1), (7,3), (5,4), and (6,4).

OUTPUT FORMAT:

* Line 1: The minimum number of bales of hay Farmer John must remove
        in order to open up a path for his tractor to move to the
        origin.

SAMPLE OUTPUT (file tractor.out):

1

OUTPUT DETAILS:

Farmer John only needs to remove one bale of hay to free his tractor.

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

Problem 2: Flowerpot [Brian Dean, 2012]

Farmer John has been having trouble making his plants grow, and needs your
help to water them properly.  You are given the locations of N raindrops  
(1 <= N <= 100,000) in the 2D plane, where y represents vertical height of
the drop, and x represents its location over a 1D number line:

Each drop falls downward (towards the x axis) at a rate of 1 unit per
second.  You would like to place Farmer John's flowerpot of width W
somewhere along the x axis so that the difference in time between the
first raindrop to hit the flowerpot and the last raindrop to hit the
flowerpot is at least some amount D (so that the flowers in the pot receive
plenty of water).  A drop of water that lands just on the edge of the
flowerpot counts as hitting the flowerpot.

Given the value of D and the locations of the N raindrops, please compute
the minimum possible value of W.

PROBLEM NAME: fpot

INPUT FORMAT:

* Line 1: Two space-separated integers, N and D.  (1 <= D <=
        1,000,000)

* Lines 2..1+N: Line i+1 contains the space-separated (x,y)
        coordinates of raindrop i, each value in the range
        0...1,000,000.

SAMPLE INPUT (file fpot.in):

4 5
6 3
2 4
4 10
12 15

INPUT DETAILS:

There are 4 raindrops, at (6,3), (2,4), (4,10), and (12,15).  Rain must
fall on the flowerpot for at least 5 units of time.

OUTPUT FORMAT:

* Line 1: A single integer, giving the minimum possible width of the
        flowerpot.  Output -1 if it is not possible to build a
        flowerpot wide enough to capture rain for at least D units of
        time.

SAMPLE OUTPUT (file fpot.out):

2

OUTPUT DETAILS:

A flowerpot of width 2 is necessary and sufficient, since if we place it
from x=4..6, then it captures raindrops #1 and #3, for a total rain
duration of 10-3 = 7.

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

Problem 3: Landscaping [Brian Dean, 2012]

Farmer John is building a nicely-landscaped garden, and needs to move a
large amount of dirt in the process.

The garden consists of a sequence of N flowerbeds (1 <= N <= 100), where
flowerbed i initially contains A_i units of dirt.  Farmer John would like
to re-landscape the garden so that each flowerbed i instead contains B_i
units of dirt.  The A_i's and B_i's are all integers in the range 0..10.

To landscape the garden, Farmer John has several options: he can purchase
one unit of dirt and place it in a flowerbed of his choice for $X.  He can
remove one unit of dirt from a flowerbed of his choice and have it shipped
away for $Y.  He can also transport one unit of dirt from flowerbed i to
flowerbed j at a cost of $Z times |i-j|.  Please compute the minimum total
cost for Farmer John to complete his landscaping project.

PROBLEM NAME: landscape

INPUT FORMAT:

* Line 1: Space-separated integers N, X, Y, and Z (0 <= X, Y, Z <=
        1000).

* Lines 2..1+N: Line i+1 contains the space-separated integers A_i and
        B_i.

SAMPLE INPUT (file landscape.in):

4 100 200 1
1 4
2 3
3 2
4 0

INPUT DETAILS:

There are 4 flowerbeds in a row, initially with 1, 2, 3, and 4 units of
dirt. Farmer John wishes to transform them so they have 4, 3, 2, and 0
units of dirt, respectively.  The costs for adding, removing, and
transporting dirt are 100, 200, and 1.

OUTPUT FORMAT:

* Line 1: A single integer giving the minimum cost for Farmer John's
        landscaping project.

SAMPLE OUTPUT (file landscape.out):

210

OUTPUT DETAILS:

One unit of dirt must be removed (from flowerbed #4), at a cost of 200.  The
remaining dirt can be moved at a cost of 10 (3 units from flowerbed #4 to
flowerbed #1, 1 unit from flowerbed #3 to flowerbed #2).

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