**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Four problems numbered 6 through 9
**********************************************************************

Problem 6: Waves [Richard Forster, BIO 2003, 2003]

Farmer John's cows thoroughly enjoy throwing pebbles into the lake
next to their grazing field. When a pebble hits the surface of the
lake, it generates a wave that propagates across the surface of the
lake.

The surface of the lake is represented by a large grid of squares.
The water at each square is at some depth, which is determined by
the interaction of the waves.  Before any pebbles are dropped, every
square (except those on the original river banks) has a depth of
0.  When displayed, each square will be represented as follows:

     o Square has a depth < 0
     - Square has a depth = 0
     * Square has a depth > 0
     X Square is part of the original river bank

When a pebble in dropped into the lake it causes a wave of raised
water to spread out in a diamond pattern that grows every second.
The depth of each square in the diamond is increased by 1 for just
one single second. This wave is followed two seconds later by a
wave of lowered water (depth decreased by 1) which also spreads out
as a diamond.  Each pebble causes only two waves, the raised wave
followed by the lowered wave.

For example, the diagram below shows the effect of a pebble dropped
in the middle of the lake at time intervals of 0, 1, 2 and 3 seconds:
after it is dropped:

0 seconds   1 second    2 seconds   3 seconds
 -------     -------     -------     ---*---
 -------     -------     ---*---     --*-*--
 -------     ---*---     --*-*--     -*-o-*-
 ---*---     --*-*--     -*-o-*-     *-o-o-*
 -------     ---*---     --*-*--     -*-o-*-
 -------     -------     ---*---     --*-*--
 -------     -------     -------     ---*---

The river banks have fixed x co-ordinates and run for the entire
length (top to bottom) of the lake with a width of a single square.
When a wave reaches a river bank, rather than carrying on, it
continues to grow but the part that hits the bank is reflected.

The early seconds of a wave hitting one of the river banks are shown
below. To make the picture clearer, the second wave of lowered water
is not shown:

1 second    2 seconds   3 seconds   4 seconds   5 seconds
 X------     X------     X--*---     X-*-*--     X*---*-
 X------     X--*---     X-*-*--     X*---*-     X*----*
 X--*---     X-*-*--     X*---*-     X*----*     X-*----
 X-*-*--     X*---*-     X*----*     X-*----     X--*---
 X--*---     X-*-*--     X*---*-     X*----*     X-*----
 X------     X--*---     X-*-*--     X*---*-     X*----*
 X------     X------     X--*---     X-*-*--     X*---*-

When sections of waves meet they have no effect on the way each
other propagates. In other words, at the next clock tick the waves
will grow as though there was no encounter. Note however that their
effects are combined on the lake.  For example:

 1 second      2 seconds     3 seconds     4 seconds
 ---------     ---------     ---------     ---*-----
 ---------     ---------     ---*-----     --*-*-*--
 ---------     ---*-----     --*-*-*--     -*-o-*-*-
 ---*-----     --*-*-*--     -*-o-*-*-     *-o-----*
 --*-*-*--     -*-o-*-*-     *-o-----*     -o-*-o---
 ---*-----     --*-*-*--     -*-o-*-*-     *-o-----*
 ---------     ---*-----     --*-*-*--     -*-o-*-*-
 ---------     ---------     ---*-----     --*-*-*--
 ---------     ---------     ---------     ---*-----

Write a program to help the cows figure out how the waves will
spread out over time.

PROBLEM NAME: waves

INPUT FORMAT:

* Line 1: Four space-separated integers: P, B1, B2, and R:

      * P (1 <= P <= 5) indicates the number of pebbles,<br>

      * B1 (-500,000 <= B1 <= 500,000) and B2 (-500,000 <= B2 <= 500,000)
        are the x co-ordinates of two river banks, and<br>

      * R (1 <= R <= 500,000) the time at which you are to display the lake.<br>

      No two pebbles will be dropped at the same position at the
      same time.  The two banks will have different x co-ordinates,
      and no pebble will be dropped on a bank.

* Lines 2..P+1: Each line contains three space-separated integers that
        describe a pebble: X (-500,000 <= X <= 500,000), Y (-500,000
        <= Y <= 500,000), and and T (1 <= T <= 500,000)

      * X and Y are the coordinates where a pebble is dropped

      * T is the time at which the pebble is dropped

SAMPLE INPUT (file waves.in):

2 4 100 4
-3 0 1
0 0 2

OUTPUT FORMAT:

* Lines 1..9: The output contains a 9 x 9 grid, centered on 0,0. The
        bottom left of the grid represents (-4, -4) and the top right
        represents (4,4). The grid should represent the state of the
        lake at time R.

