Problems - 2001 Winter Open, Green
PROBLEM 1: Counting Cows [Brian Dean, 2001] 

Farmer John's farm has several fenced-in fields, and FJ wants to know which of them currently contains the most cows. N (1 <= N <= 100) cows in total live at various integer coordinates in the two-dimensional plane that is the farm. This farm contains K (1 <= K <= 1000) fences. Each fence is a line segment of positive length with integer coordinates for endpoints. If fences intersect, they may do so only at their endpoints. No cow lives on any part of any fence or at the same point as any other cow.

A `field' is defined as an area of the farm which is completely enclosed by fences. A cow is said to belong to smallest field (in terms of area) which encloses it. It is possible for a cow not to belong to any fenced-in field, in which case we say that cow belongs to the "master" field. Your task is: given the layout of cows and fences, report the number of cows that belong to the field containing the most cows (including possibly the "master" field).

For example, in the three figures below, the answers are a:2, b:2, and c:1.

   +-------+               -------+                cow 1
   | cow 1 +--------+       cow 1 |               ________
   |          cow 2 |             |  cow 2       /       |
   +----------------+      -------+             +--------+

         (a)                  (b)                (c)      

      

INPUT FORMAT:

* Line 1: Two integers: N and K

* Lines 2..N+1: Two integers, the x,y coordinates for a cow

* Lines N+2..N+1+K: Four integers, endpoints of a fence coordinate

SAMPLE INPUT (file count.in):

This input corresponds to Figure b above.

2 3
4 5
10 3
3 0 7 0
7 0 7 6
0 6 7 6

OUTPUT FORMAT:

A single line with a single integer which is the number of cows contained within the field enclosing the most cows.

SAMPLE OUTPUT (file count.out):

2


PROBLEM 2: Herd Splitting [Brian Dean, 2001]

Farmer John wants to split his herd of N (1 <= N <= 40) cows into two herds. The i-th cow gives Mi liters of milk (1 <= Mi <= 100) per month, and FJ wants to split his cows such that the each of the resulting two herds produces the same amount of milk. Since it might not be possible to construct such an equal partition of the cows, FJ might first choose to remove some of the cows from the herd (as many as he wants) before splitting up the remaining cows into two equal groups. Let T be the total amount of milk produced by one of these two equally producing groups of cows. Your goal is to find the maximum possible value of T.

INPUT FORMAT:

* Line 1: One integer: N

* Lines 2..N+1: Each line contains one cow's milk production

SAMPLE INPUT (file split.in):

6
1
2
39
6
10
7

OUTPUT FORMAT:

A single line with a single integer which is the maximum value of T. If there is no way to remove some number of cows and then split the remaining cows into two herds with equal milk production, you should output the number 0.

SAMPLE OUTPUT (file split.out):

13
PROBLEM 3: Treasure Hunting [Brian Dean, 2001]

Farmer John (also known as FJ) has discovered a map containing the locations of buried hidden treasures on his farm. The treasures are numbered sequentially 1..N (1 <= N <= 100). Each treasure is hidden at a different (x,y) pair of integer coordinates buried at some integer depth (a positive integer denoted as z), and has some integer value (V).

FJ moves between two points in a "Manhattan" style, rather than on a diagonal line. For example, to move from (1,2) to (5,7), he would move 4 units for the first coordinate and then 5 units for the second coordinate. FJ moves at a rate of one unit per minute and digs at a rate of 0.5 units per minute. You are also given an integer time limit (T) on the total time FJ can spend hunting treasure.

Starting at the origin (0,0), FJ considers the treasures in sequence from 1 to N, and for each, he can decide to skip over the treasure or to move to it and dig it up (which takes some amount of time, but gives him some amount of value in return when the treasure is completely unearthed). Your task is to determine the maximum amount of value FJ can obtain within his time limit. FJ must return to the origin before his time limit expires.

INPUT FORMAT:

* Line 1: Two integers: N (1 <= N <= 80) and T (1 <= T <= 1,000,000)


* Lines 2..N+1: Four integers representing a treasure: x (-100 <= x <= 100),
y (-80 <= y <= 80), z (0 < z <= 25), and V (1 <= V <= 1000)

SAMPLE INPUT (file treas.in):

3 20
2 3 2 5
-5 0 8 51
2 -2 1 14

OUTPUT FORMAT:

A single line with a single integer that is maximum amount of value FJ can dig up during his treasure hunt.

SAMPLE OUTPUT (file treas.out):

19
PROBLEM 4: Cow Pool  [Rob Kolstad, 2000]

The cows have decided they simply must have a swimming pool for next summer. Furthermore, they have decided on a shape: they want an "L"-shaped pool. They will be putting this pool in a forest near their pastures and wish not to remove any trees. You will be given the size of the forest (W width by H high) and a set of N tree locations. Find the largest (by area) possible pool that can be put into the forest.

Here's an example grid and forest with the largest pool:

    .  .  *  .  .  .  .      .  .  *  .  .  .  .

    *  .  .  .  .  .  .      *  P  P  .  .  .  .

    .  .  .  *  *  *  .      .  P  P  *  *  *  .

    .  .  .  .  .  .  .      .  P  P  .  .  .  .

    *  .  .  *  .  *  .  ->  *  P  P  *  .  *  .

    .  .  .  .  .  .  .      .  P  P  P  P  P  .

    .  .  .  .  .  .  .      .  P  P  P  P  P  .

    *  .  .  .  .  .  *      *  P  P  P  P  P  *

    .  .  *  .  *  .  .      .  .  *  .  *  .  .


The largest pool covers 23 gridpoints.

Note the distinctive "L" shape of the pool. The "L" shape is formed by combining two rectangles that share the lower left hand part of the "L" shape. The lower bar of the "L" must be wider than the upper part of the "L". Likewise, the upper part of the "L" must be taller than the lower bar. The "L" shape is never rotated or reflected. A simple rectangle is not an "L" shape.

INPUT FORMAT:

* Line 1: Three integers, W (5 <= W <= 150), H (5 <= H <= 150), N (1 <= N <= 20000)

* Lines 2..N+1: each line contains two integers, that tell the row and column, respectively, of a tree. The upper left corner of the tree map is Row 1, Column 1. The top row in the example above contains a tree at Row 1, Column 3.

SAMPLE INPUT (file pool.in):

The example above has this input file:

7 9 12
1 3
2 1
3 4
3 5
3 6
5 1
5 4
5 6
8 1
8 7
9 3
9 5

OUTPUT FORMAT:

A single line with the number of gridpoints of the largest possible pool that can be built.

SAMPLE OUTPUT (file pool.out):

23
PROBLEM 5: Cows in Bed  [Hal Burch, 2001]

FJ has N (1 <= N <= 5000) cows who sleep in stalls in a barn with K stalls numbered 0..K-1. The i-th cow has a unique brand that is a number Si (1 <= Si <= 1,000,000). Each cow knows where to sleep because she sleeps in stall number Si mod K. Of course, cows will never want to share a stall for sleeping.

Given a set of cows and their brands, determine the minimum K such that no two cows sleep in the same stall.

INPUT FORMAT:

* Line 1: One integer: N

* Lines 2..N+1: One integer that is a cows brand

SAMPLE INPUT (file bed1.in):

5
4
6
9
10
13

OUTPUT FORMAT:

A single line with the minimum value of K on it. All legal input datasets can be solved within the allotted time.

SAMPLE OUTPUT (file bed1.out):

8