Usaco Open12 Gold

Part of USACO Open12

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

Problem 1: Tied Down [Brian Dean, 2012]

As we all know, Bessie the cow likes nothing more than causing mischief on
the farm.  To keep her from causing too much trouble, Farmer John decides
to tie Bessie down to a fence with a long rope.  When viewed from above,
the fence consists of N posts (1 <= N <= 10) that are arranged along
vertical line, with Bessie's position (bx, by) located to the right of this
vertical line.  The rope FJ uses to tie down Bessie is described by a
sequence of M line segments (3 <= M <= 10,000), where the first segment
starts at Bessie's position and the last ends at Bessie's position. No
fence post lies on any of these line segments.  However, line segments may
cross, and multiple line segments may overlap at their endpoints.

Here is an example of the scene, viewed from above:

To help Bessie escape, the rest of the cows have stolen a saw from the
barn.  Please determine the minimum number of fence posts they must cut
through and remove in order for Bessie to be able to pull free (meaning she
can run away to the right without the rope catching on any of the fence posts).

All (x,y) coordinates in the input (fence posts, Bessie, and line segment
endpoints) lie in the range 0..10,000.  All fence posts have the same x
coordinate, and bx is larger than this value.

PROBLEM NAME: tied

INPUT FORMAT:

* Line 1: Four space-separated integers: N, M, bx, by.

* Lines 2..1+N: Line i+1 contains the space-separated x and y
        coordinates of fence post i.

* Lines 2+N..2+N+M: Each of these M+1 lines contains, in sequence, the
        space-separated x and y coordinates of a point along the rope.
        The first and last points are always the same as Bessie's
        location (bx, by).

SAMPLE INPUT (file tied.in):

2 10 6 1
2 3
2 1
6 1
2 4
1 1
2 0
3 1
1 3
5 4
3 0
0 1
3 2
6 1

INPUT DETAILS:

There are two posts at (2,3) and (2,1).  Bessie is at (6,1).  The rope goes
from (6,1) to (2,4) to (1,1), and so on, ending finally at (6,1). The shape
of the rope is the same as in the figure above.

OUTPUT FORMAT:

* Line 1: The minimum number of posts that need to be removed in order
        for Bessie to escape by running to the right.

SAMPLE OUTPUT (file tied.out):

1

OUTPUT DETAILS:

Removing either post 1 or post 2 will allow Bessie to escape.

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

Problem 2: Bookshelf [Neal Wu / Traditional, 2012]

When Farmer John isn't milking cows, stacking haybales, lining up his cows,
or building fences, he enjoys sitting down with a good book.  Over the
years, he has collected N books (1 <= N <= 100,000), and he wants to build
a new set of bookshelves to hold them all.  

Each book i has a width W(i) and height H(i).  The books need to be added
to a set of shelves in order; for example, the first shelf should contain
books 1...k for some k, the second shelf should start with book k+1, and so
on.  Each shelf can have a total width of at most L (1 <= L <=
1,000,000,000).  The height of a shelf is equal to the height of the
tallest book on that shelf, and the height of the entire set of bookshelves
is the sum of the heights of all the individual shelves, since they are all
stacked vertically.  

Please help FJ compute the minimum possible height for the entire set of
bookshelves.

PROBLEM NAME: bookshelf

INPUT FORMAT:

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

* Lines 2..1+N: Line i+1 contains two space-separated integers: H(i)
        and W(i).  (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).

SAMPLE INPUT (file bookshelf.in):

5 10
5 7
9 2
8 5
13 2
3 8

INPUT DETAILS:

There are 5 books.  Each shelf can have total width at most 10.

OUTPUT FORMAT:

* Line 1: The minimum possible total height for the set of
        bookshelves.

SAMPLE OUTPUT (file bookshelf.out):

21

OUTPUT DETAILS:

There are 3 shelves, the first containing just book 1 (height 5, width 7),
the second containing books 2..4 (height 13, width 9), and the third
containing book 5 (height 3, width 8).

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

Problem 3: Balanced Cow Subsets [Neal Wu, 2012]

Farmer John's owns N cows (2 <= N <= 20), where cow i produces M(i) units
of milk each day (1 <= M(i) <= 100,000,000).  FJ wants to streamline the
process of milking his cows every day, so he installs a brand new milking
machine in his barn.  Unfortunately, the machine turns out to be far too
sensitive: it only works properly if the cows on the left side of the barn
have the exact same total milk output as the cows on the right side of the
barn!  

Let us call a subset of cows "balanced" if it can be partitioned into two
groups having equal milk output.  Since only a balanced subset of cows can
make the milking machine work, FJ wonders how many subsets of his N cows
are balanced.  Please help him compute this quantity.

PROBLEM NAME: subsets

INPUT FORMAT:

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains M(i).

SAMPLE INPUT (file subsets.in):

4
1
2
3
4

INPUT DETAILS:

There are 4 cows, with milk outputs 1, 2, 3, and 4.

OUTPUT FORMAT:

* Line 1: The number of balanced subsets of cows.

SAMPLE OUTPUT (file subsets.out):

3

OUTPUT DETAILS:

There are three balanced subsets: the subset {1,2,3}, which can be
partitioned into {1,2} and {3}, the subset {1,3,4}, which can be
partitioned into {1,3} and {4}, and the subset {1,2,3,4} which can be
partitioned into {1,4} and {2,3}.

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