SAMPLE OUTPUT (file waves.out):

--------X
-*------X
*-*-*---X
-o-*-*--X
o-----*-X
-o-*-*--X
*-*-*---X
-*------X
--------X

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

Problem 7: Navigating the City [Woburn Contest, 2005]

A dip in the milk market has forced the cows to move to the city.
The only employment available is in the venerable field of taxi-driving.
Help the cows learn their way around the city.

Given a city map with E (1 <= E <= 40) east/west street locations
and N (1 <= N <= 30) north/south street locations, create instructions
for a taxi driver to navigate from the start of his route (marked
'S') to the end (marked 'E'). Each instruction is a direction (one
of 'N', 'E', 'S', or 'W') followed by a space followed by an integer
that tells how many blocks to drive in that direction. If multiple
routes are available, your program should output the shortest route.
The shortest route is guaranteed to exist and be unique.

The map is depicted as a grid of '+'s that represent intersections
and a set of roads depicted as '-' and '|'.  Buildings and other
obstacles are shown as '.'s. Here is a typical map:

+-+-+.+-+-+
|...|.....|
+-+.+-+-+-+
..|.......|
S-+-+-+.E-+

The taxi should go east, north, west, north, east two blocks, and so on. 
See the output format and sample solution below for its complete route.

PROBLEM NAME: navcit

INPUT FORMAT:

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

* Lines 2..2*N: These lines each contain 2*E-1 characters and encode
        the map of the street. Every other input line gives the data
        for the east/west streets; the remaining lines show the
        north/south streets. The format should be clear from the
        example.

SAMPLE INPUT (file navcit.in):

3 6
+-+-+.+-+-+
|...|.....|
+-+.+-+-+-+
..|.......|
S-+-+-+.E-+

OUTPUT FORMAT:

* Lines 1..?: Each line contains a direction letter and a number of
        blocks to travel in that direction.

SAMPLE OUTPUT (file navcit.out):

E 1
N 1
W 1
N 1
E 2
S 1
E 3
S 1
W 1

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

Problem 8: Disease Manangement [Coaches, 2004]

Alas!  A set of D (1 <= D <= 15) diseases (numbered 1..D) is running through
the farm.  Farmer John would like to milk as many of his N (1 <= N <= 1,000)
cows as possible.  If the milked cows carry more than K (1 <= K <= D)
different diseases among them, then the milk will be too contaminated and
will have to be discarded in its entirety.  Please help determine the
largest number of cows FJ can milk without having to discard the milk.

PROBLEM NAME: disease

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 describes the diseases of cow i with a list
        of 1 or more space-separated integers. The first integer, d_i,
        is the count of cow i's diseases; the next d_i integers
        enumerate the actual diseases. Of course, the list is empty if
        d_i is 0.

SAMPLE INPUT (file disease.in):

6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1

OUTPUT FORMAT:

* Line 1: M, the maximum number of cows which can be milked.

SAMPLE OUTPUT (file disease.out):

5

OUTPUT DETAILS:

If FJ milks cows 1, 2, 3, 5, and 6, then the milk will have only two
diseases (#1 and #2), which is no greater than K (2). 

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

Problem 9: Muddy roads [Dutch Championships, via Jan Kuipers, 2004]

Farmer John has a problem: the dirt road from his farm to town has
suffered in the recent rainstorms and now contains (1 <= N <= 10,000)
mud pools.

Farmer John has a collection of wooden planks of length L that he
can use to bridge these mud pools. He can overlap planks and the
ends do not need to be anchored on the ground. However, he must
cover each pool completely.

Given the mud pools, help FJ figure out the minimum number of planks
he needs in order to completely cover all the mud pools.

PROBLEM NAME: mud

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains two space-separated integers: s_i
        and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the
        start and end points of a mud pool along the road. The mud
        pools will not overlap.  These numbers specify points, so a
        mud pool from 35 to 39 can be covered by a single board of
        length 4. Mud pools at (3,6) and (6,9) are not considered to
        overlap.

SAMPLE INPUT (file mud.in):

3 3
1 6
13 17
8 12

INPUT DETAILS:

FJ needs to use planks of length 3 to cover 3 mud pools.  The mud pools
cover regions 1 to 6, 8 to 12, and 13 to 17.

OUTPUT FORMAT:

* Line 1: The miminum number of planks FJ needs to use.

SAMPLE OUTPUT (file mud.out):

5

OUTPUT DETAILS:

FJ can cover the mud pools with five planks of length 3 in the
following way:
                   111222..333444555....
                   .MMMMM..MMMM.MMMM....
                   012345678901234567890

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