Problems - 2000 Winter Open, Green
PROBLEM 1: Gift Giving [Hal Burch] 
It's a holiday down at the farm. You've purchased gifts for the cows and now are trying to choose the perfect gift for each cow. Each cow has given you her wish list for gifts. Each cow will receive exactly one gift. A cow is pleased by her gift only if it appears on her wish list.

Your job is to determine the greatest number of cows that can be pleased given a certain set of gifts to give. The list of gifts might list a gift more than once if more than one was bought.

In this problem, each gift will be designated by an integer in the range 1..1000.

INPUT FORMAT:

Line 1: two integers: C, 1 <= C <= 100, the number of cows getting gifts G, C <= G <= 100, the number of gifts to give
Line 2: G single-space separated integers denoting gifts to give
Line 3..C+2: C lines specifying gifts cows want, each line like this:
n  w1 w2 ... wn
where n is the number of gifts that cow wants and w0, w1, etc. are the gift numbers.
SAMPLE INPUT (file INPUT.TXT):

5 5
35 35 483 622 801
1 35
1 35
1 35
3 483 622 801
3 35 801 483
OUTPUT FORMAT:

A single line with an integer that tells how many cows can be satisfied by the list of gifts.

SAMPLE OUTPUT (file OUTPUT.TXT):

4

[Problem|Data|Solutions]

PROBLEM 2: Building Blocks [Adapted by Hal Burch]
The cows want to build a tower out of the blocks they found. They want you to tell them how high the tower will be, given the sizes of the blocks. Each block has a width and length in addition to being one unit in height. The blocks must be stacked with all their edges parallel to a set of axes, and the blocks can be rotated 90 degrees, if you wish. In order to build a stable tower, each higher block must be no larger than the block on which it sits -- both the width and the length of each higher block must be no larger than the width and length of the block upon which it sits.

Your job is to determine the height of the tallest possible stable tower that can be built with a given collection of blocks.

INPUT FORMAT:

Line 1: one integer: B, 1 <= B <= 100, the number of blocks
Line 2..B+1: B lines, each with two integers denoting the width and length of a square block. Each of these dimensions is at least one unit and at most 100 units.
SAMPLE INPUT (file INPUT.TXT):

5
3 7
4 5
4 5
5 6
2 2

OUTPUT FORMAT:

A single line with an integer telling how high the tallest possible stable tower can be.

SAMPLE OUTPUT (file OUTPUT.TXT):

4

[Problem|Data|Solutions]

PROBLEM 3: Cow Calisthenics [Hal Burch & Russ Cox]
The cows hate calisthenics (exercises). They do, however, enjoy jogging a little bit. They have surveyed their pasture and have created a list of all the possible paths in the field. Interestingly, the paths are "directed" -- paths can be traversed only in one direction. Sometimes, two different paths connect a pair of points, one path going one way and one path going the other way.

Your job is to help the cows find the shortest "circular route" around which they can jog. A circular route is one which starts and ends at the same location. The length of a route is the sum of the lengths of the paths one must traverse to jog around the route.

Paths in their pasture always connect two points. Each point is named as a positive integer. These points are sequentially numbered, starting at 1. Distances between points are positive integers.

It is guaranteed that at least one "circular route" appears in any supplied cow pasture.

INPUT FORMAT:

Line 1: integer: N, 1 <= N <= 2000, the number of connections between pairs of points in the pasture; the number of distinct points will never exceed 400
Line 2..N+1: N lines specifying a space-separated beginning point, end point, and distance; no distances exceeds 1000
SAMPLE INPUT (file INPUT.TXT):

4
3 1 5
1 2 4
2 3 3
1 3 44

OUTPUT FORMAT:

A single line with the integer distance around the shortest possible circuit.

SAMPLE OUTPUT (file OUTPUT.TXT):

12

[Problem|Data|Solutions]

PROBLEM 4: Equal Summed Subsets [Adapted by Rob Kolstad]
Given the set of integers {1, 2, 3, ..., N}, determine the total number of ways you can divide the set into two equal-summed subsets A and B of that set. The union of A and B is the set of integers {1,2,...n} and A and B have no integers in common. Do not count answers that are just mirror images of each other, e.g.:

        {1, 4} and {2, 3}
              vs.
        {2, 3} and {1, 4}

counts as a single solution, not two solutions just because the two sets can be ordered the other way.

INPUT FORMAT:

A single line with an integer 1 <= N <= 36 that denotes the size of the set. It is guaranteed that at least one pair of equal summed subsets can be generated

SAMPLE INPUT (file INPUT.TXT):

12

OUTPUT FORMAT:

A single line with an integer that tells how many pairs of equal
summed subsets can be created.

SAMPLE OUTPUT (file OUTPUT.TXT):

62

[Problem|Data|Solutions]